Do Loop Until You Die

We all know the importance of protecting consumers of our libraries from our design decisions.  In object oriented programming we refer to this protection mechanism as encapsulation or black box design.  Functional programming allows us to achieve the same goal under a slightly different guise, abstract data types.

 

Abstract Data Types in ML

 

The first way to build an abstract data type in ML is to define the data type using abstype instead of datatype.

 

abstype ‘a Set = set of ‘a list

with …

 

Here we’ve chosen to use a list as the underlying store for our Set data type.  As long as we keep the “interface” the same, we are free to choose a different design for the underlying store.  The abstype keyword hides the set data constructor from the consumer, preventing sets being constructed from lists.

 

The abstype keyword may seem convenient, however, modern ML programs rarely use it.  Abstype has been deprecated in favor of opaque signature ascription.

   

signature SetSig =

sig

    type ‘a set

    val empty : ‘a set

    val singleton : ‘a -> ‘a set

end;

 

structure Set :> SetSig =

struct

    type ‘a set = ‘a list;

    val empty = [];

    fun singleton a = [a]

end;

 

The Set structure is similar to a typeclass where we’ve provided an implementation for SetSig using lists.  We are free to provide an implementation using binary trees and change the implementation Set will use under the covers.

 

signature SetSig = …

structure ListSet :> SetSig = …

structure TreeSet :> SetSig = …

Set = TreeSet

 

The consumer remains unaware that we’re now using a binary tree instead of a list to represent sets.

 

Abstract Data Types in F#

 

There is no abstype keyword in F# so we’ll use opaque signature ascription to achieve our data abstraction.

 

module SetSig

    type ‘a set

    val internal toList : ‘a set -> ‘a list

    val empty : ‘a set

    val singleton : ‘a -> ‘a set

   

module SetSig

    type ‘a set = internal Set of ‘a list

    let toList s = match s with Set lst -> lst

    let empty = Set[]

    let is_empty s = List.length(toList s) = 0

    let singleton x = Set[x]

 

There are a couple of problems with the F# implementation.

 

The fist is just annoying.  We use the module keyword for both the signature and the implementation in F#.  The signature must go into a file with the fsi extension and the implementation in a file with an fs extension.  The system is similar to header files in c and went out of favor around the time Java was introduced.  Hopefully, the day will come when the signature and the many implementations of the signature can be declared in the same file.

 

The second is limiting.  Notice how we’ve had to declare a toList method to convert our set to a list?  This limits our signature to lists.  Without the concept of functors we have no way to vary our implementation without changing our signature.

 

The third is explicitness. Even with functors in the language we would constantly have to convert from a set to a functor and back again.  There is no implicit conversion mechanism.

 

The fourth is the module system. Notice how without a different keyword for signature and structure we have no way to provide additional implementations of our signature.  ML allows the following all in one file

 

signature SetSig = …

structure ListSet :> SetSig = …

structure TreeSet :> SetSig = …

Set = TreeSet

 

How we achieve this in F# I do not know.

 

Expanding Our Set Signature

 

Let’s add a bit more functionality to our Set signature to get an idea of how cumbersome problem number two is.

 

module SetSig

    type ‘a set

    val internal toList : ‘a set -> ‘a list (* list all set elts, sorted low to high *)

    val empty : ‘a set (* the empty set *)

    val is_empty : ‘a set -> bool (* is a set the empty set *)

    val singleton : ‘a -> ‘a set (* a set with one element *)

    val union: ‘a set -> ‘a set -> ‘a set (* union of two sets *)

    val is_member : ‘a -> ‘a set -> bool (* is elt a member of given set? *)

    val remove : ‘a -> ‘a set -> ‘a set (* remove elt from given set *)

 

module SetSig

    type ‘a set = internal Set of ‘a list

    let toList s = match s with Set lst -> lst

    let empty = Set[]

    let is_empty s = List.length(toList s) = 0

    let singleton x = Set[x]

    let union s1 s2 = Set(ListSetUtils.union (toList s1) (toList s2))

    let is_member x s = ListSetUtils.is_member x (toList s)

    let remove x s = Set(ListSetUtils.remove x (toList s))

 

Two patterns should immediately jump out at you.

 

1.    We constantly have to use toList to convert our set to a list

2.    We constantly have to use the Set data constructor to wrap our list as a set

 

The constant wrapping and unwrapping obfuscates the purpose of our code and makes it harder to vary the implementation without rewriting everything.  You wish there was a way to tell the compiler to implicitly convert from list to set and vice versa instead of always having to explicitly make the conversion.

 

Pattern Matching To the Rescue

 

All is not doom and gloom, however, F# has very cool pattern matching capabilities.  Let’s say a consumer of our library wants to add a function to calculate the cardinality of the set.  In ML we would provide a destructor function and force the user into the following pattern.

 

let rec cardinality s =

    if is_empty s then 0 else

    let (x,s’) = singleton_split s

    1 + cardinality s’ 

 

With F# we can provide pattern matching over our abstract data types.

 

module SetSig

    …

    val internal singleton_split : ‘a set -> ‘a * ‘a set (* remove elt from given set and return singleton *)

    val (|Nil|Cons|) : ‘a set -> Choice<’a set,(’a * ‘a set)>

 

