InquiryLabs
Politics, Programming and Possibilities
Using “foldr” in Haskell
Author: Duane Johnson17 Jul
I’ve been reading Real World Haskell lately in order to get a better grasp on Haskell and functional programming. It’s a book I’d highly recommend—especially when it’s done!
One of the fundamental building-blocks of Haskell is the foldr method which, I am told, is called a “primitive recursive” function because it is capable of building any function in a set of useful recursive functions (e.g. foldl, map, filter, etc.) This is really important to me, because I had always liked foldl before, which seemed more intuitive (i.e. it iterates through a list from left to right, which is my natural way of thinking of lists). Anyway, it turns out that foldr can be used to build foldl, but not vice-versa, which proves foldr is more “primitive”.
One of the exercises in the Real World Haskell book is to create the concat function which takes a list of lists and turns them into one list. I spent about an hour trying various recursive tricks last night, and realized that this is a double-recursive problem—you need an append function available before you can recursively join a list of indefinite length.
What really delighted me in the end was that both the append and the concat functions can be very easily defined in terms of “foldr”:
myAppend a b = foldr (:) b a
myConcat = foldr myAppend []
In the first definition, myAppend is using foldr to replace the last (empty) element of the list with “b” (the list to be appended) and then consing each element in a onto the front of that list.
In the second definition, myConcat is using foldr to start with an empty list and then append prepend each element of the outer list with a previous element of that list (i.e. the parameter passed to myConcat is expected to be a list of lists).
Since myAppend is just the concatenation of two lists, it is exactly the same as the (++) operator in Haskell. So, the concat function can concisely be defined as:
myConcat = foldr (++) []
This code makes use of currying, which means that I’m defining a function that uses another function with incomplete parameters (in this case, I’ve only passed two parameters to foldr when three are normally required). The first function expects an anonymous parameter (i.e. the list of lists) which will get passed into foldr, thus completing the foldr function.
Update: I just found an even more concise way to define concat (assuming ++ is not available), thanks to the help on #haskell:
myConcat = foldr (flip (foldr (:))) []
That’s one reason Haskell is “precision engineering for programmers” 
PhotoStream
-
flickrRSS probably needs to be setup
3 Responses for "Using “foldr” in Haskell"
I think when you say “currying,” you really mean “partial application”. Currying (which I associate with brushing down a horse), is where you have a function that takes, say, a pair of arguments (p,q), and “changes” it into a function that takes one argument, p, and gives back another function that takes the second argument, q, as an argument, and that function gives the same answer that just giving (p,q) to the original function gave. Partial application is where you take that other function (not the “changed” one, but the resulting function you get from giving p to the “changed” one), and use that function as a separate function in its own right (which, well, it is, it just isn’t emphasized as such usually).
The point is, especially in “imperative” language use, you can’t do partial application “on the fly” - you have to deliberately define a new function, with separate arguments, that calls the original function in its body. Another point is, that the arguments of a function aren’t thought of as being a tuple (a pair, triple, quadruple, or whatever); the argument list is just a convenient way to show that those particular arguments are the ones being given to the function. Functions aren’t thought of as being given a single, “tuple” argument; they’re thought of as having multiple arguments, with a syntax that specifies those arguments which go to the function.
It helps if you have a language that facilitates returning a function as a result, as well as functions that accept other functions as arguments.
Oh sorry for making another entry, but a help to see why/how your update works is to note the use of the function “flip.” Here’s the Haskell-style type signature (what you’d call a “function declaration” in C or Java, except in Haskell, they’re almost always optional)
flip :: (a -> b -> c) -> b -> a -> c
In short: what “flip” does, is take a two-argument function (more-or-less; there are points to make on whether “two-argument function” even makes sense - I’ll assume you get my meaning), and gives back a two-argument function, just with the order of the arguments switched. So, look back at your original MyAppend:
myAppend a b = foldr (:) b a
You could, using that whole “partial application” thing, call the “foldr (:)” part a function in its own right (since it is), and use flip on it to flip the arguments back around:
myAppend a b = flip (foldr (:)) a b
Even better: you can see now, that the arguments (a b) are given to the functions in the same order - so that means they’re the same function! In the world of Lambda Calculus, it’s called “eta reduction,” but I like to think of it as transitivity on functions. Or to put it into regular talk, “two things equal to the same thing are equal to each other,” once more taking liberties with the language - please don’t hurt me, Math Gods!
So, we can just drop the arguments out of the picture and write:
myAppend = flip (foldr (:))
and Haskell accepts that as a perfectly valid definition for a function! Of course, we still have to remember that it needs two arguments given to it, to give an answer (useful to us, anyway), but that’s our problem.
So, to quote your quote, that’s another reason Haskell is “precision engineering for programmers”
Thanks chaps for that. I’m working my way through the YAHT pdf (Yet Another Haskell Tutorial) and the explanation of currying and parital application has cleared it up somewhat.
Leave a reply