Crashing F#

There's been a lot of buzz about using F# on the CLR for functional programming. This week, I decided to take the language for a spin.

The Basics

F# has a wonderfully light and succinct syntax. It uses the same keyword, let, for both values and functions.

let str = "Hello"
let func a = a + str 
let another = func " World!"
printfn "%s" another

Also, discriminated unions (sum types) are super simple

type SumType =
  |First
  |Second
  |Third of string * int
  |Fourth of a:string * b:int * c:double

Anytime I try out a new language I try to explore five things:

 
  1. Tail recursive functions
  2. Functor
  3. Monad
  4. Free Monad
  5. Pattern Matching

F#, as far as I can tell after using it for a total of about 10 hours, can be used for 1-3 and 5 but not 4. Here is a brief synopsis of my trials.

Tail Recursion

This was extremely simple in F#. Its two steps:

  1. Mark a function as recursive using the rec keyword
  2. Put the recursive step as the last operation
module Recursion
    //need a keyword for recursion, otherwise boilerplate free
    //very nice
    let rec check many acc =
        if(0 = many) then acc
        else
            let a = many - 1
            let b = acc + many
            check a b

The Recursion.check function uses the accumulator pattern to add int values from 1 to many to the initial accumulator value acc.

Functor & Monad

This took some work! F# lacks higher kinded polymorphism. My first attempt at this was:

type Functor<'A> =
    abstract map: 'A<'B> -> ('B -> 'C) -> 'A<'C>

Which produced a compile time error: "Type parameter cannot be used as type constructor." Ouch!!!

Luckily, F# type inference is good enough that we don't really need to define type classes with a little boilerplate. Here is a Functor & Monad example:

//cannot do higher kinds so no type classes
//do not need higher kinds; type syntax takes care of it
module CategoryList
type Functor<'Type>() =
member this.map(l: list<'Type>)(f: 'Type -> 'Return) =
  List.map f l
type Monad<'Type>(func: Functor<'Type>) =
member this.point(t: 'Type) = [t]
member this.flatMap(l: list<'Type>)(f: 'Type -> list<'Return>) =
List.concat(func.map l f)

Defining a Functor and Monad instance is simple. We don't need a type hierarchy here; we only need 3 functions.

module Category
let check() =
//instantiate monad
let func = CategoryList.Functor<int>()
let monad = CategoryList.Monad(func)

//define monadic chain functions
let flatMap l f = monad.flatMap f l
let map l f= func.map f l

//define helpers
let mapper (x:int) = [1 .. x]
let mapperStr (x:int) = x.ToString()

let hundred = [1 .. 100]//data

//(|>) language level monad support
let hundredMore = (hundred
|> flatMap mapper)
printfn "%A" hundredMore

let bigString = (hundredMore
|> flatMap mapper
|> map mapperStr)
printfn "%A" bigString

The key here is the |> operator (also known as pipe). By piping a list into a flatMap into another flatMap and so on, we can get language level monad support.

Free Monad

Here I have failed. The closest I've gotten is:

module Free
type FreeMonad<'F, 'A> =
|Pure of 'A
|Suspend of 'F

type FreeMonad<'F, 'A> with
member this.fold fpure fsuspend =
match this with
|Pure(a) -> fpure(a)
|Suspend(free) -> fsuspend(free)

let inline liftF(t:'F)(func: 'T): FreeMonad<'F, 'A>
when ^T: (member map: (^F -> (^A -> ^AA) -> ^FF)) = Suspend(t)
let inline point(a: 'A)(func: 'T): FreeMonad<'F, 'A>
when ^T: (member map: (^F -> (^A -> ^AA) -> ^FF)) = Pure(a)

let check(): Unit =
let func = CategoryList.Functor<int>()
let lst: list<int> = [1..10]
let monad:FreeMonad<list<int>, int> = liftF(lst)(func)
()

I could never get the liftF function to work out. The combination of type parameters never type checks against the parameterized types AA and FF. The compiler just cannot understand the second layer of type inference that needs to happen for the map method to be recognized.

Pattern Matching

Pattern matching is pretty straight forward. You can do direct

let func a =
  match a with
  |1 -> "one"
  |2 -> "two"
  |3 | 5 | 10 | 30 -> "large"
  |_ -> "else"

with guards

let func a =
    match a with
    |value when 0 > value -> "negative"
    |value when 0 < value -> "positive"
    |_ -> "zero"

type matching

let func a =
    match a with
    |(str: string) -> "string"
    |_ -> "not"

discrimminated unions

type Union =
    |Simple
    |Pair of int * int
    |Triple of int * int * int
let func a =
    match a with
    |Simple -> "simple"
    |Pair(a, b) -> "(" + a.ToString() + "," + b.ToString() + ")"
    |Triple(a, b, c) -> "(" + a.ToString() + "," + b.ToString() + c.ToString() + ")"

That's most of pattern matching, by combining these patterns you can get some pretty serious control folow moving through your application.