Есть ли ленивый способ написать функцию минус (удалить элементы из списка)? - PullRequest
Новая
       8

Есть ли ленивый способ написать функцию минус (удалить элементы из списка)?

6 голосов
/ 01 октября 2010

Моя функция выглядит следующим образом: 

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

Может использоваться следующим образом: 

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

с выводом: [99,44,23423]

Я написал это, потому чтоЯ смотрю на проблему Проекта Эйлера 7, и Сито Эратосфена кажется правильным инструментом, и так оно и было, но я продолжал читать страницу Википедия и дошел до части о сите Эйлера.*

Я попытался скопировать / вставить код и запустить его в GHCi, но в моей версии GHCi нет модуля с именем Data.OrdList, и я не смог найти функцию с именем minus в Hoogle.

Это код из Википедии: 

 import Data.OrdList (minus)

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

Если я подставлю туда свою минус-функцию, я получу ошибку нехватки памяти, потому что моя функция не ленивая.

Есть ли способ сделать ленивую функцию минус?

Моя функция минус работает так же, как функция минус в статье в Википедии?

Ответы [ 3 ]

6 голосов
/ 02 октября 2010

Как указал sepp2k, реализация minus должна предполагать упорядоченные списки.Вот возможная реализация: 

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
5 голосов
/ 01 октября 2010

Есть ли способ сделать функцию "ленивый минус"?

Если вы не предполагаете, что входные списки упорядочены (и вы не можете их сортировать), это не так. Вам нужно знать, находится ли первый элемент списка list1 в list2, прежде чем вы узнаете, каким будет первый элемент результата. Таким образом, вы не можете обойтись без оценки всего второго списка, прежде чем создавать единственный элемент в худшем случае.

Однако, если вы предполагаете, что входные списки упорядочены (что минус, используемый в Википедии явно делает, когда модуль называется * Ord * List), очень легко написать функцию минуса, которая достаточно ленива.

А поскольку ваш список ввода фактически упорядочен, такая функция минуса будет отлично работать для ваших нужд.

3 голосов
/ 02 октября 2010

Google превзошел Google.

Взято из 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
...