module SetSig

    …

    let singleton_split s =

        match toList s with

        | [] -> invalid_arg “s”

        | x::s -> let lst = ListSetUtils.remove x s

                  (x, Set(lst))

    let (|Nil|Cons|) s =

        if is_empty s then Nil(s)

        else Cons(singleton_split s)

 

Notice the return type of our pattern matching function, choice basically returns all possibilities and allows us to match on them.  The consumer of our library can now do the following.

 

let rec cardinality s =

    match s with

    | Nil s -> 0

    | Cons(x,s) -> 1 + cardinality s

 

Handy, and an F# exclusive feature.

 

A Mixed Bag of Functionality

 

The Set class provided in Microsoft.FSharp actually implements a Set as an object oriented class.  Unfortunately, swapping this Set out for your own implementation is a non starter as it does not implement an interface.

 

With Haskell we get higher kinded polymorphism and type classes, ML solves many of the same problems with a sophisticated module system, F# uses the object oriented type system of .Net to solve problems the way you would in VB or C#.  Hopefully, at some point F# will be free to forge its own road on the .Net platform, making it easier to solve problems the other functional languages have licked.

December 15th, 2008 | Tags: Abstract Data Types, F#, ML, Sets | Category: F#, Pattern Matching | Comments (7)

When pitching functional programming to an imperative friend, the “map” function is the canonical example of the obvious advantages of the functional approach.  And once our backwoods imperative friend has begrudgingly accepted “map” as a neat party trick, we can really amaze them by abstracting “map” over any mappable structure.  That is as long as brand of functional magic is something besides F#.

 

A Map over Trees

 

Let’s start with an example from Real World Haskell.

 

type Tree<’a> =

    | Node of (Tree<’a>) * (Tree<’a>)

    | Leaf of ‘a

 

let tree = Node ((Leaf “foo”),(Node((Leaf “x”),(Leaf “quux”))))

 

And we can write a function to calculate the length of the string at each node.

   

let rec tree_lengths = function

    | Leaf s -> Leaf (String.length s)

    | Node (l,r) -> Node (tree_lengths l,tree_lengths r)

 

> tree_lengths tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

 

But we prefer to use our party trick wherever we can and so we write.

 

let rec tree_map f tree =

    match tree with

    | Leaf a -> Leaf (f a)

    | Node (l,r) -> Node (tree_map f l,tree_map f r)

 

> tree_map String.length tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

 

Then impress them with our combinations.

 

let odd = (fun x -> x % 2 <> 0)

 

> tree_map (odd << String.length) tree;;

val it : Tree<bool> = Node ((Leaf true),(Node((Leaf true),(Leaf false))))

 

And finally define an operator for our tree_map mapping function.

 

let (<$>) f tree = tree_map f tree

 

> String.length <$> tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

 

> (odd << String.length) <$> tree;;

val it : Tree<bool> = Node ((Leaf true),(Node((Leaf true),(Leaf false))))

 

A Map over Type<_>

 

Now that we’ve defined a map function for Tree types let’s compare it to our familiar map function over lists.

 

// val tree_map : (’a -> ‘b) -> Tree<’a> -> Tree<’b>  

let rec tree_map f tree =

    match tree with

    | Leaf a -> Leaf (f a)

    | Node (l,r) -> Node (tree_map f l,tree_map f r)

 

// val list_map : (’a -> ‘b) -> List<’a> -> List<’b>

let rec list_map f list =

    match list with

    | [] -> []

    | h::t -> (f h) :: list_map f t

 

In both cases we’re taking a function over ordinary types and lifting it into a function over container types. If a is a Type then our Tree and List types are related in that they are both Type<_>.  And because we prefer to codify the relationship between apparently disparate structures, we write the following map function  

 

// val list_map : (’a -> ‘b) -> Type<’a> -> Type<’b>

let type_map f t =

    match t with

    | :? List<’a> -> list_map f t.a

    | :? Tree<’a> -> tree_map f t.a

 

let (<$>) f t = type_map f t

 

Of course the compiler screams about our attempt to relate trees and lists.  Our type_map function requires 4 concepts the F# compiler does not support.

 

1.    Higher kinded polymorphism

2.    Pattern matching over higher kinds

3.    Static type tests

4.    Polymorphic return types

 

In plain English this means we want the compiler to differentiate between ordinary types and parameterized types, pattern match over parameterized types, provide a standard way to extract the underlying type, catch invalid type tests at compile time instead of runtime, and allow us to return specific instances of Type<_> from a function.

 

Because F# has to use the type system of .Net, I wouldn’t expect any of these any time soon, if ever. 

 

A Connection between Trees and Lists

 

Unfortunately, F# brains will never make the connection between trees and lists. Trees and lists will forever remain separate unrelated concepts.  How important you regard this connection depends on your tolerance for redundant code.  I guess we’ll have to learn to have a high tolerance indeed. 

December 7th, 2008 | Tags: F#, Functors, Haskell, Map | Category: F#, Functors, Haskell | Comments (1)

When a book is packed with concepts and information it’s very easy to gloss over something that in retrospect is very interesting.  I often skim back over things I’ve already read hoping some of the new information I’ve accumulated will lead to deeper insights and interesting discoveries.  “Untying the recursive knot” from F# for Scientists is one such concept I don’t believe I was sufficiently fluent enough in functional programming to glean its power.  Let’s have a look.

 

Recursive Functions

 

