Это правильный способ написания функции сворачивания на Haskell?

Question

Я выполнял упражнения из раздела Рекурсивный тип данных YAHT , и мне было сложно написать функцию listFoldr (в основном потому, что я не совсем понимал разницу между foldl и foldr вначале). Когда я наконец понял, как именно работает функция foldr, я решил, что простой обмен аргументами функции - это все, что потребуется для изменения моей функции listFoldl на функцию listFoldr:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

Это похоже на работу (я сделал больше тестов, чем это):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

Но решение , данное для упражнения, сильно отличается от моего. Их listFoldl точно такой же, как у меня, но посмотрите на их listFoldr:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

Какое решение лучше моего или их? Один из них неверный? (В моих тестах они оба заканчиваются с одинаковым результатом ...)

Answer 1

Ваше решение определенно неверно. Вы просто реализовали foldl, в котором функция f принимает аргументы в обратном порядке. Например, что неправильно, foldr (:) [] должна быть функцией идентификации в списках, но ваша функция переворачивает список. Есть много других причин, по которым ваша функция не foldr, например, как foldr работает с бесконечными списками, а ваша - нет. Это чистое совпадение, что они одинаковы в вашем примере, потому что 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). Я думаю, что вы должны начать с нуля и посмотреть, как foldr должен работать.

Answer 2

Твой сломан. Попробуйте что-нибудь, что не приведет ни к одному числовому результату.

eg: listFoldr (++) "a" ["b", "c", "d"]

Вы обрабатываете в неправильном направлении.

Answer 3

Я думаю, вы обрабатываете элементы в «обратном порядке», и поэтому ваш не прав.

Вы должны продемонстрировать это на примере, где «порядок имеет значение». Например, что-то вроде

listfoldr f "" ["a", "b", "c"]

где 'f' - функция, аналогичная

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

где '@' - оператор добавления строки (я забыл, что это в Хаскеле). Смысл в том, чтобы просто «инструментировать» функцию, чтобы вы могли видеть, в каком порядке она вызывается с различными аргументами.

(Обратите внимание, что это не отображалось в вашем примере, потому что математика "4-1-2-3" дает тот же ответ, что и "4-3-2-1".)

Answer 4

В списке [x1, x2, ..., xk] ваш listFoldr вычисляет

 f xk (... (f x2 (f x1 i)) ...)

, тогда как foldr должен вычислять

 f x1 (f x2 (... (f xk i) ...))

(Для сравнения foldl вычисляет

f (... (f (f i x1) x2) ...) xk

По существу, listFoldr f = foldl (flip f).)

Ты тестовый случай неудачный, потому что

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

Когда вы тестируете подобные функции, обязательно передайте f, который не является коммутативным и неассоциативным (т. Е. Аргумент и порядок приложения имеют значение), так что вы можете быть уверены, что выражение оценено правильно. Конечно, вычитание некоммутативно и неассоциативно, и вам просто не повезло.