Охрана Хаскелла не встречается

Question

test :: [String] -> [String]

test = foldr step []

  where step x ys

          | elem x ys = x : ys

          | otherwise = ys

Я пытаюсь создать новый список, состоящий из всех различных вводимых строк.Мои тестовые данные:

test ["one", "one", "two", "two", "three"]

ожидаемый результат:

["one", "two", "three"]

Я новичок в Haskell, и я уверен, что мне не хватает чего-то очень фундаментального и очевидного, но все кончилосьспособов исследовать это.Не могли бы вы указать, где мое мышление несовершенно?

Фактический ответ - [].Кажется, что первое условие защиты никогда не выполняется (если я заменю его на True, исходный список будет реплицирован), поэтому список вывода никогда не будет создан.

Насколько я понимаю, складка будет накапливатьРезультат шага по каждому элементу списка, добавление его в пустой список.Я ожидал, что этот шаг проверит каждый элемент на предмет его включения в список вывода (первый проверенный элемент отсутствует) и добавит все, что еще не было включено в список вывода.Очевидно, нет: -)

Answer 1

Подумайте об этом: ваш код говорит: «когда x находится в остатке, добавьте x к результату», то есть создайте дубликат. Вам просто нужно изменить его на «когда x не находится в остатке, добавьте x к результату», и вы получите правильную функцию.

Эта функция существенно отличается от Data.List.nub: эта функция более строгая. Таким образом:

test [1..] = _|_   -- infinite loop (try it)
nub [1..] = [1..]

nub дает правильный ответ для бесконечных списков - это означает, что ему не нужен весь список, чтобы начать вычислять результаты, и, таким образом, он является хорошим игроком в игре потоковой обработки.

Причина, по которой он является строгим, заключается в том, что elem является строгим: он просматривает весь список (предполагая, что не находит совпадений), прежде чем возвращает результат. Вы можете написать это так:

nub :: (Eq a) => [a] -> [a]
nub = go []
    where
    go seen [] = []
    go seen (x:xs) | x `elem` seen = go seen xs
                   | otherwise     = x : go (x:seen) xs

Обратите внимание, как seen растет как результат до , тогда как ваш растет как остаток от . Первый всегда конечен (начиная с [] и добавляя по одному за раз), тогда как последний может быть бесконечным (например, [1..]). Таким образом, этот вариант может давать элементы более лениво.

Это было бы быстрее (O (n log n) вместо O (n ^ 2)), если бы вы использовали Data.Set вместо списка для seen. Но это добавляет ограничение Ord.

Answer 2

Ваши рассуждения верны: вам просто нужно переключить = x : ys и = ys, чтобы добавить x, когда не элемент ys.Кроме того, Data.List.nub делает именно эту вещь.