Удалить последовательные дубликаты из бесконечного списка с помощью свертывания?

Рассмотрим одну из следующих реализаций функции для удаления последовательных дубликатов из списка:

uniq :: Eq a => [a] -> [a]
uniq [] = []
uniq (x:xs) = x:uniq (dropWhile (x ==) xs)

uniq :: Eq a => [a] -> [a]
uniq (x:xs@(y:_))
 | x == y    = x:tail (uniq xs)
 | otherwise = x:uniq xs
uniq l = l

Они оба работают как положено как в конечном, так и в бесконечном списках. Чтобы быть более конкретным, для бесконечных списков, я ожидаю take n $ uniq l завершать до тех пор, пока не будет бесконечно длинных последовательностей повторяющихся значений, прежде чем n значения для возврата.

Теперь рассмотрим эту попытку такой функции, используя foldr:

uniq :: (Foldable t, Eq a) => t a -> [a]
uniq = foldr uniqHelper []
 where uniqHelper x [] = [x]
       uniqHelper x acc@(y:_)
        | x == y    =   acc
        | otherwise = x:acc

Это работает правильно для конечных списков, но никогда не завершается для бесконечных, потому что uniqHelper всегда нужно оценивать свой второй аргумент. Это то, что можно исправить с помощью более умного uniqHelperили по своей сути невозможно использовать фальцовку для этой задачи?

Источник

3 ответа

Решение

Вы можете перенести удаление элемента в хвост, поэтому, независимо от значения, мы сначала "уступаем" x, а затем мы используем функцию (здесь tl) оценить хвост списка:

uniq :: (Foldable t, Eq a) => t a -> [a]
uniq = foldr uniqHelper []
 where uniqHelper x acc = x : tl acc
           where tl acc@(x2:xs) | x == x2 = xs
                                | otherwise = acc
                 tl [] = []

Таким образом, мы сначала x, а потом беспокоиться о следующем элементе позже. Если второй параметр (свернутый список хвоста списка) содержит тот же элемент, то мы его "удаляем", в противном случае мы сохраняем весь список.

Вышесказанное также может дать первый элемент repeat, например:

Prelude> head (uniq (repeat 1))
1
Prelude> take 5 $ uniq [1..]
[1,2,3,4,5]
Prelude> uniq [1,1,1,1,2,2,2,1,1,1,1,1,1,3,3,3,3,1,1]
[1,2,1,3,1]

Конечно, если есть бесконечное количество 0с последующим 1, тот 1 никогда не излучается:

Prelude> uniq (repeat 0 ++ [1])
[0
Источник

Ваш первый фрагмент производит первый x из многих, но третий фрагмент производит последний x, в этом причина расхождения.

Чтобы точно отобразить первый фрагмент как правильный сгиб, мы сворачиваем в функции, чтобы мы могли передавать аргумент состояния, время от времени обновляемый до нового уникального элемента списка:

uniq [] = []
uniq (x:xs) = x : foldr g (const []) xs x
  where
  g y r x | y==x  =     r x
      | otherwise = y : r y

Это фактически пропускает дубликаты вместо повторного использования, а затем игнорирует их снова и снова, как и два других ответа, которые фактически эквивалентны друг другу: dropWhile может пропустить только один элемент, который затем будет пропущен следующим редуктором, вызывающим его dropWhile (==x),

Я всегда использую r в качестве имени второго аргумента редуктора, в качестве мнемонического устройства для "результирующего результата". Здесь наличие еще одного аргумента после r в g определение означает, что r это функция, которой мы можем передать обновленное значение, выступающее в качестве состояния.

Этот метод позволяет использовать foldr для кодирования вычислений с состоянием, таких как take, drop, dropWhile, takeWhile и т. д.

> head $ uniq $ repeat 1
1

> take 10 $ uniq [n | n <- [1..], n <- replicate n n]
[1,2,3,4,5,6,7,8,9,10]

> uniq [1..10]
[1,2,3,4,5,6,7,8,9,10]
Источник

Вы можете просто объединить свои реализации:

uniq :: Eq a => [a] -> [a]
uniq = foldr uniqHelper []
  where uniqHelper x acc = x : dropWhile (==x) acc

чтобы получить желаемое поведение в бесконечных списках:

Prelude> take 5 $ uniq [1..]
[1,2,3,4,5]
Источник
Другие вопросы по тегам