Comprendre différentes statments FOLDR

Question

Je comprends des déclarations de FOLDR simples comme

foldr (+) 0 [1,2,3] 

Cependant, je vais avoir du mal avec les déclarations de FOLDR plus complexes, à savoir ceux qui prennent 2 paramètres dans la fonction, et avec/et - les calculs. Quelqu'un pourrait-il expliquer les étapes qui se produisent pour obtenir ces réponses?

foldr (\x y -> (x+y)*2) 2 [1,3] = 22 

foldr (/) 2 [8,12,24,4] = 8.0 

Merci.

Answer 1

La fonction foldr est définie comme suit:

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr _ a []  = a 
foldr f a (x:xs) = f x (foldr f a xs) 

Considérons maintenant l'expression suivante:

foldr (\x y -> (x + y) * 2) 2 [1,3] 

Nous allons donner le lambda un nom:

f x y = (x + y) * 2 

Par conséquent:

foldr f 2 [1,3] 
-- is 
f 1 (foldr f 2 [3]) 
-- is 
f 1 (f 3 (foldr f 2 [])) 
-- is 
f 1 (f 3 2) 
-- is 
f 1 10 
-- is 
22 

De même:

foldr (/) 2 [8,12,24,4] 
-- is 
8/(foldr (/) 2 [12,24,4]) 
-- is 
8/(12/(foldr (/) 2 [24,4])) 
-- is 
8/(12/(24/(foldr (/) 2 [4]))) 
-- is 
8/(12/(24/(4/(foldr (/) 2 [])))) 
-- is 
8/(12/(24/(4/2))) 
-- is 
8/(12/(24/2.0)) 
-- is 
8/(12/12.0) 
-- is 
8/1.0 
-- is 
8.0 

Espoir qui a aidé.

Answer 2

L'argument de fonction d'un repli prend toujours deux arguments. (+) et (/) sont des fonctions binaires comme celle de votre second exemple.

Prelude> :t (+) 
(+) :: Num a => a -> a -> a 

Si on reformule le second exemple que

foldr f 2 [1,3] 
    where 
    f x y = (x+y)*2 

nous pouvons étendre le droit fois en utilisant exactement le même schéma que nous utiliserions pour (+):

foldr f 2 [1,3] 
foldr f 2 (1 : 3 : []) 
1 `f` foldr f 2 (3 : []) 
1 `f` (3 `f` foldr f 2 []) 
1 `f` (3 `f` 2) 
1 `f` 10 
22 

Il est intéressant de noter que foldr est associatif à droite, ce qui montre comment nichent les parenthèses. Inversement, foldl, et son cousin utile foldl', sont à gauche associative.

Answer 3

Vous pouvez penser foldr, maybe et either comme des fonctions qui remplacent les constructeurs de données de leurs types respectifs avec des fonctions et/ou des valeurs de votre choix:

data Maybe a = Nothing | Just a 

maybe :: b -> (a -> b) -> Maybe a -> b 
maybe nothing _just Nothing = nothing 
maybe _nothing just (Just a) = just a 

data Either a b = Left a | Right b 

either :: (a -> c) -> (b -> c) -> Either a b -> c 
either left _right (Left a) = left a 
either _left right (Right b) = right b 

data List a = Cons a (List a) | Empty 

foldr :: (a -> b -> b) -> b -> List a -> b 
foldr cons empty = loop 
    where loop (Cons a as) = cons a (loop as) 
     loop Empty  = empty 

Donc, en général, vous ne Il faut vraiment penser à la récursion impliquée, il suffit de penser à remplacer les constructeurs de données:

foldr f nil (1 : (2 : (3 : []))) == (1 `f` (2 `f` (3 `f` nil)))