The factorial function is a pretty standard function for introducing the concept of recursion to beginning functional programmers.

 

let rec factorial = function

    | 0 -> 1

    | n -> n * factorial (n - 1)

 

The rec keyword allows us to recursively call our factorial function passing in a number 1 less than the current call.  The factorial function is a perfectly good function that accomplishes its assigned task, hence

 

> factorial 5;;

val it : int = 120

 

but as functional programmers we’re not so interested in standalone functionality as the ability to compose simple functions into more complex ones.  We have no way to intercept the recursion and plug in a piece of custom functionality.

 

So how can we untie this recursive knot?

 

Higher Order Continuations

 

We can rewrite our factorial function to accept the function it should call next.

 

//val factorial : (int -> int) -> int -> int

let factorial factorial = function

    | 0 -> 1

    | n -> n * factorial(n - 1)

 

And now we need a way to jumpstart the recursion.

 

//val y : ((’a -> ‘b) -> ‘a -> ‘b) -> ‘a -> ‘b

let rec y f x =

    f (y f) x

 

The y combinator will continue to generate a continuation for us as long as we ask for one.  Applying y to our factorial function gives us the answer we expect

 

> y factorial 5;;

val it : int = 120

 

except now we’re able to insert some custom functionality right into the middle of the recursion.

 

> y (factorial >> fun f n -> printf “%d\n” n; f n) 5;;

5

4

3

2

1

0

val it : int = 120

 

Pretty neat!  Instead of each function having its own proprietary recursion, we’ve made y our recursive combinator, and all other functions are responsible for playing nicely with it or risk being excluded from the fun.

December 1st, 2008 | Tags: Combinators, F#, Recursion | Category: Combinators, F# | Leave a comment

If you’ve been programming in F# for any length of time then undoubtedly you’ve run into the term “call by value”.  Another name for “call by value” is eager evaluation as opposed to lazy evaluation and the corresponding “call by name”.  Let’s throw together a fun little program to demonstrate the difference between the two.

 

Call By Value

 

type MissileCommand =

    | Launch

    | Disable

 

let a1 = printfn “%A” “KABOOM!”

let a2 = printfn “%A” “WE LIVE!”

 

let run cmd a1 a2 =

    match cmd with

    | Launch -> a1

    | Disable -> a2

   

run Disable a1 a2

 

So what do you think gets printed to the screen when we run our Disable command?  You may be surprised to see the following written to the console.

 

“KABOOM!”

“WE LIVE!”

 

So how did the human race get obliterated when we sent the Disable command?  In a “call by value” language functions arguments are evaluated eagerly, so both a1 and a2 are evaluated before the run function is applied to them.  Scary!

 

Call By Name

 

To simulate “call by name” semantics in F# we are forced to explicitly wrap our functions in a lazy wrapper.

 

let lazy_a1 = lazy (printfn “%A” “KABOOM!”)

let lazy_a2 = lazy (printfn “%A” “WE LIVE!”)

 

let safe_run cmd (a1:Lazy<_>) (a2:Lazy<_>) =

    match cmd with

    | Launch -> a1.Force()

    | Disable -> a2.Force()

 

safe_run Disable lazy_a1 lazy_a2

 

And now the human race is saved from nuclear annihilation as we get what we expect printed to the console.

 

“WE LIVE!”

 

The lazy wrapper acts as a thunk for the actual computation which only gets computed once we force it.

 

Call By Value With Side Effects

 

Now I hope you don’t lie await at night worrying about a computer bug accidently leading to Armageddon.  I’m sure our nuclear missile system is written in a lazy language. But I do hope you get a feeling for what a noxious combination “call by value” and undocumented side effects are.

 

What if instead of printing to the console our action updated a global counter?  Or deleted records from a database?  Functional languages allow us to pass functions around as if they were data, but do we really want them evaluating them behind the scenes when they do?

November 28th, 2008 | Tags: call by name, call by value, eager evalutation, F#, lazy evalutation | Category: F#, Lazy Evaluation | Comments (7)

We left off in a rather unsatisfying predicament, we can simulate OCaml functors with interfaces, but at the expense of passing in two type parameters and guarding all our functions with type constraints.  Yuck!

 

Let’s solve both these problems

 

OCaml Functors at the Type Level

 

Let’s leave the realm of regular F# and pretend we’re able to declare static members on our interfaces.  This allows us to pass functions around with the type parameters themselves instead of just the instances.  With this one simple enhancement to interfaces we can now declare the following signatures.

 

#type comparison = Less | Equal | Greater;;

type comparison = Less | Equal | Greater

 

#module type ORDERED_TYPE =

   sig

     type t

     val compare: t -> t -> comparison

   end;;

module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end

 

#module OrderedString =

   struct

     type t = string

     let compare x y = if x = y then Equal else if x < y then Less else Greater

   end;;

module OrderedString : sig type t = string val compare : ‘a -> ‘a -> comparison end

 

becomes

 

type comparison = Less | Equal | Greater

 

type ORDERED_TYPE<’a> =

    static type t : ‘a

    static abstract compare : t -> t -> comparison

 

type OrderedString() =

    interface ORDERED_TYPE<string> with

        member compare x y = if x = y then Equal else if x < y then Less else Greater

 

and our set signature with only the add function gets simplified to the following.

 

