Est-ce une bonne façon d'écrire la fonction foldr Haskell?
-
22-08-2019 - |
Question
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 ...)
La solution
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 ».)
Autres conseils
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.
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.
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.