Почему вы можете перевернуть список с помощью foldl, но не с помощью foldr в Haskell

Во-первых, сигнатуры типов не совпадают:

foldl :: (o -> i -> o) -> o -> [i] -> o
foldr :: (i -> o -> o) -> o -> [i] -> o

Итак, если вы поменяете имена аргументов:

reverse' xs = foldr (\ x acc -> x : acc) [] xs

Теперь он компилируется. Он не работает, но сейчас компилируется.

Дело в том, что foldl работает слева направо (т.е. назад), тогда как foldr работает справа налево (т.е. вперед). Вот почему foldl позволяет перевернуть список; он передает вам вещи в обратном порядке.

Сказав все это, вы можете сделать

reverse' xs = foldr (\ x acc -> acc ++ [x]) [] xs

Однако это будет очень медленно. (Квадратичная сложность, а не линейная сложность.)

Каждый foldl является foldr.

Давайте вспомним определения.

foldr :: (a -> s -> s) -> s -> [a] -> s
foldr f s []       = s
foldr f s (a : as) = f a (foldr f s as)

Это стандартный одношаговый итератор для списков. Раньше я заставлял своих студентов стучать по столу и скандировать «Что вы делаете с пустым списком? Что вы делаете с a : as»? И вот как вы понимаете, что такое s и f соответственно.

Если вы задумаетесь о том, что происходит, вы увидите, что foldr эффективно вычисляет большую композицию из f a функций, а затем применяет эту композицию к s.

foldr f s [1, 2, 3]
= f 1 . f 2 . f 3 . id $ s

Теперь давайте проверим foldl

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t []       = t
foldl g t (a : as) = foldl g (g t a) as

Это тоже одношаговая итерация по списку, но с аккумулятором, который меняется по мере продвижения. Давайте переместим его в последнюю очередь, чтобы все слева от аргумента списка осталось прежним.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) []       t = t
flip (foldl g) (a : as) t = flip (foldl g) as (g t a)

Теперь мы можем увидеть одношаговую итерацию, если переместим = на одну позицию влево.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) []       = \ t -> t
flip (foldl g) (a : as) = \ t -> flip (foldl g) as (g t a)

В каждом случае мы вычисляем что бы мы сделали, если бы знали аккумулятор, абстрагируясь с помощью \ t ->. Для [] мы бы вернули t. Для a : as мы будем обрабатывать хвост с g t a в качестве аккумулятора.

Но теперь мы можем преобразовать flip (foldl g) в foldr. Абстрагируйте рекурсивный вызов.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) []       = \ t -> t
flip (foldl g) (a : as) = \ t -> s (g t a)
  where s = flip (foldl g) as

И теперь мы готовы превратить его в foldr, где тип s создается с помощью t -> t.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) = foldr (\ a s -> \ t -> s (g t a)) (\ t -> t)

Итак, s говорит "что as будет делать с аккумулятором", а мы возвращаем \ t -> s (g t a), то есть "что a : as делает с аккумулятором". Перевернуть назад.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g = flip (foldr (\ a s -> \ t -> s (g t a)) (\ t -> t))

Эта-расширить.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = flip (foldr (\ a s -> \ t -> s (g t a)) (\ t -> t)) t as

Уменьшите flip.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = foldr (\ a s -> \ t -> s (g t a)) (\ t -> t) as t

Таким образом, мы вычисляем, «что бы мы сделали, если бы знали аккумулятор», а затем скармливаем ему исходный аккумулятор.

Немного поучительно играть в гольф. Мы можем избавиться от \ t ->.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = foldr (\ a s -> s . (`g` a)) id as t

Теперь позвольте мне изменить эту композицию, используя >>> из Control.Arrow.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = foldr (\ a s -> (`g` a) >>> s) id as t

То есть foldl вычисляет большую обратную композицию. Так, например, учитывая [1,2,3], мы получаем

foldr (\ a s -> (`g` a) >>> s) id [1,2,3] t
= ((`g` 1) >>> (`g` 2) >>> (`g` 3) >>> id) t

где «конвейер» подает свой аргумент слева, поэтому мы получаем

((`g` 1) >>> (`g` 2) >>> (`g` 3) >>> id) t
= ((`g` 2) >>> (`g` 3) >>> id) (g t 1)
= ((`g` 3) >>> id) (g (g t 1) 2)
= id (g (g (g t 1) 2) 3)
= g (g (g t 1) 2) 3

и если вы возьмете g = flip (:) и t = [] вы получите

flip (:) (flip (:) (flip (:) [] 1) 2) 3
= flip (:) (flip (:) (1 : []) 2) 3
= flip (:) (2 : 1 : []) 3
= 3 : 2 : 1 : []
= [3, 2, 1]

