Map Reduce Example in F#

A while back I blogged about the canonical map reduce example (as seen in the Hadoop user manual) of counting words. Today I noticed that an alias for F#'s List.fold function is List.reduce*. I had already seen List.map, so I put two and two together, and pretty soon I had a tiny program up and running in F# Interactive. Enjoy:

/// maps an input into a tuple of input and count
let mapper x =
    (x, 1)

/// reduces a list of input and count tuples, summing the counts
let reducer (a:(string * int) list) (x:string * int) =
    if List.length a > 0 && fst (List.head a) = fst x then
        (fst (List.head a), snd (List.head a) + snd x)::List.tail a
    else
        x::a            

/// maps the mapper function over a list of input
let map xs =
    List.map (mapper) xs

/// maps the reducer function over a list of input and count tuples
let reduce (xs:(string * int) list) = 
    List.fold (reducer) [] xs

/// maps the input, sorts the intermediate data, and reduces the results
let mapReduce xs = 
    map xs
    |> List.sort
    |> reduce

It turns out the functional programming appears to be made for this pattern!

FaultException<T>

If you're stuck trying to get WCF to play nicely with a FaultException<T> where T is a custom System.Exception-derived type, you may be interested to know that the exception needs to have this protected constructor in order to work as expected:

[Serializable]
public class NotFoundException : ApplicationException {
    public NotFoundException() {
    }

    protected NotFoundException(SerializationInfo info, StreamingContext context)
        :base(info, context) {
    }
}

Without it, WCF will not deserialize your custom exception properly, and you'll (at best) be able to catch a non-generic FaultException (with the rather unhelpful reason of "The creator of this fault did not specify a Reason."

Monad

Don't expect a great answer from me as to what constitutes a monad; there's already a good question/answer on Stack Overflow.

Basically, it's a bit of glue that joins two functions together. I decided to write one for myself in C# to see what it would look like without any syntactic sugar that other languages might provide:

public static class Binding {
    public static Func<TInput, TOutput> Bind<TInput, TIntermediate, TOutput>(Func<TInput, TIntermediate> left, Func<TIntermediate, TOutput> right) {
        return arg => right(left(arg));
    }
}

It's designed so that the output of left "flows" into the input of right. The output of the rightmost function is returned to the caller as the result of the expression. Here are two functionally equivalent examples (one written normally, and the other with monads):

Func<string, IEnumerable<char>> js = s => s.Select(c => c - '0').Where(i => i % 2 == 0).Select(i => (char)(i + 'a')).Select(c => Char.ToUpper(c));

Func<string, IEnumerable<char>> ks = Binding.Bind<IEnumerable<char>, IEnumerable<int>, IEnumerable<char>>(
    k1 => k1.Select(c => c - '0'),
    Binding.Bind, IEnumerable<int>, IEnumerable<char>>(
        k2 => k2.Where(i => i % 2 == 0),
        Binding.Bind<IEnumerable<int>, IEnumerable<char>, IEnumerable<char>>(
            k3 => k3.Select(i => (char)(i + 'a')),
            k4 => k4.Select(c => Char.ToUpper(c)))));

Check that they work as expected:

Debug.Assert(ks("0123456789").SequenceEqual(new char[] {'A','C','E','G','I'}));