Posts Tagged: fold


8
Feb 11

The Road to Functional Programming in F# – From Imperative to Computation Expressions

In F# there are a lot of options when it comes to choosing the style in which you will perform a computation.  So, for our last meeting of the the NYC F# User Group I decided to try and build a general understanding of how the different styles are related to each other through trying them and discussing our results. Come along with us and explore five of different styles of programming in F#.

For our example I chose Project Euler #1 as it’s simple and wouldn’t get in the way of contrasting the different computation styles.

Find the sum of all the multiples of 3 or 5 below 1000.

As there are a lot of people out there that are new to F#, let’s start with an imperative approach.  That way we can all feel comfortable and see how the other styles relate.

let pe1_while limit =
    let mutable acc = 0
    let mutable x = 0
    while x < limit do
        if x % 5 = 0 || x % 3 = 0 then acc <- acc + x
        x <- x + 1
    acc

pe1_while 1000F# Web Snippets

val pe1_while : int -> int

Full name: Untitled.pe1_while

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val mutable acc : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val mutable x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Next, let’s move on to doing the same thing recursively.  This transition is the first step on the long road of functional programming and it’s important that new users see how the two basic patterns map to each other.  For this reason, I kept everything but the style of computation the same.

let pe1_rec limit =
    let rec inner_pe1 x acc =
        if x < limit then
            if x % 5 = 0 || x % 3 = 0 then
                inner_pe1 (x + 1) (x + acc)
            else
                inner_pe1 (x + 1) acc
        else acc
    inner_pe1 0 0F# Web Snippets

val pe1_rec : int -> int

Full name: Untitled.pe1_rec

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val inner_pe1 : (int -> int -> int)

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val acc : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

As you can see, the combination of the first if and the recursive calls correspond to the while statement.  The predicate remains the same.  The biggest conceptual hurdle for new users here is that for both predicates a course of action must be explicitly specified in both the success and failure case.

Another important idea here is that when doing recursion you don’t want to leave anything left undone on the stack. If you do, the compiler can’t do tail call optimization. Without tail call optimization each recursive call will create an additional stack frame. This slows things down and can even crash your program by overflowing the stack if the recursion goes too deep. As long as you don’t leave anything left undone your recursive function will run just as fast as a while loop.

I constructed this example with the thought that it would be best to avoid having to explain too many new constructs at once.  However, while discussing this solution one new user remarked that this looked like spaghetti code.  In response to this Paul, one of our more advanced users, whipped up a much nicer solution utilizing pattern matching.

let pe1_rec2 limit =
    let rec inner_pe1 acc = function
        | 1                     -> acc
        | i when (i % 3 = 0)
              || (i % 5 = 0)    -> inner_pe1 (acc + i) (i - 1)
        | i                     -> inner_pe1 acc       (i - 1)
    inner_pe1 0 (limit - 1) F# Web Snippets

val pe1_rec2 : int -> int

Full name: Untitled.pe1_rec2

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val inner_pe1 : (int -> int -> int)

val acc : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val i : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Now that’s some pretty code!  While it may have some intermediate concepts, the recursion looks just beautiful when structured with a pattern match.

Still, to most I think this hardly seems worth giving up mutation for.  This is why we should move on to pipelines and comprehensions next.

let pe1_seq limit =
    seq { 0 .. limit - 1 }
    |> Seq.filter (fun x -> x % 5 = 0 || x % 3 = 0)
    |> Seq.sumF# Web Snippets

val pe1_seq : int -> int

Full name: Untitled.pe1_seq

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Multiple items

val seq : seq<‘T> -> seq<‘T>

Full name: Microsoft.FSharp.Core.Operators.seq

——————–

type seq<‘T> = System.Collections.Generic.IEnumerable<‘T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<‘T>
inherits: System.Collections.IEnumerable

module Seq

from Microsoft.FSharp.Collections

val filter : (‘T -> bool) -> seq<‘T> -> seq<‘T>

Full name: Microsoft.FSharp.Collections.Seq.filter

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val sum : seq<‘T> -> ‘T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum

While bound to perform somewhat slower due to the use of sequences, it’s hard to imagine a more conceptually elegant solution to this problem. In comparison to the imperative version, the sequence comprehension takes on the role of both the while loop and the incrementor in generating the sequence values, the filter acts as the predicate and the sum as the accumulator.

The final two examples I’ll show you were more for fun and to provide a challenge to the intermediate and experienced users.  Conquering folding and unfolding were some of the biggest hurdles I faced when learning functional programming.  Just getting comfortable with how accumulators work takes some time for everyone.  For practice let’s use fold in our pipeline instead of filter and sum.

let pe1_fold limit =
    Seq.init limit id
    |> Seq.fold (fun acc x -> if x % 5 = 0 || x % 3 = 0
                              then acc + x 
                              else acc) 0F# Web Snippets

val pe1_fold : int -> int

Full name: Untitled.pe1_fold

val limit : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

module Seq

from Microsoft.FSharp.Collections

val init : int -> (int -> ‘T) -> seq<‘T>

Full name: Microsoft.FSharp.Collections.Seq.init

val id : ‘T -> ‘T

Full name: Microsoft.FSharp.Core.Operators.id

val fold : (‘State -> ‘T -> ‘State) -> ‘State -> seq<‘T> -> ‘State

Full name: Microsoft.FSharp.Collections.Seq.fold

val acc : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

val x : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

Here we took a somewhat different route when generating sequence values by using the Seq.init function.  As I discussed in my Ted Neward’s Folding Challenge post, the contents of the folding function can be directly mapped to the imperative and recursive solutions.  Just as in the first two examples the adding is done explicitly right along with the application of the predicate.   The biggest conceptual difference in this example is that the accumulator is passed as the return value of each call to fold instead of being kept in a mutable variable as in the imperative version or explicitly passed forward as in the recursive.

