Czy istnieje leniwy sposób na zapisanie funkcji minusa (usunięcie elementów z listy)?

Question

Moja funkcja wygląda tak:

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

Może być stosowany tak:

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

z wyjściem: [99,44,23423]

Napisałem to, bo patrzę na Projekt Euler problemu 7 , a Sito Eratostenesa wydaje się być właściwym narzędziem i tak było, ale czytałem dalej Wikipedia page i dotarłem do części o sicie Eulera.

Próbowałem skopiować/wkleić kod i uruchomić go w GHCi, ale moja wersja GHCi nie ma modułu o nazwie Data.OrdList i nie mogłem znaleźć funkcji o nazwie minus w Hoogle.

Jest to kod z Wikipedii:

import Data.OrdList (minus) 

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

Gdybym zastąpić moją funkcję minus tam, otrzymuję out błędu pamięci, ponieważ moja funkcja nie jest leniwy.

Czy istnieje sposób na wykonanie funkcji leniwy minus?

Czy moja funkcja minusa działa tak samo, jak funkcja minus w artykule z Wikipedii?

Answer 1

Jak zauważył sepp2k, implementacja minus musi przyjmować uporządkowane listy. Oto możliwe wdrożenie:

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

Czy istnieje sposób na wykonanie funkcji leniwy minus?

Jeśli nie zakładasz, że listy wejściowe są uporządkowane (i nie masz pozwolenia na ich sortowanie), nie ma. Musisz wiedzieć, czy pierwszy element listy1 znajduje się na liście2, zanim będziesz wiedział, jaki będzie pierwszy element wyniku. Więc nie możesz ominąć konieczności oceny całej drugiej listy przed wyprodukowaniem pojedynczego elementu w najgorszym przypadku.

Jeśli jednak przyjmiesz, że listy wejściowe są uporządkowane (to, czego minus użyty przez Wikipedię ma wyraźnie jako moduł nazywa się * Lista Ord *), bardzo łatwo jest napisać funkcję ujemną, która jest wystarczająco leniwa.

A skoro lista wejść jest faktycznie uporządkowana, taka funkcja minus będzie działać idealnie dla twoich potrzeb.

Answer 3

Google uzyskał lepsze wyniki niż Hoogle.

Zrobione z 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