type Set<’con> when ‘con :> ORDERED_TYPE<con.t> () =

    member me.add (x : con.t) (s : con.t list) =

        let rec add (x : con.t) (s : con.t list) =

            match s with

            | [] -> [x]

            | hd::tl ->

                match con.compare x hd with

                | Equal   -> s         (* x is already in s *)

                | Less    -> x :: s    (* x is smaller than all elements of s *)

                | Greater -> hd :: add x tl

        add x s

 

By allowing functions to be passed around with type parameters, we now only have to pass a single type parameter because we can extract the underlying type by a call to t.  Also, we no longer have to pass constrained types into our add function.  We can simply call the static compare function on our con type parameter.

 

Of course, we don’t have “fancy” type level programming in F# so we’re forced to solve the problem at the instance level.

 

OCaml Functors at the Instance Level

 

Type constraints seem of little use when you can’t perform type level programming.  So let’s move the type constraint from the parameter list to the constructor.  Let’s redefine our interfaces and set type.

 

type ORDERED_TYPE<’a> =

    abstract compare : ‘a -> ‘a -> comparison

 

type OrderedString() =

    interface ORDERED_TYPE<string> with

        member me.compare x y = if x = y then Equal else if x < y then Less else Greater

 

type Set<’a> (cf : ORDERED_TYPE<’a>) =

    member me.empty : ‘a list = []

    member me.add (x : ‘a) (s : ‘a list) =

        let rec add (x : ‘a) (s : ‘a list) =

            match s with

            | [] -> [x]

            | hd::tl ->

                match cf.compare x hd with

                | Equal   -> s         (* x is already in s *)

                | Less    -> x :: s    (* x is smaller than all elements of s *)

                | Greater -> hd :: add x tl

        add x s

 

Just as with the type level example, we now only need a single type parameter and no longer have to constrain our functions with type constraints.  The use of the class really isn’t too bad.

 

let StringSet = Set<string>(OrderedString())

let r1 = StringSet.add “do” (StringSet.add “re” (StringSet.add “mi” StringSet.empty))

printfn “%A” r1

 

prints [“do”;”mi”;”re”] to the console we can easily compose a different version of our set.  For instance,

 

type OrderedStringReverse() =

    let reverse (s:string) = new string(s |> Seq.to_array |> Array.rev)

    interface ORDERED_TYPE<string> with

        member me.compare x y =

            let rev_x = reverse x

            let rev_y = reverse y

            if rev_x = rev_y then Equal else if rev_x < rev_y then Less else Greater

 

let StringSetReverse = Set<string>(OrderedStringReverse())

let r2 = StringSetReverse.add “do” (StringSetReverse.add “re” (StringSetReverse.add “mi” StringSetReverse.empty))

printfn “%A” r2

 

prints [“ro”;”mi”;”do”].  So by passing the constraint to the constructor we can change the structure our “functor” generates.

 

What Do We Lose?

 

Compossibility.   In the second example our StringSetReverse only exists at runtime.  The following declaration fails.

 

type StringSetReverse = Set<string>(OrderedStringReverse())

 

We cannot make StringSetReverse part of our type system and use it as a type in other areas of our program.  We’ve lost the ability to compose complex types from simpler ones.  How important you consider composing complex types from simple ones will determine how much you feel F# has lost compared to OCaml.

November 23rd, 2008 | Tags: F#, Functors, Interfaces, OCaml, Polymporphism | Category: F#, Functors, OCaml, Polymorphism | Comments (3)

The following page describes in detail the differences between the OCaml and F# languages. It’s a good read for anyone familiar with OCaml and an even better read for those who are not.  For the first line of the summary declares

 

Functors, OCaml-style objects, labels and option arguments are not supported.  Some common functors like Set.Make and Hashtbl.Make are simulated by returning records of functions.

 

Simulating functors by returning records of functions sounds interesting.  Let’s take a closer look at what functors in OCaml are.

 

OCaml Functors

 

Chapter 2 of the OCaml manual has a pretty good example of using functors.  I have to admit that just finding a good example was somewhat of a chore, which suggests either functors aren’t used a whole lot by OCaml programmers or nobody understands them.

 

The example starts by declaring a signature to represent types that are orderable.

 

#type comparison = Less | Equal | Greater;;

type comparison = Less | Equal | Greater

 

#module type ORDERED_TYPE =

   sig

     type t

     val compare: t -> t -> comparison

   end;;

module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end

 

We’ll fall back on our object oriented upbringing and use an interface to model the same signature in F#.

 

type comparison = Less | Equal | Greater

 

type ORDERED_TYPE<’a> =

    abstract t : ‘a

    abstract compare : ‘a -> ‘a -> comparison

 

Now a structure is created for strings. Notice how there is no explicit connection between the structure and the signature.

 

#module OrderedString =

   struct

     type t = string

     let compare x y = if x = y then Equal else if x < y then Less else Greater

   end;;

module OrderedString : sig type t = string val compare : ‘a -> ‘a -> comparison end

 

We have no choice but to explicitly implement our interface signature.

 

type OrderedString(t : string) =

    interface ORDERED_TYPE<string> with

        member me.t = t

        member me.compare x y = if x = y then Equal else if x < y then Less else Greater

 

For those paying attention you’ll see a subtle difference between the two OrderedString declarations.  The F# declaration returns an instance of a string for t instead of the type of string.  In fact, whereas the F# definition appears to be an instance of type the OCaml version appears to be a type of a type.

 

