Quelques explications s'imposent !
A quoi sert la fonction id ? À quoi sert la fonction id ? Pourquoi en aurions-nous besoin ici ?
id est le fonction d'identité , id x = x et est utilisé comme l'équivalent du zéro lors de la construction d'une chaîne de fonctions à l'aide de la fonction composition des fonctions , (.) . Vous pouvez le trouver défini dans le prélude .
Dans l'exemple ci-dessus, la fonction id est l'accumulateur dans la fonction lambda ?
L'accumulateur est une fonction qui se construit par l'application répétée d'une fonction. Il n'y a pas de lambda explicite, puisque nous nommons l'accumulateur, step . Vous pouvez l'écrire avec un lambda si vous le souhaitez :
foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
Ou comme Graham Hutton écrirait :
5.1 Le foldl opérateur
Maintenant, généralisons à partir de la suml exemple et considérer l'opérateur standard foldl qui traite les éléments d'une liste dans l'ordre de gauche à droite en utilisant une fonction f pour combiner des valeurs, et une valeur v comme valeur de départ :
foldl :: ( ) ([] )
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs
En utilisant cet opérateur, suml peut être redéfini simplement par suml = foldl (+) 0 . De nombreuses autres fonctions peuvent être définies de manière simple à l'aide de foldl . Par exemple, la fonction standard reverse peut être redéfini en utilisant foldl comme suit :
reverse :: [] []
reverse = foldl (xs x x : xs) [ ]
Cette définition est plus efficace que notre définition originale utilisant le pliage, car elle évite l'utilisation de l'opérateur inefficace append. (++) pour les listes.
Une simple généralisation du calcul de la section précédente pour la fonction suml montre comment redéfinir la fonction foldl en termes de fold :
foldl f v xs = fold (x g (a g (f a x))) id xs v
En revanche, il n'est pas possible de redéfinir fold en termes de foldl en raison du fait que foldl est strict dans la queue de son argument liste mais fold ne l'est pas. Il existe un certain nombre de "théorèmes de dualité" utiles concernant fold y foldl ainsi que quelques lignes directrices pour décider quel opérateur est le mieux adapté à des applications particulières (Bird, 1998).
Le prototype de foldr est foldr : : (a -> b -> b) -> b -> [a] -> b
Un programmeur Haskell dirait que l'élément type de foldr es (a -> b -> b) -> b -> [a] -> b .
et le premier paramètre est une fonction qui a besoin de deux paramètres, mais la fonction étape dans l'implémentation de myFoldl utilise 3 paramètres, je suis complètement confus.
C'est déroutant et magique ! On joue un tour et on remplace l'accumulateur par une fonction, qui est à son tour appliquée à la valeur initiale pour donner un résultat.
Graham Hutton explique le truc pour tourner foldl en foldr dans l'article ci-dessus. Nous commençons par écrire une définition récursive de foldl :
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs
Et ensuite le refactoriser via la transformation d'argument statique sur f :
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs = g xs v
where
g [] v = v
g (x:xs) v = g xs (f v x)
Réécrivons maintenant g afin de faire flotter le v vers l'intérieur :
foldl f v xs = g xs v
where
g [] = \v -> v
g (x:xs) = \v -> g xs (f v x)
Ce qui revient à penser à g comme une fonction à un argument, qui renvoie une fonction :
foldl f v xs = g xs v
where
g [] = id
g (x:xs) = \v -> g xs (f v x)
Maintenant, nous avons g une fonction qui parcourt récursivement une liste, appliquer une fonction f . La valeur finale est la fonction d'identité, et chaque étape donne également lieu à une fonction.
Mais nous avons déjà à portée de main une fonction récursive très similaire sur les listes, foldr !
2 L'opérateur de pliage
El fold a ses origines dans la théorie de la récursion (Kleene, 1952), tandis que l'utilisation de l'opérateur de fold comme concept central dans un langage de programmation remonte à l'opérateur de réduction de l'APL (Iverson, 1962), et plus tard à l'opérateur d'insertion du FP (Backus, 1978). En Haskell, l'opérateur fold pour les listes peut être défini comme suit :
fold :: ( ) ([] )
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)
C'est-à-dire qu'étant donné une fonction f de type et une valeur v de type la fonction fold f v traite une liste de type [] pour donner une valeur de type en remplaçant le constructeur nil [] à la fin de la liste par la valeur v et chaque constructeur de cons (:) dans la liste par la fonction f . De cette manière, le fold encapsule un modèle simple de récursion pour le traitement des listes, dans lequel les deux constructeurs de listes sont simplement remplacés par d'autres valeurs et fonctions. Un certain nombre de fonctions familières sur les listes ont une définition simple utilisant l'opérateur fold .
Cela ressemble à un schéma récursif très similaire à celui de notre g fonction. Maintenant, l'astuce : en utilisant toute la magie disponible (aka Bird, Meertens et Malcolm), nous appliquons une règle spéciale, le propriété universelle du pli qui est une équivalence entre deux dénitions pour une fonction g qui traite des listes, énoncées comme :
g [] = v
g (x:xs) = f x (g xs)
si et seulement si
g = fold f v
Donc, la propriété universelle des plis stipule que :
g = foldr k v
où g doit être équivalente aux deux équations, pour certaines k y v :
g [] = v
g (x:xs) = k x (g xs)
D'après nos conceptions précédentes de foldl, nous savons v == id . Pour la deuxième équation cependant, nous avons besoin de calculer la définition de k :
g (x:xs) = k x (g xs)
<=> g (x:xs) v = k x (g xs) v -- accumulator of functions
<=> g xs (f v x) = k x (g xs) v -- definition of foldl
<= g' (f v x) = k x g' v -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x)) -- expand k. recursion captured in g'
Ce qui, en substituant nos définitions calculées de k y v donne une définition de foldl comme :
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs =
foldr
(\x g -> (\a -> g (f v x)))
id
xs
v
La récursive g est remplacé par le combinateur foldr, et l'accumulateur devient une fonction construite via une chaîne de compositions de f à chaque élément de la liste, dans l'ordre inverse (on plie donc à gauche au lieu de droite).
C'est certainement un peu avancé, donc pour comprendre en profondeur cette transformation, les propriété universelle des plis Je recommande le tutoriel de Hutton, dont le lien figure ci-dessous.
Références
2 votes
Pour les vrais masochistes,
step = curry $ uncurry (&) <<< (flip f) *** (.)