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 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 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
Full name: Untitled.pe1_fold
type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
from Microsoft.FSharp.Collections
Full name: Microsoft.FSharp.Collections.Seq.init
Full name: Microsoft.FSharp.Core.Operators.id
Full name: Microsoft.FSharp.Collections.Seq.fold
type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
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
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
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 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
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
module Seq
from Microsoft.FSharp.Collections
val map : (‘T -> ‘U) -> seq<‘T> -> seq<‘U>
Full name: Microsoft.FSharp.Collections.Seq.map
member Euler1Builder2.Run : filtered:seq<int> -> int
Full name: Untitled.Euler1Builder2.Run
val filtered : seq<int>
type: seq<int>
inherits: System.Collections.IEnumerable
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
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.
Enjoy this post? Continue the conversation with me on twitter.
Tags: Computation, Computation Expressions, F#, fold, Imperative, NYC F# User Group, Seq
Nice post!
About recursion, Functional programming taught me the same as imperative programming did; When you see production code using recursion, be wary.
It’s the elegant solution, to be sure, but hardly the most efficient. The F# compiler unfortunately does not give you a warning when your rec methods are not tail calls.
To me, more often than not, a recursive method is a nice, elegant prototype waiting to be rewritten to an imperative one using encapsulated mutables.
A compiler warning would be nice for sure, but I don’t think it’s necessary to go as far as to rewrite recursive functions as imperative. Once you get familiar with them, the non-tail ones jump right out at you. The key thing to look for is if the results of the recursive function are used after it’s called.
There are ‘functional’ concepts that allow to avoid both explicit recursion and mutable state. Moreover, Haskell people encourage use of folds instead of recursion. Abstraction… you know =)
Robert Jeppesen: “…To me, more often than not, a recursive method is a nice, elegant prototype waiting to be rewritten to an imperative one using encapsulated mutables.”
Then, how about let the compiler do it? That it’s exactly what the F# compiler does when you enable the “Generate tail call” optimization (it’s enabled by default in “Release” mode). The compiler would rewrite the recursion into a while loop with mutable variables. Just the way you want it. You can verify what the compiler does by using Reflector.
I think there is no need in lambda in Euler1Builder2.For implementation. One can simply do ‘generated |> Seq.map f’.
That’s true. I’ve been avoiding point-free style for examples because I don’t want to confuse new users, but I guess that’s kind of silly for something like computation expressions.
Thanks for the post! I especially like the computation expression examples because I’m still not very much at home with that beast.
I’m giving a talk this weekend at the NYC Code Camp on Computation Expressions. A blog post will follow shortly for sure :).
Its nice seeing the evolution of the code going from recursion through to computation expressions.
I must say the most elegant for me personally are the pipelined versions, they are very easy to read and code comments are not necessary any more. I remember reading chapter 17 in Professional F# 2.0 it really nails the concept well.
Have you noticed the the fswebsnippet tooltips don’t always pop up on the top layer?
I has a similar problem on my blog, so a reverted back to syntaxhighlighter
Thanks!
I’ve had that same problem with the web snippets in chrome but not firefox. They look nice enough that I figure it’s ok. Still, I’ll mention it to Tomas. Maybe he has a suggestion.
Great post! Nice to see a simple example evolving through the various options F# has to offer.
The evolution of your code mirrored very much my experience in coming to grips with the language.
There’s an error in the third snippet.
inner_pel (limit – 1) 0 should be
inner_pel 0 (limit – 1)
Good catch. I’m not sure how that snuck in there.
Great post.
As an imperative programmer, I thought every functional example looked more complicated than the imperative.
I hope this is just my contingent learning path: I would like to hear whether someone raised entirely in functional circles thought the imperative example as difficult to understand as I do the functional examples.
Thanks!
Coming from an imperative background myself, I can say it really is just about learning new patterns. The thing about the FP patterns which, once mastered, leads to much better code, is that they have fewer bound variables in scope and break the problem up into easy to reason about cases. Believe me, once you have it down, it’s much harder to mess up on a pre-coffee Monday morning :).
Just use the sequences – use fold to map over existing stuff and unfold to generate new stuff. Forget about the tail call problem – the sequence takes care of it for you
But as always it’s a tradeoff. Sequences have significant overhead when compared to a nice tail call recursive function. IEnumerable will always require a mess of invocations to get even a single element, while a tail recursive function gets turned into a fast loop by the compiler.
[…] This post was mentioned on Twitter by Mark Needham, cameron frederick, Richard Minerich, darachennis, danfinch and others. danfinch said: RT @rickasaurus: Blogged: The Road to Functional Programming in F# – From Imperative to Computation Expressions http://bit.ly/fPETDi #fsharp […]
[…] Richard Minerich’s The Road to Functional Programming in F# – From Imperative to Computation… “In F# there are a lot of options when it comes to choosing the style in which you will perform a computation. ” […]
[…] recursion with accumulators. This post is just a more advanced version of what I talked about in my From Imperative to Computation Expressions post. In fact, if you haven’t already I suggest you read it first. I’ll be assuming you […]
[…] want to move on to recursion and folding though. When you’re ready to make the jump read this post which talks about how to go about […]