То есть,

reverse as = foldr (\ a s -> (a :) >>> s) id as []

выполнив общее преобразование foldl в foldr.

Только для математиков. Выполните cabal install newtype и импортируйте Data.Monoid, Data.Foldable и Control.Newtype. Добавьте трагически пропавший экземпляр:

instance Newtype (Dual o) o where
  pack = Dual
  unpack = getDual

Заметьте, что, с одной стороны, мы можем реализовать foldMap с помощью foldr

foldMap :: Monoid x => (a -> x) -> [a] -> x
foldMap f = foldr (mappend . f) mempty

но и наоборот

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f = flip (ala' Endo foldMap f)

так что foldr накапливается в моноиде составных эндофункций, но теперь, чтобы получить foldl, мы говорим foldMap работать в моноиде Dual.

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl g = flip (ala' Endo (ala' Dual foldMap) (flip g))

Что такое mappend для Dual (Endo b)? Обтекание по модулю, это точно обратная композиция, >>>.

Вы можете использовать foldr для эффективного обращения списка (ну, большую часть времени в GHC 7.9 — это зависит от некоторых оптимизаций компилятора), но это немного странно:

reverse xs = foldr (\x k -> \acc -> k (x:acc)) id xs []

Я написал объяснение того, как это работает в Haskell Wiki.

foldr в основном деконструирует список каноническим способом: foldr f initial это то же самое, что и функция с шаблонами:^{(это в основном определение папки)}

 ff [] = initial
 ff (x:xs) = f x $ ff xs

т. е. он отменяет элементы один за другим и передает их в f. Что ж, если все, что делает f, — это обратно их обратно, то вы получаете список, который у вас был изначально! (Другой способ сказать это: foldr (:) [] ≡ id.

foldl "деконструирует" список в обратном порядке, поэтому, если вы вернете элементы назад, вы получите обратный список. Чтобы получить тот же результат с foldr, вам нужно добавить к «неправильному» концу — либо как показал MathematicalOrchid, неэффективно с ++, либо с помощью списка различий:

reverse'' :: [a] -> [a]
reverse'' l = dl2list $ foldr (\x accDL -> accDL ++. (x:)) empty l

type DList a = [a]->[a]
(++.) :: DList a -> DList a -> DList a
(++.) = (.)
emptyDL :: DList a
emptyDL = id
dl2list :: DLList a -> [a]
dl2list = ($[])

Что можно компактно записать как

reverse''' l = foldr (flip(.) . (:)) id l []

Вот что foldl op acc делает со списком, скажем, из 6 элементов:

(((((acc `op` x1) `op` x2) `op` x3) `op` x4) `op` x5 ) `op` x6

в то время как foldr op acc делает это:

x1 `op` (x2 `op` (x3 `op` (x4 `op` (x5 `op` (x6 `op` acc)))))

Когда вы посмотрите на это, станет ясно, что если вы хотите, чтобы foldl перевернул список, op должен быть оператором "прикрепить правый операнд к началу левого операнда". Это просто (:) с перевернутыми аргументами, т.е.

reverse' = foldl (flip (:)) []

(это то же самое, что и ваша версия, но с использованием встроенных функций).

Если вы хотите, чтобы foldr перевернул список, вам нужен оператор "прикрепить левый операнд к концу правого операнда". Я не знаю встроенной функции, которая делает это; если вы хотите, вы можете написать это как flip (++) . return.

reverse'' = foldr (flip (++) . return) []

или если вы предпочитаете написать это самостоятельно

reverse'' = foldr (\x acc -> acc ++ [x]) []

Хотя это было бы медленно.

Небольшое, но важное обобщение некоторых из этих ответов заключается в том, что вы можете реализовать foldl с foldr, что, я думаю, является более четким способом объяснить, что в них происходит:

myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr step []
    where step a bs = f a : bs

-- To fold from the left, we:
--
-- 1. Map each list element to an *endomorphism* (a function from one
--    type to itself; in this case, the type is `b`);
--
-- 2. Take the "flipped" (left-to-right) composition of these
--    functions;
--
-- 3. Apply the resulting function to the `z` argument.
--
myfoldl :: (b -> a -> b) -> b -> [a] -> b
myfoldl f z as = foldr (flip (.)) id (toEndos f as) z
    where
      toEndos :: (b -> a -> b) -> [a] -> [b -> b]
      toEndos f = myMap (flip f)

myReverse :: [a] -> [a]
myReverse = myfoldl (flip (:)) []

Для более подробного объяснения представленных здесь идей я бы рекомендовал прочитать книгу Тома Эллиса "Из чего состоит foldr?" и "foldr состоит из моноидов".