fold – The greatest thing that ever happened to your data structure

Let’s say that you’ve been working hard on this really awesome data structure. Its fast, its space efficient, its immutable, its everything anyone could dream of in a data structure. But you only have time to implement one function for processing the data in your new miracle structure, so what would it be?

Ok, not a terribly realistic scenario, but bare with me here, there is a point to this. The answer to this question, of course, is that you would implement fold. Why you might ask? Because if you have a fold implementation then it is possible to implement just about any other function you want in terms of fold. Don’t believe me? Well, I’ll show you, and in showing you I’ll also demonstrate how finding the right abstraction in a functional language can reduce the size and complexity of your codebase in amazing ways.

Now, to get started, let’s take a look at what exactly the fold function is:

val fold:folder('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

In simple terms it iterates over the items in the structure, and applies a function to each element which in some way processes the element and returns some kind of accumulator. Ok, maybe that didn’t come through quite as simply as I would have hoped. So how about start with a pretty straight-forward example: sum.

 
let sum (list:int list)= List.fold (fun s i -> s + i) 0 list 

Here we are folding over a list of integers, but in theory the data structure could be just about anything. Each item in the list gets added to the previous total. The first item is added with the value passed in to the fold, so for items [1;2;3] we start by adding 1 to 0, then 2 to 1, then 3 to 3, the result is 6. We could even get kinda crazy with the point-free style and use the fact that the + operator is a function which takes two arguments, and returns a third…which happens to exactly match our folding function.

let sum (list:int list) = List.fold (+) 0 list

So that’s pretty cool right? Now it seem like you could also very easily create a Max function for your structure by using the built in max operator, or a Min function using the min operator.

let max (list:int list) = List.fold (max) (Int32.MinValue) list 
let min (list:int list) = List.fold (min) (Int32.MaxValue) list

But I did say that you could create any other processing function right? So how about something a little trickier, like Map? It may not be quite as obvious, but the implementation is actually equally simplistic. First let’s take a quick look at the signature of the map function to refresh our memories:

val map: mapping ('T –> 'U) –> list:'T list –> 'U list

So how do we implement that in terms of fold? Again, we’ll use List because its simple enough to see what goes on internally:

let map (mapping:'a -> 'b) (list:'a list) = List.fold (fun l i –> mapping i::l) [] list

Pretty cool right? Use the Cons operator (::) and a mapping function with an initial value of an empty list. So that’s pretty fun, how about another classic like filter? Also, pretty similar

let filter (pred:'a -> bool) (list:'a list) = List.fold (fun l i –> if pred I then i::l else l) [] list

Now we’re on a roll, so how about the choose function (like map, only returns an Option and any None value gets left out)? No problem.

let choose (chooser:'a –> 'b option) (list:'a list) = List.fold (fun l i –> match chooser i with | Some i –> i::l | _ –> l) [] list

Ok, so now how about toMap?

let toMap (list:'a*'b list) = List.fold (fun m (k,v) –> Map.add k v) Map.empty list

And collect (collapsing a list of lists into a single list)?

list collect (list:'a list list) = List.fold (fun l li –> List.fold (fun l' i' –> i'::l') l li) [] list

In this case we’re nesting a fold inside a fold, but it still works. And now, just for fun, list exists, tryFind, findIndex, etc

let exists (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i || b) false list
let tryFind (pred:'a -> bool) (list:'a list) = List.fold (fun o i -> if pred i then Some i else o) None list
let findIndex (pred:'a -> bool) (list:'a list) = List.fold (fun (idx,o) i -> if pred i then (idx + i,Some idx) else (idx + 1,o)) (-1,None) list |> snd |> Option.get
let forall (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i && b) true list
let iter (f:'a -> unit) (list:'a list) = List.fold (fun _ i -> f i) () list
let length (list:'a list) = List.fold (fun c _ -> c + 1) 0 list
let partition (pred:'a -> bool) (list:'a list) = List.fold (fun (t,f) i -> if pred i then i::t,f else t,i::f) ([],[]) list

Its worth pointing out that some of these aren’t the most efficient implementations. For example, exists, tryFind and findIndex ideally would have some short-circuit behavior so that when the item is found the list isn’t traversed any more. And then there are things like rev, sort, etc which could be built in terms of fold, I guess, but the simpler and more efficient implementations would be done using simpler recursive processing. I can’t help but find the simplicity of the fold abstraction very appealing, it makes me ever so slightly giddy (strange, I know).