¿existe alguna forma de escribir la función menos (eliminar elementos de una lista)?

Question

Mi función es el siguiente:

minus :: (Eq a) => [a] -> [a] -> [a] 
minus [] xs      = [] 
minus (y:ys) xs | y `notElem` xs = y : (minus ys xs) 
       | otherwise  = minus ys xs 

Se puede utilizar la siguiente manera:

[99,44,55,22,23423] `minus` [55,22] 

con la salida: [99,44,23423]

escribí esto porque estoy mirando problema Proyecto Euler 7 , y el Tamiz de Eratóstenes parece ser la herramienta correcta, y lo fue, pero seguí leyendo el Wikipedia page y llegué a la parte sobre el tamiz de Euler.

Intenté copiar/pegar el código y ejecutarlo en GHCi, pero mi versión de GHCi no tiene un módulo llamado Data.OrdList, y no pude encontrar una función llamada minus en Hoogle.

Este es el código de Wikipedia:

import Data.OrdList (minus) 

primes = euler [2..] 
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs)) 

Si sustituyo mi función menos allí, me sale un error de falta de memoria, porque mi función no es perezoso.

¿Hay alguna manera de hacer una función de menos perezoso?

¿Mi función menos hace lo mismo que la función menos en el artículo de Wikipedia?

Answer 1

Como sepp2k señaló, la implementación de minus debe asumir listas ordenadas. Aquí hay una posible implementación:

minus :: Ord a => [a] -> [a] -> [a] 
minus [] _ = [] 
minus xs [] = xs 
minus l1@(x:xs) l2@(y:ys) 
    | x > y = minus l1 ys 
    | x < y = x : minus xs l2 
    | otherwise = minus xs l2 

Answer 2

¿Hay alguna manera de hacer una función menos activa?

Si no asume que las listas de entrada están ordenadas (y no tiene permiso para ordenarlas), no las hay. Tendrá que saber si el primer elemento de list1 está en list2 antes de saber cuál será el primer elemento del resultado. Por lo tanto, no puede evitar tener que evaluar toda la segunda lista antes de producir un solo elemento en el peor de los casos.

Sin embargo, si asume que las listas de entrada están ordenadas (que el menos utilizado por wikipedia claramente hace ya que el módulo se llama * Ord * List), es muy fácil escribir una función menos que sea floja.

Y dado que su lista de entrada en realidad está ordenada, dicha función menos funcionaría perfectamente para sus necesidades.

Answer 3

Google superó a Hoogle.

Tomado de http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/src/Data-OrdList.html

minus :: (Ord a) => [a] -> [a] -> [a] 
minus = minusBy compare 

minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] 
minusBy cmp = loop 
    where 
    loop [] _ys = [] 
    loop xs [] = xs 
    loop (x:xs) (y:ys) 
     = case cmp x y of 
      LT -> x : loop xs (y:ys) 
      EQ ->  loop xs ys 
      GT ->  loop (x:xs) ys