Как реализовать удаление с помощью foldr в Haskell

Ответ 1

delete - это модальный поиск. Он имеет два разных режима работы - независимо от того, нашел ли он результат или нет. Вы можете использовать foldr для построения функции, которая передает состояние по строке, когда проверяется каждый элемент. Поэтому в случае delete состояние может быть простым Bool. Это не совсем лучший тип, но он будет делать.

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

{-# LANGUAGE ScopedTypeVariables #-}

delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f undefined xs undefined
  where
    f :: a -> (Bool -> [a]) -> (Bool -> [a])
    f x g = undefined

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

{-# LANGUAGE ScopedTypeVariables #-}

delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f undefined xs undefined
  where
    f :: a -> (Bool -> [a]) -> (Bool -> [a])
    f x g found | x == a && not found = g True
                | otherwise           = x : g found

Это кажется относительно простым. Если текущий элемент является искомым, и он еще не найден, не выводите его и продолжайте с состоянием, установленным на True, указав, что оно было найдено. otherwise, выведите текущее значение и продолжите текущее состояние. Это оставит остальные аргументы foldr. Последнее - начальное состояние. Другой - функция состояния для пустого списка. Хорошо, это тоже неплохо.

{-# LANGUAGE ScopedTypeVariables #-}

delete :: forall a. Eq a => a -> [a] -> [a]
delete a xs = foldr f (const []) xs False
  where
    f :: a -> (Bool -> [a]) -> (Bool -> [a])
    f x g found | x == a && not found = g True
                | otherwise           = x : g found

Независимо от того, что такое состояние, создайте пустой список, когда встречается пустой список. И начальное состояние состоит в том, что искомый элемент еще не найден.

Этот метод применим и в других случаях. Например, foldl можно записать как foldr таким образом. Если вы посмотрите на foldl как функцию, которая многократно преобразует исходный аккумулятор, вы можете предположить, что создаваемая функция - как преобразовать начальное значение.

{-# LANGUAGE ScopedTypeVariables #-}

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr g id xs z
  where
    g :: b -> (a -> a) -> (a -> a)
    g x cont acc = undefined

Базовые случаи не слишком сложны, чтобы найти, когда проблема определяется как манипуляция исходным аккумулятором с именем z. Пустым списком является преобразование идентичности, id, а значение, переданное созданной функции, равно z.

Реализация g сложнее. Это нельзя просто сделать слепо на типах, потому что есть две разные реализации, которые используют все ожидаемые значения и проверку типов. Это случай, когда типов недостаточно, и вам нужно учитывать значения доступных функций.

Давайте начнем с инвентаризации значений, которые, похоже, должны использоваться, и их типов. Вещи, которые, похоже, должны быть использованы в теле g, это f :: a -> b -> a, x :: b, cont :: (a -> a) и acc :: a. f, очевидно, возьмет x как свой второй аргумент, но есть вопрос о подходящем месте для использования cont. Чтобы выяснить, где это происходит, помните, что он представляет функцию преобразования, возвращаемую обработкой остальной части списка, и что foldl обрабатывает текущий элемент, а затем передает результат этой обработки в остальную часть списка.

{-# LANGUAGE ScopedTypeVariables #-}

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl f z xs = foldr g id xs z
  where
    g :: b -> (a -> a) -> (a -> a)
    g x cont acc = cont $ f acc x

Это также предполагает, что foldl' можно записать таким образом только с одним крошечным изменением:

{-# LANGUAGE ScopedTypeVariables #-}

foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a
foldl' f z xs = foldr g id xs z
  where
    g :: b -> (a -> a) -> (a -> a)
    g x cont acc = cont $! f acc x

Разница заключается в том, что ($!) используется для оценки оценки f acc x, прежде чем он перейдет к cont. (Я говорю "предлагаю", потому что есть некоторые случаи ребер, где ($!) не вызывает оценку даже до WHNF.)

Ответ 2

delete не работает по всему списку равномерно. Структура вычисления не просто рассматривает весь список по одному элементу за раз. Он отличается тем, что попадает на элемент, который он ищет. Это говорит о том, что он не может быть реализован как просто foldr. Там должна быть какая-то постобработка.

Когда это происходит, общий шаблон состоит в том, что вы создаете пару значений и просто берете один из них по завершении foldr. Вероятно, это то, что вы сделали, когда вы подражали Хаттону dropWhile, хотя я не уверен, так как вы не включили код. Что-то вроде этого?

delete :: Eq a => a -> [a] -> [a]
delete a = snd . foldr (\x (xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], [])

Основная идея заключается в том, что xs1 всегда будет полным хвостом списка, а xs2 является результатом delete по хвосту списка. Поскольку вы хотите удалить только первый элемент, который соответствует, вы не хотите использовать результат delete над хвостом, когда вы соответствуете искомому значению, вы просто хотите вернуть остальную часть списка без изменений - к счастью, это то, что всегда будет в xs1.

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

delete :: Eq a => a -> [a] -> [a]
delete a = snd . foldr (\x ~(xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], [])

Это не единственный способ получить этот результат. Использование let-binding или fst и snd в качестве аксессуаров на кортеже также будет выполнять задание. Но это изменение с наименьшим различием.

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

Если вы посмотрите на эту лямбда, вы увидите, что выбранная ветка выбрана, прежде чем делать что-либо со вторым аргументом функции уменьшения. Кроме того, вы увидите, что большую часть времени функция уменьшения создает конструктор списка в обеих половинах кортежа результатов, прежде чем ему понадобится оценить второй аргумент. Поскольку эти конструкторы списков - это то, что делает это из delete, это то, что важно для потоковой передачи, если вы не позволяете этой паре мешать. И сделать совпадение шаблона на паре неопровержимым - это то, что мешает этому.

В качестве бонусного примера потоковых свойств foldr рассмотрим мой любимый пример:

dropWhileEnd :: (a -> Bool) -> [a] -> [a]
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) []

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

Ответ 3

Вот простое удаление, реализованное с помощью foldr:

delete :: (Eq a) => a -> [a] -> [a]
delete a xs = foldr (\x xs -> if x == a then (xs) else (x:xs)) [] xs