Finally, as a challenge to the most experienced users let’s see if we can do this with a computation expression.

type Euler1Builder() =
    member b.Combine(x, y) = x + y
    member b.Zero() = 0
    member b.Yield(x) = if x % 5 = 0 || x % 3 = 0 then x else 0
    member b.For(vals, f) =
        vals |> Seq.fold (fun s n -> b.Combine(s, f n)) (b.Zero()) 

let eb = new Euler1Builder()

let pe1_eb limit = eb { for x = 0 to limit - 1 do yield x }F# Web Snippets

type Euler1Builder =
class
new : unit -> Euler1Builder
member Combine : x:int * y:int -> int
member For : vals:seq<‘a> * f:(‘a -> int) -> int
member Yield : x:int -> int
member Zero : unit -> int
end

Full name: Untitled.Euler1Builder

val b : Euler1Builder

member Euler1Builder.Combine : x:int * y:int -> int

Full name: Untitled.Euler1Builder.Combine

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val y : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

member Euler1Builder.Zero : unit -> int

Full name: Untitled.Euler1Builder.Zero

member Euler1Builder.Yield : x:int -> int

Full name: Untitled.Euler1Builder.Yield

member Euler1Builder.For : vals:seq<‘a> * f:(‘a -> int) -> int

Full name: Untitled.Euler1Builder.For

val vals : seq<‘a>

type: seq<‘a>
inherits: System.Collections.IEnumerable

val f : (‘a -> int)

module Seq

from Microsoft.FSharp.Collections

val fold : (‘State -> ‘T -> ‘State) -> ‘State -> seq<‘T> -> ‘State

Full name: Microsoft.FSharp.Collections.Seq.fold

val s : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val n : ‘a
member Euler1Builder.Combine : x:int * y:int -> int
member Euler1Builder.Zero : unit -> int

val eb : Euler1Builder

Full name: Untitled.eb

val pe1_eb : int -> int

Full name: Untitled.pe1_eb

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

This first attempt is what I showed off at our user group meeting.  It’s embarrassingly ugly and ends up just being a convoluted way to generate a sequence and fold over the values.  Since the meeting I’ve fiddled with it a bit and have come up with a solution I like much more.

type Euler1Builder2() =
    member b.Yield(x) = if x % 5 = 0 || x % 3 = 0 then x else 0
    member b.For(generated, f) = generated |> Seq.map (fun x -> f x)
    member b.Run(filtered: int seq) = filtered |> Seq.sum 

let eb2 = new Euler1Builder2()

let pe1_eb2 limit = eb2 { for x = 0 to limit - 1 do yield x }F# Web Snippets

type Euler1Builder2 =
class
new : unit -> Euler1Builder2
member For : generated:seq<‘a> * f:(‘a -> ‘b) -> seq<‘b>
member Run : filtered:seq<int> -> int
member Yield : x:int -> int
end

Full name: Untitled.Euler1Builder2

val b : Euler1Builder2

member Euler1Builder2.Yield : x:int -> int

Full name: Untitled.Euler1Builder2.Yield

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

member Euler1Builder2.For : generated:seq<‘a> * f:(‘a -> ‘b) -> seq<‘b>

Full name: Untitled.Euler1Builder2.For

val generated : seq<‘a>

type: seq<‘a>
inherits: System.Collections.IEnumerable

val f : (‘a -> ‘b)

module Seq

from Microsoft.FSharp.Collections

val map : (‘T -> ‘U) -> seq<‘T> -> seq<‘U>

Full name: Microsoft.FSharp.Collections.Seq.map

val x : ‘a

member Euler1Builder2.Run : filtered:seq<int> -> int

Full name: Untitled.Euler1Builder2.Run

val filtered : seq<int>

type: seq<int>
inherits: System.Collections.IEnumerable

Multiple items

val int : ‘T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

——————–

type int<‘Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type: int<‘Measure>
implements: System.IComparable
implements: System.IConvertible
implements: System.IFormattable
implements: System.IComparable<int<‘Measure>>
implements: System.IEquatable<int<‘Measure>>
inherits: System.ValueType

——————–

type int = int32

Full name: Microsoft.FSharp.Core.int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Multiple items

val seq : seq<‘T> -> seq<‘T>

Full name: Microsoft.FSharp.Core.Operators.seq

——————–

type seq<‘T> = System.Collections.Generic.IEnumerable<‘T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<‘T>
inherits: System.Collections.IEnumerable

val sum : seq<‘T> -> ‘T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum

val eb2 : Euler1Builder2

Full name: Untitled.eb2

val pe1_eb2 : int -> int

Full name: Untitled.pe1_eb2

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Instead of being like the fold example, this is much more like pipeline.  The only downside here is that the computation expression attempts to be as generic as possible and so we need a type annotation to make the example compile.  Overall, I think it ended up looking quite nice.  It’s also not nearly as complex as you might think.

Let me explain how each of the members of the computation expression fit together to make this work.  The builder’s For method allows us to use a for loop within our expression.  The values generated by that for loop are provided to the For method in the form of a sequence.  When For is called, it is passed that sequence along with a function which does whatever is scoped inside of our expression’s for loop.  In this case, that function is the builder’s Yield method because we are yielding each value.  Finally, the entire computation is preformed within the context of the Run method, which allows the input and output of the expression to be manipulated.  So, within our example we generate our values with For, filter them in Yield and then finally sum them in Run.

I hope you’ve enjoyed our journey through the different styles of computation in F#. The only style I think I didn’t cover here is continuation passing, which is more of a hack to get around the limits of recursion and linked lists anyway.  If you do think of something I missed, want to discuss something related or just feel like being friendly I hope you’ll leave a comment.


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.