c'è un modo pigro per scrivere la funzione meno (rimuovere elementi da una lista)?

Question

La mia funzione è simile al seguente:

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

Può essere utilizzato in questo modo:

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

con uscita: [99,44,23423]

ho scritto questo perché sto guardando Project Euler problema 7 e il setaccio di Eratostene sembra lo strumento giusto, e lo è stato, ma ho continuato a leggere il numero Wikipedia page e sono arrivato alla parte sul setaccio di Eulero.

Ho provato a copiare/incollare il codice ed eseguirlo in GHCi, ma la mia versione di GHCi non ha un modulo chiamato Data.OrdList e non ho trovato una funzione chiamata minus in Hoogle.

Questo è il codice da Wikipedia:

import Data.OrdList (minus) 

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

Se sostituisco la mia funzione meno in là, ottengo un errore di memoria, perché la mia funzione non è pigro.

C'è un modo per rendere una funzione meno pigro?

La funzione Minus fa la stessa cosa della funzione minus nell'articolo di Wikipedia?

Answer 1

Come sottolineato da Sepp2k, l'implementazione di minus deve assumere elenchi ordinati. Ecco una possibile implementazione:

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

C'è un modo per rendere una funzione meno pigro?

Se non si assume che gli elenchi di input siano ordinati (e non è possibile ordinarli), non lo è. Dovrai sapere se il primo elemento di list1 è in list2 prima di sapere quale sarà il primo elemento del risultato. Quindi non puoi andare in giro a dover valutare l'intera seconda lista prima di produrre un singolo elemento nel peggiore dei casi.

Tuttavia, se si presuppone che gli elenchi di input siano ordinati (il meno utilizzato da wikipedia chiaramente come il modulo è chiamato * Ord * List), è molto facile scrivere una funzione meno sufficientemente pigra.

E dal momento che l'elenco di input è effettivamente ordinato, tale funzione meno funzionerebbe perfettamente per le vostre esigenze.

Answer 3

Google ha sovraperformato Hoogle.

Tratto da 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