Implementing Set as a Functor

 

The type signature are done, let’s move on to the meat of building our functor.  We’ll start with the signature.

 

module Set :

  functor (Elt : ORDERED_TYPE) ->

    sig

      type element = Elt.t

      type set = element list

      val empty : ‘a list

      val add : Elt.t -> Elt.t list -> Elt.t list

      val member : Elt.t -> Elt.t list -> bool

    end

 

And examine the implementation of the signature piece by piece.

 

#module Set =

   functor (Elt: ORDERED_TYPE) ->

     struct

       type element = Elt.t

       type set = element list

 

So a set is a functor that takes an ordered type as a parameter.  The type is then extracted and stored in the element type.  I have a feeling our F# definition will have to be quite different.

 

type Set<’a,’con> when ‘con :> ORDERED_TYPE<’a> () =

 

And so it is.  With F# we can’t combine the constraint and underlying type as a single parameter.  Unlike OCaml we have no way of extracting the underlying type from the container type.  This results in an unfortunate redundant construction.

 

So the construction of our types are different, let’s analyze the functions.

 

let empty = []

let rec add x s =

  match s with

    [] -> [x]

  | hd::tl ->

     match Elt.compare x hd with

       Equal   -> s         (* x is already in s *)

     | Less    -> x :: s    (* x is smaller than all elements of s *)

     | Greater -> hd :: add x tl

let rec member x s =

  match s with

    [] -> false

   | hd::tl ->

      match Elt.compare x hd with

        Equal   -> true     (* x belongs to s *)

      | Less    -> false    (* x is smaller than all elements of s *)

      | Greater -> member x tl

 

And the corresponding F# implementation.

 

member me.empty : ‘con list = []

member me.add (x : ‘con) (s : ‘con list) =

    let rec add (x : ‘con) (s : ‘con list) =

        match s with

        | [] -> [x]

        | hd::tl ->

            match x.compare x.t hd.t with

            | Equal   -> s         (* x is already in s *)

            | Less    -> x :: s    (* x is smaller than all elements of s *)

            | Greater -> hd :: add x tl

    add x s   

member me.is_member (x : ‘con) (s : ‘con list) =

    let rec is_member (x : ‘con) (s : ‘con list) =

        match s with

        | [] -> false

        | hd::tl ->

            match x.compare x.t hd.t with

            | Equal   -> true     (* x belongs to s *)

            | Less    -> false    (* x is smaller than all elements of s *)

            | Greater -> is_member x tl

    is_member x s

 

The fundamental difference with the F# code is we’re forced to work with the constraint instead of the underlying type.  Because the compare function is only available on instances of ordered types we can only pass those types into our set.

 

The compare function in the OCaml example however is attached to type itself instead of an instance of the type.  Remember how our OCaml structure was more analogous to a type of type rather than an instance of a type?  This allows us to solve problems at the type level instead of always relying on runtime dispatch for polymorphism.

 

Applying the Set Functor

 

So we’ve built a signature for an ORDERED_TYPE.  We’ve created a structure for a string type that implements the signature.  We’ve created a functor called Set that can be applied to the structure.  So let’s finish this off and do the application.

 

#module StringSet = Set(OrderedString);;

module StringSet :

  sig

    type element = OrderedString.t

    type set = element list

    val empty : ‘a list

    val add : OrderedString.t -> OrderedString.t list -> OrderedString.t list

    val member : OrderedString.t -> OrderedString.t list -> bool

  end

 

The application of the functor creates a new set for ordered strings.  We can now use this set with functions that only work with strings.

 

#StringSet.member “bar” (StringSet.add “foo” StringSet.empty);;

- : bool = false

 

The application of our F# “functor” is slightly messier because of the inherent redundancy.

 

let StringSet = Set<string,OrderedString>()

 

And of course we have to wrap our strings in OrderedStrings.

 

let result = StringSet.is_member (OrderedString(“bar”)) (StringSet.add (OrderedString(“foo”)) StringSet.empty)

 

Does F# Compete Against Java or Other Functional Languages

 

Some further tricks with interfaces or a record of functions may solve the problem encountered above, but we continue to get the sense that .Net really just isn’t designed with functional languages in mind.  Here’s another situation where the F# type system doesn’t appear to be up to snuff with a fellow functional friend.  I think most people would agree .Net was created to compete with Java and it shows. 

 

So will this legacy be the stone around F#’s neck that prevents it from ever really being able to compete with Haskell or OCaml?  F# may become a great replacement for C# or Java programs, but will the .Net type system ever evolve to the point where F# can solve problems at the type level?  With the mutable nature of the .Net API’s and the large legacy code base that must be supported, maybe F# would have been better off staying in the lab and forging the way forward for a proper .Net 2.0.

 

Full Source Code

 

#light

 

type comparison = Less | Equal | Greater

 

type ORDERED_TYPE<’a> =

    abstract t : ‘a

    abstract compare : ‘a -> ‘a -> comparison

 

type OrderedString(t : string) =

    interface ORDERED_TYPE<string> with

        member me.t = t

        member me.compare x y = if x = y then Equal else if x < y then Less else Greater

       

