Est-ce une bonne façon d'écrire la fonction foldr Haskell?

Question

Je faisais les exercices de section de récursive de Yaht type de données, et a trouvé l'écriture de la fonction un peu difficile listFoldr (principalement parce que je ne comprenais pas vraiment la différence entre et foldl au premier foldr). Quand je me suis finalement rendu compte exactement comment la fonction a travaillé listFoldl, j'ai décidé qu'un simple échange d'arguments de la fonction serait tout ce qui serait nécessaire pour modifier ma fonction à une <=> fonction <=>:

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

Cela semble fonctionner (je l'ai fait plus d'essais que cela):

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

Mais les donnée pour l'exercice est beaucoup différente de la mienne. Leur est exactement la <=> même que le mien, mais regardez leur <=>:

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

Quelle est la solution meilleure, la mienne ou la leur? Est-ce un d'eux incorrect? (Dans mes tests, ils finissent à la fois avec le même résultat exact ...)

Answer 1

Je pense que vous traitez les éléments dans le « ordre inverse », et si le vôtre est pas juste.

Vous devriez être en mesure de le démontrer avec un exemple où « les questions d'ordre ». Par exemple, quelque chose comme

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

où « f » est une fonction dans le sens de

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

où '@' est un opérateur string-append (j'oublie ce qu'il est en Haskell). Le point est juste « instrument » la fonction afin que vous puissiez voir quel ordre il est appelé avec les différents args.

(Notez que cela ne figure pas dans votre exemple parce que le calcul « 4-1-2-3 » donne la même réponse que « 4-3-2-1 ».)

Answer 2

Votre solution est certainement incorrecte. Vous avez tout simplement mis en place un dans lequel la foldl fonction prend des arguments dans f l'ordre inverse. Par exemple de ce qui est mal, est censé foldr (:) [] être une fonction d'identification sur les listes, mais votre fonction inverse la liste. Il y a beaucoup d'autres raisons pour lesquelles votre fonction n'est pas foldr, comme la façon dont fonctionne sur les listes 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)) infinies et le vôtre ne fonctionne pas. C'est une pure coïncidence que ce sont les mêmes dans votre exemple, parce que <=>. Je pense que vous devriez commencer à partir de zéro et de regarder comment est censé <=> travailler.

Answer 3

vôtre est cassé. Essayez avec quelque chose qui ne se termine pas avec un seul résultat numérique.

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

Vous traitez dans la mauvaise direction.

Answer 4

Sur une liste [x1, x2, ..., xk], votre listFoldr calcule

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

alors que doit calculer foldr

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

(En comparaison, calcule foldl

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

Pour l'essentiel, listFoldr f = foldl (flip f)).

Vous êtes cas de test est regrettable, parce que

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

Lorsque vous testez des fonctions comme celles-ci, assurez-vous de passer dans un f qui est non-commutative et non associatif (à savoir, la matière d'arguments et de l'ordre d'application), de sorte que vous pouvez être sûr que l'expression est évaluée correctement. Bien sûr, la soustraction est non commutative et non associatif et vous venez a la malchance.