Some explanation is ok!
What is the id function for? What is the role? Why do we need it here?
id is an identical function , id x = x and is used as the equivalent of zero when constructing a chain of functions with the composition of functions (.) . You can find it in the prelude .
In the above example, is the id function an accumulator in the lambda function?
Battery is a feature that is created through multiple applications. There is no explicit lambda, as we call the battery, step . You can write it with lambda if you want:
foldl fa bs = foldr (\bgx -> g (fxb)) id bs a
Or, as Graham Hatton wrote :
5.1 foldl operator
Now let's suml example and consider the standard foldl operator that processes list items in order from left to right, using the f function to combine the values, and the v value as the initial value:
foldl :: (β → α → β) → β → ([α] → β) foldl fv [ ] = v foldl fv (x : xs) = foldl f (fvx) xs
Using this operator, suml can be overridden simply by suml = foldl (+) 0 . Many other functions can be defined in a simple way with foldl . For example, the standard reverse function can be overridden with foldl as follows:
reverse :: [α] → [α] reverse = foldl (λxs x → x : xs) [ ]
This definition is more efficient than our original definition using fold, as it avoids the use of the inefficient append (++) operator for lists.
A simple generalization of the calculation in the previous section for the suml function shows how to override the foldl function in terms of fold :
foldl fv xs = fold (λx g → (λa → g (fax))) id xs v
In contrast, it is not possible to redefine fold in terms of foldl , because foldl is strict at the tail of the list argument, but fold is not. There are a number of useful “duality theorems” regarding fold and foldl , as well as some recommendations for determining which operator is best for specific applications (Bird, 1998).
foldr - foldr :: (a → b → b) → b → [a]
A Haskell programmer would say that the type of foldr is (a → b → b) → b → [a] → b .
and the first parameter is a function that needs two parameters, but the step function in the implementation of myFoldl uses 3 parameters, I'm completely confused
This is confusing and magical! We play the trick and replace the battery with a function that, in turn, applies to the original value to get the result.
Graham Hatton explains the trick to turn foldl into foldr in the above article. Let's start by writing the recursive definition of foldl :
foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv [] = v foldl fv (x : xs) = foldl f (fvx) xs
And then reformat it by converting the static argument to f :
foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv xs = g xs v where g [] v = v g (x:xs) v = g xs (fvx)
Now rewrite g to swim v inward:
foldl fv xs = g xs v where g [] = \v -> v g (x:xs) = \v -> g xs (fvx)
This is the same as thinking of g as a function of a single argument, which returns a function:
foldl fv xs = g xs v where g [] = id g (x:xs) = \v -> g xs (fvx)
Now we have g , a function that recursively scans the list, applies some function f . The final value is an identification function, and each step also leads to a function.
But, we already have a very similar recursive function in lists, foldr !
2 Bend Operator
The fold operator is based on the theory of recursion (Kleene, 1952), while the use of fold as a central concept in a programming language goes back to the APL abbreviation operator (Iverson, 1962) and then to the FP insertion operator (Backus, 1978). In Haskell, the fold operator for lists can be defined as follows:
fold :: (α → β → β) → β → ([α] → β) fold fv [ ] = v fold fv (x : xs) = fx (fold fv xs)
That is, given the function f type α → β → β and the value of v type β , the function fold fv processes a list of type [α] to give a value of type β , replacing the constructor nil [] with the end of the list by value v and each constructor cons (:) in the list by f . Thus, the fold operator encapsulates a simple recursion pattern for processing lists, in which two constructors for lists are simply replaced with other values and functions. A number of familiar functions in lists have a simple definition using fold .
This is similar to a very similar recursive scheme of our g function. Now the trick: using all the available magic at hand (just like Bird, Meertens and Malcolm), we apply a special rule, the universal property fold , which is the equivalent of two definitions for the function g that processes lists, like:
g [] = v g (x:xs) = fx (g xs)
if and only if
g = fold fv
So, the universal property of folds states that:
g = foldr kv
where g should be equivalent to two equations, for some k and v :
g [] = v g (x:xs) = kx (g xs)
From our early foldl constructs, we know v == id . However, for the second equation, we need to calculate the definition of k :
g (x:xs) = kx (g xs) <=> g (x:xs) v = kx (g xs) v -- accumulator of functions <=> g xs (fvx) = kx (g xs) v -- definition of foldl <= g' (fvx) = kxg' v -- generalize (g xs) to g' <=> k = \xg' -> (\a -> g' (fvx)) -- expand k. recursion captured in g'
Which, replacing our calculated definitions of k and v gives the definition of foldl as:
foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv xs = foldr (\xg -> (\a -> g (fvx))) id xs v
The recursive g is replaced by the foldr combinator, and the accumulator becomes a function constructed by the composition chain f for each element of the list, in the reverse order (therefore, we add the left rather than the right).
This is definitely somewhat advanced, therefore, to deeply understand this transformation, the universal property of folds that makes the transformation possible, I recommend the Hatton tutorial below.
Recommendations