April, 2010


29
Apr 10

The Ted Neward F# Folding Challenge

My friend, and fellow Professional F# 2.0 author, Ted Neward recently challenged me to a bit of a Code Kata.   Take a list of numbers and compress it in a particular simple way but without any mutable state.  What makes this problem interesting is that a tech interviewer mentioned that that he hadn’t seen a functional solution to this problem.  I also wanted to share this because I think it’s a great example of how to convert an imperative loop into a functional fold.

So, on to the problem.

Given a set of numbers like [4; 5; 5; 5; 3; 3], compress it to be an alternating list of  counts and numbers.

For example, the solution for [4; 5; 5; 5; 3; 3] would be [1; 4; 3; 5; 2; 3], as the list consists of one four, then three fives and finally two threes.  Ordering counts as the initial list must be reconstructable from the compressed list.  The answer to [4; 5; 4] would be [1; 4; 1; 5; 1; 4]

The imperative solution is rather simple, we use three variables outside of a loop:  a last value, a count and an accumulator list.

let clImp list =
    let mutable value = 0
    let mutable count = 0
    let output = new System.Collections.Generic.List<_>()
    for element in list do
        if element <> value && count > 0 then
            output.Add(count)
            output.Add(value)
            count <- 0
        value <- element
        count <- count + 1
    if count > 0 then
        output.Add(count)
        output.Add(value)
    output

Using the normal .NET mutable list type, this version works efficiently and produces the output we expect.

> let compressed = clImp numbers
   Seq.iter (fun e -> printf "%i " e) compressed;;

1 4 3 5 2 3

How might we convert this to a functional style?  In this example, the general type of operation could be thought of as the gradual building of a data structure while walking over a list.  F# just happens to have a list processing function designed just for this task.  This function is named fold and it is one of the most useful constructs in any functional programmer’s tool chest.

let clFold input =
    let (count, value, output) =
        List.fold
            (fun (count, value, output) element ->
                if element <> value && count > 0 then
                    1, element, output @ [count; value]
                else
                    count + 1, element, output)
            (0 , 0, [])
            input
    output @ [count; value]

Here, we are doing almost exactly the same thing as in the imperative version but with a fold instead of a loop.   The secret is that instead of putting variables outside of our loop and changing them with mutation, we have added them as elements in our accumulator tuple.  In this way, the values are updated when each element is visited with no mutation.

However, there is one serious problem with this example.  Appending to the end of a linked list requires recreating every node in that list.  This will make our algorithm grow exponentially slower approximately in proportion to the length of the input list.  To correct this we have two choices: do a head append with a normal fold and reverse the list when we are done, or use foldBack.  The foldBack version is a rather small step from here and looks much nicer, so let’s go in that direction.

let clFoldBack input =
    let (count, value, output) =
        List.foldBack
            (fun element (count, value, output) ->
                if element <> value && count > 0 then
                    1, element, [count; value] @ output
                else
                    count + 1, element, output)
            input
            (0, 0, [])
    [count; value] @ output

There are only two real changes here.  First, we are using foldBack instead of fold.  This change causes some argument reordering.  Second, we are appending to the head of the output list instead of the tail.  It works well, is rather fast and is easy to understand if you are comfortable with folds.

However, there is a bit of a dirty secret here.  Under the hood foldBack converts its input list into an array when the size is large.  As arrays have linear element look up time, they can be walked through backwards very quickly.  Does this make the solution not functional?  You’d never know unless you looked at the underlying implementation.  Anyway, however  you want to label it,  it sure works well.

If you liked this example and want to see more check out our book, Professional F# 2.0.   It’s just about to be done.  In fact, I better get back to editing.


10
Apr 10

The Repeating History of Closed Platforms

I was one of the many that loved the iPhone AppStore platform.  Consumers marveled at how we could easily buy any application we might want, vetted with a nice rating system.   Developers were shocked at the ease with which it seemed possible to monetize on simple applications.   The only downside seemed to be the occasional political or ambiguous AppStore rejection.

Looking back now, the recent changes to Apple’s developer terms of service are not so much of a shock.  They are just the continuation of Apple’s past policies.  It’s the same pattern of gradual erosion of Consumer and Maker rights we see on any platform over time.  If you look beyond the scope of software and include any marketable good, you see a long history of this pattern repeated over and over.  Consider cable television and the music industry.

At first, closed platforms are great.  They get the both the Consumer and the Maker what they need as fast and easily as possible, because that’s the platform provider’s job.  The platform providers are competing against each other and so must cater to both the Consumer and the Maker.  However, this soon changes.

Over time, one of two things happen, both bad:  Either a single provider wins out and gains a monopoly, or platform providers conspire together.  The platform then becomes a weapon in the corporate war chest.  The ultimate end is control over both the Makers and the Consumers until a new revolutionary platform emerges, catches the old players off guard and the process begins again.

The only escape from this pattern seems to be the open source community, a community in which the Makers have taken complete control by keeping out profit-seeking Providers.  However, this seems to have the unfortunate side effect of alienating Consumers.  Perhaps this can be remedied by a benevolent Platform Provider, but I’m not holding my breath.