Suis-je utiliser un raisonnement solide equational sur une définition du filtre en termes de foldr?

Question

bien, ceci est la définition de la fonction de filtre à l'aide foldr:

myFilter p xs = foldr step [] xs
    where step x ys | p x       = x : ys
                    | otherwise = ys

donc par exemple disons que j'ai cette fonction:

myFilter odd [1,2,3,4]

il sera:

foldr step [] [1,2,3,4]

et ce sera

step 1 (foldr step [] [2,3,4])

et ce sera

step 1 (step 2 (foldr step [] [3,4]))

et ce sera

step 1 (step 2 (step 3 (foldr step [] [4])))

et ce sera

step 1 (step 2 (step 3 (step 4 (foldr step [] []))))

et foldr step [] [] est [] donc:

step 1 (step 2 (step 3 (step 4 [])))

maintenant, nous allons effectivement entrer dans la fonction step.
voici la définition de step dans la fonction myFilter, en haut:

step x ys | p x       = x : ys
          | otherwise = ys

aussi, je vous rappelle que p est en fait la fonction odd dans notre exemple.

bien, encore une fois, nous sommes ici:

step 1 (step 2 (step 3 (step 4 [])))

et

x = 4 dans la step plus intérieure et 4 n'est pas étrange, donc nous retourner ys, qui est []

Alors maintenant, nous obtenons ceci:

step 1 (step 2 (step 3 []))

, dans la step plus intérieure, x = 3 et 3 est impair, ce qui nous ramène x:ys, qui est 3 : [], qui est [3], et maintenant nous obtenons:

step 1 (step 2 [3])

et maintenant, dans la step intérieure, x = 2 et 2 n'est pas étrange, ce qui nous ramène ys, qui est [3], maintenant nous allons obtenir:

step 1 [3]

et maintenant, x = 1 et 1 est impair, ce qui nous ramène x : ys, qui est 1 : [3], qui est [1,3].

La fin: -.)

Ai-je raison dans tous mes mouvements?
merci beaucoup: -).

p.s. la définition de myFilter est du livre Real World Haskell , au chapitre 4.

Answer 1

Cela semble juste pour moi sur la première lecture.

La chose importante à retenir est bien que pour réaliser l'évaluation paresseuse, Haskell se penchera en fait les choses dans l'autre sens. En d'autres termes, la séquence réelle est plus comme

step 1 (step 2 (step 3 (step 4 [])))

devient

step 1 <block1>

qui devient

[1, <block1>]

alors si vous essayez de tirer l'élément suivant de cette liste, il évaluera

[1, step 2 <block2>]

qui devient

[1, <block2>]

et puis essayer d'évaluer

[1, step 3 (step 4 [])]

se transforme en

[1, step 3 <block3>]

qui devient

[1, 3, <block3>]

etc. Cela m'a pris un certain temps à comprendre. Il m'a été contraire à l'intuition que depuis foldr semble être évalué de la « intérieur », mais foldl est évalué à partir du « extérieur » qui foldr serait paresseux (ce qui est), alors que foldl est stricte. Mais si vous pensez à la façon dont je décrit en haut, il est logique (pour moi, de toute façon).

Answer 2

Juste pour développer l'ordre d'évaluation paresseuse. Fondamentalement, Haskell évalue toujours la fonction première, ne regarde pas les arguments jusqu'à ce qu'il ait à

Si le résultat de l'appel à myFilter est utilisé (par exemple imprimé), la fonction sera évaluée dans l'ordre suivant:

myFilter odd [1,2,3,4]

D'abord la fonction myFilter est évaluée:

foldr step [] [1,2,3,4]

foldr est la fonction la plus externe et s'évalue:

step 1 (foldr step [] [2,3,4])

step obtient évalué la production d'un 1, puisque 1 est impair:

1 : foldr step [] [2,3,4]

Maintenant, le premier élément de la liste des résultats est disponible et peut être utilisé par la fonction appelante. Si la fonction appelant utilise également l'évaluation des éléments suivants continue avec le foldr:

1 : step 2 (foldr step [] [3,4])

L'évaluation de step ne produit pas maintenant de nouveaux éléments, depuis le 2 est même:

1 : foldr step [] [3,4]

foldr à nouveau:

1 : step 3 (foldr step [] [4])

évaluation step produit 3:

1 : 3 : foldr step [] [4]

L'évaluation foldr;

1 : 3 : step 4 (foldr step [] [])

Et step une fois de plus:

1 : 3 : foldr step [] []

Enfin foldr évalue à une liste vide:

1 : 3 : []

Answer 3

À première vue, les étapes que vous avez prises dans votre exemple précis semblent corrects individuellement. Cependant, je voudrais souligner que les deux filter et foldr peuvent être utilement appliquées à listes infinies -. Qui devrait indiquer que l'ordre de vos étapes est incorrecte en ce qui concerne Haskell est