Learn You a Haskell for Great Good! - Miran Lipovaca [33]
flip' :: (a -> b -> c) -> b -> a -> c
flip' f = \x y -> f y x
Even though this is the same as writing flip' f x y = f y x, our new notation makes it obvious that this will often be used for producing a new function. The most common use case with flip is calling it with just the function parameter, or the function parameter and one extra parameter, and then passing the resulting function on to a map or a zipWith:
ghci> zipWith (flip (++)) ["love you", "love me"] ["i ", "you "]
["i love you","you love me"]
ghci> map (flip subtract 20) [1,2,3,4]
[19,18,17,16]
You can use lambdas this way in your own functions when you want to make it explicit that your functions are meant to be partially applied and then passed on to other functions as a parameter.
I Fold You So
Back when we were dealing with recursion in Chapter 4, many of the recursive functions that operated on lists followed the same pattern. We had a base case for the empty list, we introduced the x:xs pattern, and then we performed some action involving a single element and the rest of the list. It turns out this is a very common pattern, so the creators of Haskell introduced some useful functions, called folds, to encapsulate it. Folds allow you to reduce a data structure (like a list) to a single value.
Folds can be used to implement any function where you traverse a list once, element by element, and then return something based on that. Whenever you want to traverse a list to return something, chances are you want a fold.
A fold takes a binary function (one that takes two parameters, such as + or div), a starting value (often called the accumulator), and a list to fold up.
Lists can be folded up from the left or from the right. The fold function calls the given binary function, using the accumulator and the first (or last) element of the list as parameters. The resulting value is the new accumulator. Then the fold function calls the binary function again with the new accumulator and the new first (or last) element of the list, resulting in another new accumulator. This repeats until the function has traversed the entire list and reduced it down to a single accumulator value.
Left Folds with foldl
First, let’s look at the foldl function. This is called a left fold, since it folds the list up from the left side. In this case, the binary function is applied between the starting accumulator and the head of the list. That produces a new accumulator value, and the binary function is called with that value and the next element, and so on.
Let’s implement the sum function again, this time using a fold instead of explicit recursion:
sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs
Now we can test it:
ghci> sum' [3,5,2,1]
11
Let’s take an in-depth look at how this fold happens. \acc x -> acc + x is the binary function. 0 is the starting value, and xs is the list to be folded up. First, 0 and 3 are passed to the binary function as the acc and x parameters, respectively. In this case, the binary function is simply an addition, so the two values are added, which produces 3 as the new accumulator value. Next, 3 and the next list value (5) are passed to the binary function, and they are added together to produce 8 as the new accumulator value. In the same way, 8 and 2 are added together to produce 10, and then 10 and 1 are added together to produce the final value of 11. Congratulations, you’ve folded your first list!
The diagram on the left illustrates how a fold happens, step by step. The number that’s on the left side of the + is the accumulator value. You can see how the list is consumed up from the left side by the accumulator. (Om nom nom nom!) If we take into account that functions are curried, we can write this implementation even more succinctly, like so:
sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0
The lambda function (\acc x -> acc + x) is the same as (+). We can omit the xs as the parameter because calling