Using F# fold function to implement recursion

In the last post, we talked about techniques to implement tail-recursion in F#. We also learned that to write pure functional code we can only use immutable data structures which means we have to implement loop using recursion.

Writing recursive function can be cumbersome (e.g., the function has to have one or more base cases) and hard to understand. It’s also harder to make sure that your recursive function is a tail-recursive one.

Fortunately, using higher-order function and data structure like list (which is a recursive data structure) can help easing the pain.

Let’s look at our non-tail-recursive factorial function from last post again.

let rec factorial x =
    if x <= 1 then
        1
    else 
        x * factorial (x - 1)

Since the function basically multiplies numbers (e.g., x, x-1, x-2, …) together, we can actually think of the input as a list of numbers like [5,4,3,2,1] instead.

With that in mind, we can now implement factorial function using List functions like List.fold.

Here is the List.fold signature:

(‘State -> ‘T -> ‘State) -> ‘State -> ‘T list –> ‘State

List.fold is a higher-order function that takes the following parameters:

(‘State –> ‘T –> ‘State)

A function that takes ‘State which we can think of it as an accumulator, ‘T which in this case is each value in the list, and returns new accumulator.

‘State

An initial state of an accumulator.

‘T list

The input list

The last ‘State is the final out put that we want.

Now, let’s see how we can implement our factorial function with only one line of code :-).

let foldFactorial x = [1..x] |> List.fold (fun acc i -> acc * i) 1

The most important part is the lambda expression, (fun acc i -> acc * i), that we pass to the fold function. The acc parameter in the lambda expression is the accumulated result like the acc parameter in accTailRecursiveFactorial recursive function from the last post.

let accFactorial x =
    let rec accTailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            accTailRecursiveFactorial (x - 1) (acc * x)

    accTailRecursiveFactorial x 1

Using fold also gives us tail recursive function. Here is the IL generated by foldFactorial function.

image

(NOTE: some lines have been cut to make the screenshot fit the page)

If you are curious, below is what List.fold looks like (NOTE: The code below is from list.fs in F# compiler and code library on GitHub). You probably notice that it has the nested recursive function that is tail-recursive!

[<CompiledName("Fold")>]
let fold<'T,'State> f (s:'State) (list: 'T list) = 
	match list with 
    | [] -> s
    | _ -> 
		let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
        let rec loop s xs = 
			match xs with 
            | [] -> s
            | h::t -> loop (f.Invoke(s,h)) t
		loop s list

And as a bonus, you can even make the factorial code shorter by using operator (*) which is actually a normal function in F#.

let foldFactorial2 x =  [1..x] |> List.fold (*) 1

Better yet, the code can be made shorter by using List.reduce which is a specialized version of fold that treat the first input on the list as accumulator.

let reduceFactorial x = [1..x] |> List.reduce (*)

This post shows how tail-recursive code could be implemented using List.fold and List.reduce. Since implementing recursive algorithm is important in functional programming, using built-in F# function like fold and reduce really reduces (no pun-intended 🙂 ) our work.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s