Know When to Fold'em

Adam Krieger, Tue 08 September 2015, Functional programming

fsharp, functional

'The Gambler' is one catchy song. I used to work with a guy who felt compelled to finish the chorus if you prompted him with the first line. This post is not about that song, nor is it about him. This post is about trying to solve an algorithm in a purely functional way, and it's about the subtle differences between reduce and fold.

Functional programming fundamentally changes the way you approach algorithm design. Most imperative approaches lead to non-atomic solutions. Examples of what I see in typical solutions:

The Challenge

Consider the lonely integer problem. Given an odd-length array of n integers, guaranteed to have only one value which doesn't have a pair, find the lonely value. Full problem listed on HackerRank.

One solution is to maintain a set of values with no pairs. As you iterate through the array, check to see if the value exists in the set. If it does, remove it from the set, and if not, add it to the set. After iterating through all of the items, the only value which wasn't removed from the set is the lonely integer.

Rather than telling the computer exactly what to do, let's declare the outcome by...

Solving it Functionally

Given the big three functional operations: Map, Filter, and Reduce, what can we do?

Reduce is the best match so far. Given [|"a"; "b"; "a"|], here is the step-by-step resolution. I used letters instead of integers for this example because it provides clarity while not changing the problem. [| |] is array syntax in F#.

Spoiler: Reduce is going to produce a bit of a messy solution, but going through the process is important.

  1. Wrap each element in an array, converting [|"a"; "b"; "a"|] to [| [|"a"|]; [|"b"|]; [|"a"|] |].
  2. Reduce [|"a"|] and [|"b"|] to [|"a"; "b"|]. The only element of [|"b"|] does not exist in [|"a"|], so the value is appended to the initial state.
  3. Reduce [|"a"; "b"|] and [|"a"|] to [|"b"|]. The only element of [|"a"|] does exist in [|"a"; "b"|], so the value is filtered out of the reduction.
  4. Solution found to be the only element after performing the reduction across the input: "b".

Here's the F# code

let toArr x = [| x |]

let valFilter (value:string[]) arr =
    Array.filter (fun x -> x <> value.[0]) arr

let valExists (value:string[]) arr =
    Array.exists (fun x -> x = value.[0]) arr

// If the value exists in the accumulator, filter it out
//  And if not, append it
let pairOff (accum:string[]) (value:string[]) =
    match (accum,value) with
    | (accum, value) when valExists value accum -> valFilter value accum
    | _ -> Array.append accum value

let size = Console.ReadLine()

let array =
    Console.ReadLine().Split ' '
    |> Array.map toArr
    |> Array.reduce pairOff

do Console.WriteLine array.[0]

As mentioned in the spoiler, I had a couple of problems with this approach.

Turning Point

When using reduce, the accumulator needs to be the same type as the elements in the collection. Fold, however, lets us use any type as the accumulator. It could be a string, a collection, or something completely different.

Same algorithm using fold instead of reduce.

let valFilter value arr =
    Array.filter (fun x -> x <> value) arr

let valExists value arr =
    Array.exists (fun x -> x = value) arr

let pairOff accum value =
    match (accum,value) with
    | (accum, value) when valExists value accum -> valFilter value accum
    | _ -> Array.append accum [| value |]

let size = Console.ReadLine()

let array =
    Console.ReadLine().Split ' '
    |> Array.fold pairOff [||]

do Console.WriteLine array.[0]

What Reduce and Fold accomplish are very similar. In this case, it turned out that Fold was better than Reduce, but don't ignore the power of reduce either. Reduce uses the first element as the initial state, but all results must be of that type. Fold allows the result to be of any type, but requires that you provide an initial state.

Reduce is more suited for

Fold is more suited for

Have you found a solution that was better solved with one or the other? Do you have a great example of a category of problem that I didn't list? Please let me know in the comments.