type Set<’a,’con> when ‘con :> ORDERED_TYPE<’a> () =

    member me.empty : ‘con list = []

    member me.add (x : ‘con) (s : ‘con list) =

        let rec add (x : ‘con) (s : ‘con list) =

            match s with

            | [] -> [x]

            | hd::tl ->

                match x.compare x.t hd.t with

                | Equal   -> s         (* x is already in s *)

                | Less    -> x :: s    (* x is smaller than all elements of s *)

                | Greater -> hd :: add x tl

        add x s

    member me.is_member (x : ‘con) (s : ‘con list) =

        let rec is_member (x : ‘con) (s : ‘con list) =

            match s with

            | [] -> false

            | hd::tl ->

                match x.compare x.t hd.t with

                | Equal   -> true     (* x belongs to s *)

                | Less    -> false    (* x is smaller than all elements of s *)

                | Greater -> is_member x tl

        is_member x s

 

//By applying the Set functor to a structure implementing an ordered type, we obtain set operations for this type

let StringSet = Set<string,OrderedString>()

let result = StringSet.is_member (OrderedString(“bar”)) (StringSet.add (OrderedString(“foo”)) StringSet.empty)

 

printfn “%A” result

System.Console.ReadLine()

November 20th, 2008 | Tags: F#, Functors, Interfaces, OCaml, Types | Category: F#, Functors, OCaml | Comments (6)

The map function is one of the most useful functions in all of functional programming.  Pass a function, a list of arguments, apply the function to each argument, and return a new list of the results.

 

let list = [1;2;3;4;5]

let f1 = (fun a -> a)

let alist = List.map f1 list

 

>[1;2;3;4;5]

 

The map2 function does basically the same thing, except the function takes two arguments, hence we need two lists of arguments.

 

let list = [1;2;3;4;5]

let f2 = (fun a b -> a + b)

let alist2 = List.map2 f2 list list

 

>[2;4;6;8;10]

 

And I bet you can guess what the map3 function does.

 

let list = [1;2;3;4;5]

let f3 = (fun a b c -> a + b + c)

let alist3 = List.map3 f3 list list list

 

>[3;6;9;12;15]

 

But now we’ve got a problem for there is no Map4 function.

 

Extending the Map3 Function

 

The basic idea here is to put an end to the continued definitions of Map functions.  Let’s see if we can “extend” the Map3 function to take one more argument list.  Something like the following would be great.

 

let f4 = (fun a b c d -> a + b + c + d)

let alist4 = List.map3 f4 list list list << list

 

Where the << operator is defined as

 

let rec (<<) f a =

    match f, a with

    | fh :: ft, ah :: at -> fh ah :: (ft << at)

    | _ -> []

 

We pass a list of functions, and the next list of arguments to apply the function to.  For our f4 function we will have already applied f4 for the a b and c arguments by the time we use our << operator.  So after the use of our operator we’re left with

 

>[4;8;12;16;20]

 

And if you think about it, there’s not really any reason for the Map2 or Map3 functions.  Let’s “extend” our Map function for a function requiring 5 bound variables.

 

let f5 = (fun a b c d e -> a + b + c + d + e)

let alist5 = List.map f5 list << list << list << list << list

 

>[5;10;15;20;25]

 

Introducing Parametric Numerals

 

The above use of the << operator is ok.  It solves our problem of having to continually define Map functions, but it’s not very readable.  What if a very complex calculation requires 18 bound variables? Do you really want to count up the instances of << ? And wouldn’t it be great if there was a way to constrain the map function to precisely the number of bound varaibles you require in the first place?

 

Let’s define some parametric numerals.

 

let succ n fl al = n (fl << al)

let zero al = al

let one n a = succ zero n a

let two n a b = succ one n a b

let three n a b c = succ two n a b c

let four n a b c d = succ three n a b c d

let five n a b c d e = succ four n a b c d e

 

And a new map function that can use them.

 

let mapWith n f l = n (List.map f l)

 

Our map function suddenly becomes very readable and constrained to exactly the number of bound variables we require.

 

let blist = mapWith zero f1 list

let blist2 = mapWith one f2 list list

let blist3 = mapWith two f3 list list list

let blist4 = mapWith three f4 list list list list

let blist5 = mapWith four f5 list list list list list

 

The first parameter requires a parametric numeral that states how many additional bound variables our mapWith function requires.

 

let blist5 = mapWith four f5 list list list list list

 

can be read as map with four additional bound variables, if we try to write

 

let blist5 = mapWith four f5 list list list list list list

 

then the compiler catches the error of our ways.  Pretty handy!

 

An Odd Argument Indeed

 

The first argument to our mapWith function really is an odd argument.  Unlike traditional variables, which act as placeholders, it encodes information about how the function should behave.  We’ll take more in depth look at these “odd arguments” next time.

 

The ideas in the blog come from the following paper, which is a pretty easy read.

November 15th, 2008 | Tags: Dependent Types, F#, Map Function, Parametric Numerals | Category: Dependent Types, F# | Comments (2)

We used a good old fashioned subtyping and a dash of parametric polymorphism to write an eval function capable of returning different types.  But surely we gave up too easily on polymorphic return types in F#?  I assure you we gave them the ol’ college try.

 

Polymorphic Return Types Take 1

 

Let’s start with a pretty simple data constructor that constructs two different types.

 

type Term =

    | Int of int

    | Char of char

 

Now we write a rather straightforward eval function to evaluate our terms.  For instance,

 

