Как работает складной склад?

Question

Может ли кто-нибудь объяснить, как работает foldl?
Я понял, что, например, foldr (-) 0 [1,2,3] производит (1 - (2 - (3 - 0))), тогда как foldl (-) 0 [1,2,3] производит (((0 - 1) - 2) - 3), но у меня есть еще несколько вопросов:

• первым примером (длина списка с foldr/foldl):
  foldr (\_ acc -> acc + 1) 0 [1,2,3,4,5] производит 5, как ожидалось.
  foldl (\_ acc -> acc + 1) 0 [1,2,3,4,5] производит 6.: |
  foldl (\_ acc -> acc + 1) 0 [2] производит 3.: |
  Как реагировать на эти приведенные примеры?

• второй пример:
  foldr (:) [] [1,2,3,4] производит [1,2,3,4] - не переживайте, но foldl (:) [] [1,2,3,4] дает мне ошибку: Occurs check: cannot construct the infinite type: a ~ [a]
  Что случилось с foldl?

Answer 1

В foldr, аккумулятор является вторым аргументом функции вы складной с, но в foldl, аккумулятор является первым аргументом. Если вы внимательно посмотрите на вводный параграф вопроса, вы можете это решить самостоятельно ...

Код «1-й пример» вводит в заблуждение, поскольку аргумент acc (название которого предполагает, что он должен быть аккумулятором) является последовательно второй аргумент лямбда, когда он должен быть первым для foldl. Это также запутывает, потому что тип и значения элементов списка образцов отражают тип и значение значения аккумулятора ... как отмечают комментарии, было бы лучше использовать другие значения и еще лучше использовать какой-либо другой тип!

Для «второго примера» вы получаете ошибку типа, потому что ваши аргументы меняются местами (и вы не можете иметь список, элементы которого являются списками самого себя). Либо поменять порядок аргументов вручную:

foldl (\xs x -> x:xs) 

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

foldl (flip (:)) 

Обратите внимание, что результат для foldl случае должен быть перевернутым список (а не скопирован один), потому что foldl выполняет итерацию в противоположном направлении от foldr.