Правильно ли это написать функцию Foldr в 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

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

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

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

где 'f' - это функция типа

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

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

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

Answer 2

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

Answer 3

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

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

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

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 оно некоммутативно и неассоциативно (т. е. имеет значение порядок аргументов и приложений), поэтому вы можете быть уверены, что выражение вычислено правильно.Конечно, вычитание некоммутативно и неассоциативно, и вам просто не повезло.