// Term -> int

let eval t =

    match t with

    | Int i -> i

    //the expression has type char but here is used with type int

    | Char c -> c

 

But because our first match returns an integer our second must also return a char.

 

Polymorphic Return Types Take 2

 

Just because the compiler doesn’t like what you’re trying to do doesn’t mean it isn’t right.  Let’s take a different tact.

 

// Term -> obj

let eval t =

    match t with

    | Int i -> i :> obj

    | Char c -> c :> obj

 

let i = eval (Int 1)

let c = eval (Char ‘c’)

printfn “%A” i

printfn “%A” c

 

So we sacrifice our type safety to get a couple of values printed to the console.  Not what we had in mind.  We want the type system to guide us instead of forcing us to throw it out the window.

 

Polymorphic Return Types Take 3

 

So if we can’t return a different type and we don’t want to lose our type safety, let’s try returning all possible types.

 

// Term -> Choice<int,char>

let eval t =

    match t with

    | Int i -> Choice2_1 i

    | Char c -> Choice2_2 c

 

let i = eval (Int 1)

let c = eval (Char ‘c’)

 

So our eval function compiles and returns a different choice for each constructor.  All we have to do now is extract the value out of the choice and were done.

 

// Term -> Choice<’a,’a>

let extract choice =

    match choice with

    | Choice2_1 i -> i

    | Choice2_2 c -> c

// expecting a Choice<int,int> but given a Choice<int,char>

let i = extract (eval (Int 1))

 

And if we annotate the choice function we’ve just reinvented our original problem.

 

// Term -> Choice<int,char> -> int

let extract_int_char (choice : Choice<int,char>) =

    match choice with

    | Choice2_1 i -> i

    //the expression has type char but here is used with type int

    | Choice2_2 c -> c

 

Polymorphic Return Types Take 4

 

Let’s start with a function that does work.

 

// Term -> unit

let display t =

    match t with

    | Int i -> printfn “%A” i

    | Char c -> printfn “%A” c

 

Now can’t we somehow lift the variables out of the function without changing the return type?  Something along the lines of. 

 

// Term -> ‘a ref -> unit

let eval t r =

    match t with

    | Int i -> r := i

    //the expression has type char but here is used with type int

    | Char c -> r := c

 

Only to be thwarted again and all we’re left with to get our values out of eval function is the following monstrosity.

 

// Term -> int ref -> char ref -> unit

let eval t ri rc =

    match t with

    | Int i -> ri := i

    | Char c -> rc := c

 

let ri = ref 0

let rc = ref ‘a’

let ie = eval (Int 1)

let u1 = eval (Int 1) ri rc

let i = !ri

let u2 = eval (Char ‘c’) ri rc

let c = !rc

printfn “%A” i

printfn “%A” c

 

Eat your heart out Perl.  We’ve got a new write once kid on the block.

November 12th, 2008 | Tags: Choice, F#, Polymorphism, Reference Cells, Return Types | Category: F#, Polymorphism | Comments (5)

So we know how to use a type parameter to statically constrain the length of a list.  Let’s continue our exploration of type constraints and see if we can figure out how to constrain the return type of a data constructor.

 

Data Constructor Constraints in Haskell

 

The paper “Fun with Phantom Types” by R Hinze has an example of a simple expression language in Haskell.

 

data Term t = Zero

            | Succ(Term Int)

            | Pred(Term Int)

            | IsZero(Term Int)

            | If (Term Bool) (Term t) (Term t)

 

What we’d like to be able to do with this language is have the interpreter statically catch any type errors.  For instance,

 

Main>let one = Succ(Zero)

Main>eval IsZero(one)

 

is a type safe declaration because IsZero can take a Term Int, whereas

 

Main>IsZero(IsZero one)

 

is not type safe because IsZero does not take a Term Bool.  Hinze suggest the following ‘mild’ extension for Haskell.

 

data Term t = Zero                             with t = Int

            | Succ(Term Int)                   with t = Int

            | Pred(Term Int)                   with t = Int

            | IsZero(Term Int)                 with t = Bool

            | If (Term Bool) (Term a) (Term a) with t = a

 

What the extension does is constrain each type constructor to returning a Term of the type specified after the with keyword.  Let’s see how we could do this in F#

 

Data Constructor Constraints in F#

 

We’ll start by building a discriminated union to construct our Term.

 

type Term<’t> = Zero

              | Succ of Term<int>

              | Pred of Term<int>

              | IsZero of Term<bool>

              | If of Term<bool> * Term<’t> * Term<’t>

 

And let’s examine the types when we use our union.

 

// val one : Term<’a>

let one = Succ(Zero)

// val is_false : Term<’a>

let is_false = IsZero(one)

// val is_problem : Term<’a>

let is_problem = IsZero(IsZero(one))

 

Notice how each of our bound variables gets assigned the type Term<a>?  What we would prefer is for the F# compiler to constrain the return type of the constructor to a designated type. This would allow the compiler to catch the type error on line 3.  An IsZero can only accept Term<int> and here we’re passing it a Term<bool>. 

 

So if we can’t fool the compiler at link time then let’s at least force a runtime exception.

 

let rec eval (t : Term<’a>) =

    match t with

    | Zero         -> 0

    //this code causes the construct to be less generic than the annotation

    | Succ e       -> eval e + 1

    | Pred e       -> eval e - 1

    //the expression has type bool but here is used with type int

    | IsZero e     -> eval e = 0

    | If(e1,e2,e3) -> if eval e1 then eval e2 else eval e3         

 

No such luck.  The match on Succ constrains t to Term<int> which prevents us from passing e to the eval statement at the IsZero match.  The type inference algorithm does not allow for polymorphic inputs or outputs to functions.  Why not?  Remember from this blog entry that “match” functions get compiled down into standard .Net methods.  So what language does allow for polymorphic return types?

 

Data Constructor Constraints in VB

 

Let’s dust off our old standby and see if it can’t teach the Haskell and F# prodigies a lesson on problem solving.

 

Public MustInherit Class Term(Of TEval)

    Public MustOverride Function Eval() As TEval

End Class

 

Public Class Succ

    Inherits Term(Of Integer)

    Private _e As Term(Of Integer)

    Public Sub New(ByVal e As Term(Of Integer))

        _e = e

    End Sub

    Public Overrides Function Eval() As Integer

        Return _e.Eval + 1

    End Function

End Class

 

Public Class IsZero

    Inherits Term(Of Boolean)

    Private _e As Term(Of Integer)

    Public Sub New(ByVal e As Term(Of Integer))

        _e = e

    End Sub

    Public Overrides Function Eval() As Boolean

        Return _e.Eval = 0

    End Function

End Class

 

The constructor for each of our terms does allow us to constrain the type of term that can be used to construct the term.  The TEval type constraint further lets us constrain the type that gets returned when the type is evaluated.

 

All we’ve done is break our constructor and eval function out over each term.  Because each term has its own slot in the virtual method table our “broken out” function can return a different type depending upon the match.  It seems odd that F# does something very similar to the above when building discriminated unions but chooses to combine the eval function into a single function instead of making the match code local to each term.

 

//why is the code to right of the -> not encapsulated in each term?

let rec eval (t : Term<’a>) =

    match t with

    | Zero         -> 0

    | Succ e       -> eval e + 1

    | Pred e       -> eval e - 1

    | IsZero e     -> eval e = 0

    | If(e1,e2,e3) -> if eval e1 then eval e2 else eval e3         

 

Because if it was then we’d realize the benefits of static checking for our domain specific expression languages just like the terms we constructed in VB.

 

// val one : Succ

let one = Succ(Zero())

// val is_false : IsZero

let is_false = IsZero(one)

// the type IsZero is not compatible with the type int

let is_problem = IsZero(IsZero(one))

 

Thanks for figuring that out for me compiler!  Kind of nice to see our trusty, Von Neumann, hacker language for Morts teach our lambda friends a lesson in how to do type safe domain specific languages.

 

Full Source Code

 

Public MustInherit Class Term(Of TEval)

    Public MustOverride Function Eval() As TEval

End Class

 

Public Class Zero

    Inherits Term(Of Integer)

    Public Sub New()

    End Sub

    Public Overrides Function Eval() As Integer

        Return 0

    End Function

End Class

 

Public Class Succ

    Inherits Term(Of Integer)

    Private _e As Term(Of Integer)

    Public Sub New(ByVal e As Term(Of Integer))

        _e = e

    End Sub

    Public Overrides Function Eval() As Integer

        Return _e.Eval + 1

    End Function

End Class

 

Public Class Pred

    Inherits Term(Of Integer)

    Private _e As Term(Of Integer)

    Public Sub New(ByVal e As Term(Of Integer))

        _e = e

    End Sub

    Public Overrides Function Eval() As Integer

        Return _e.Eval - 1

    End Function

End Class

 

Public Class IsZero

    Inherits Term(Of Boolean)

    Private _e As Term(Of Integer)

    Public Sub New(ByVal e As Term(Of Integer))

        _e = e

    End Sub

    Public Overrides Function Eval() As Boolean

        Return _e.Eval = 0

    End Function

End Class

 

Public Class [If](Of TEval)

    Inherits Term(Of TEval)

    Private _e1 As Term(Of Boolean)

    Private _e2 As Term(Of TEval)

    Private _e3 As Term(Of TEval)

    Public Sub New(ByVal e1 As Term(Of Boolean), ByVal e2 As Term(Of TEval), ByVal e3 As Term(Of TEval))

        _e1 = e1

        _e2 = e2

        _e3 = e3

    End Sub

    Public Overrides Function Eval() As TEval

        If _e1.Eval Then

            Return _e2.Eval

        Else

            Return _e3.Eval()

        End If

    End Function

End Class 

 

#light

 

open TermVB

 

let one = Succ(Zero())

let i = one.Eval()

printfn “%A” i

 

let i1 = IsZero(one).Eval()

printfn “%A” i1

 

// the type IsZero is not compatible with type Term<int>

//let i2 = IsZero(IsZero(one))

 

let i3 = If(IsZero(one),Zero(),one).Eval()

printfn “%A” i3

 

let True = IsZero(Zero())

let False = IsZero(one)

let t1 = If(True,True,False).Eval()

printfn “%A” t1

 

System.Console.ReadLine()

November 11th, 2008 | Tags: F#, Haskell, Paramtric Polymorphism, Pattern Matching, Subtype Polymorphism, Type Constraints, VB | Category: F#, Haskell, Pattern Matching, VB | Comments (4)