by ·1 Comment

So here we are at part 2 in the series of posts looking at Functional Data Structures from the book of the same name by Chris Okasaki. Last time we looked at what is perhaps the simplest of the functional data structures, the List (also useful as a LIFO stack).  Up next we’ll continue in the order that Chris Okasaki used in his book, and take a look at implementing a Set using a Binary Tree.

Diving right in, here is implementation for a Set using a binary tree in F#:

module Set

    type Tree<'a when 'a:comparison> =
        | Empty
        | Tree of Tree<'a>*'a*Tree<'a> 

    let rec isMember value tree =
        match (value,tree) with
        | (_,Empty) -> false
        | (x,Tree(a,y,b)) ->
            if value < y then
                isMember x a
            elif value > y then
                isMember x b
            else
                true

    let rec insert value tree = 
        match (value,tree) with
        | (_,Empty) -> Tree(Empty,value,Empty)
        | (v,Tree(a,y,b)) as s -> 
            if v < y then
                Tree(insert v a,y,b)
            elif v > y then
                Tree(a,y,insert v b)
            else
                snd s

This is pretty simple, like the List we’re working with a Discriminated Union, this time with an Empty, and then a Tree that is implemented using a 3-tuple (threeple?) with a Tree, an element, and a Tree. There is a constraint on the elements that ensures they are comparable, since this is going to be an ordered tree.

We only have two functions here, one isMember, which says whether or not the element exists in the set, and the other insert, which adds a new element. If you look at the isMember function, its not too difficult, a recursive search of the tree attempting to find the element. Since this is a sorted tree, each iteration will compare the element being searched for with the element in the current node of the tree. If its less than the current node we follow the right-hand side of the tree, otherwise we follow the left-hand side of the tree. If we find an empty tree, the element doesn’t exist. Update is a little more difficult…it’s recursive like isMember, but it is also copying some of the paths. The bits that are copied are the bits that are not being traversed, so in reality the majority of the tree returned from the update function is actually shared with the source tree, its root is just new. Take a hard look at that for a moment, and see if the pain begins to subside…then we’ll look at the C# version.

public static class Tree
{
    public static EmptyTree<T> Empty<T>() where T: IComparable
    {
        return new EmptyTree<T>();
    }
}

public class EmptyTree<T> : Tree<T> where T: IComparable
{
    public override bool IsEmpty { get { return true; }}
}

public class Tree<T> where T: IComparable
{
    public Tree<T> LeftSubtree { get; internal set; }
    public Tree<T> RightSubtree { get; internal set; }
    public T Element { get; internal set; }
    public virtual bool IsEmpty
    {
        get { return false; }
    }
}

public static class Set
{
    public static bool IsMember<T>(T element, Tree<T> tree) where T: IComparable
    {            
        if (tree.IsEmpty)
            return false;
        var currentElement = tree.Element;
        var currentTree = tree;
        while(!currentTree.IsEmpty)
        {
            if (element.CompareTo(currentElement) == 0)
                return true;
            if (element.CompareTo(currentElement) == 1)
            {
                currentTree = currentTree.RightSubtree;
            }
            else
            {
                currentTree = currentTree.LeftSubtree;
            }
            currentElement = currentTree.Element;
        }
        return false;
    }

    public static Tree<T> Insert<T>(T element, Tree<T> tree) where T: IComparable
    {
        if (tree.IsEmpty)
            return new Tree<T> { LeftSubtree = Tree.Empty<T>(), Element = element, 
                                 RightSubtree = Tree.Empty<T>() };
        switch(element.CompareTo(tree.Element))
        {
            case 0:
                return tree;
            case 1:
                return new Tree<T> { RightSubtree = tree.RightSubtree, Element = tree.Element, 
                                     LeftSubtree = Set.Insert<T>(element,tree.LeftSubtree) };
            default:
                return new Tree<T> { LeftSubtree = tree.LeftSubtree, Element = tree.Element, 
                                     RightSubtree = Set.Insert<T>(element, tree.RightSubtree) }; 
        }
    }
}

This is a reasonable chunk of code, so lets work it from the top down. We start off by defining the Tree data structure. We use inheritance in this case to make an Empty tree, since we don’t have Discriminated Unions in C# (If I were a good person I would update that right now to return a singleton of the EmptyTree class, but alas, I’m lazy). The Static Tree class provides the convenience method for creating the empty tree, and the Tree type is our parameterized tree.

The methods in the Set class do the work of checking for an existing member in the set, and inserting a new member in the set.  I took the opportunity to convert the recursive isMember function to a looping construct in C# (which is what the F# compiler will do for you).  This is not really possible with the Insert method because it is not tail recursive.  The logic is the same in both versions, but the C# version is a bit more verbose (though having LeftSubtree and RightSubtree makes things a little clearer in my opinion).  Again, the biggest difference between the two is the amount of code (since we don’t have Discriminated Unions and Pattern Matching in C# land)

Summing Up Persistent Structures

Interestingly this is where the first section of Okasaki’s book ends (Its actually chapter 2, but chapter 1 is more of a foundational thing…no code).  These two implementations show the basic ideas behind what are described as “Persistent” data structures…meaning bits of the structures are re-used when creating new structures are part of an operation that would mutate the original structure in a non-functional (mutable) data structure.  In the case of a List/Stack we are referencing the old list as the “Tail” of the new list, so each time we add a new item we are simply allocating space for the new item.  In the case of the Tree/Set we create a new root tree on Add, and then reference all paths except for the new node that gets added (or, if the item already exists, we just have the new root…this is actually something Okasaki suggests the reader should solve as an additional exercise).  These concepts are fundamental to the more complex data structures that fallow, and present the basic ideas that are employed to make the structures efficient within the context of functional programming.

Up next in the book is a look at how more traditional data structures, such as heaps and queues, can be converted to a more functional setting.  Expect more goodness in the area, but I would also like to revisit some of the basics here.  The more observant readers may have noticed that the majority of the functions used on these simple types were not Tail Recursive, which means the compiler and JIT cannot optimize them, which ultimately means they are going to cause your stack to blow up if you’re dealing with large structures.  It might be worth exploring how to go about converting these to make them Tail Recursive.

by ·1 Comment

I thought it might be fun to explore a little bit of CS as it applies to functional programming, by looking at the idea of Functional Data Structures.  This is actually an area that is still getting a lot of active research, and is pretty interesting stuff overall.  The general idea is to try and figure out ways to provide immutable data structures which can be efficiently implemented in a functional setting.  So you look at some standard data structures, like a linked list, and find a way to implement that as an immutable linked list.  One of the really cool features of Functional Data Structures is that because your dealing with them in an immutable setting, you can actually get a lot of re-use out of them….specifically for something like a list, you can add an item to the list, and return a “new” list that consists of the old list and the new item, and literally provide a structure that points to the old list instead of copying items.  Even if you have other parts of the code referencing older versions of the list without the new item, you don’t have to worry since none of them can mutate the list.

The biggest body of research on this topic was published by Chris Okasaki in 1998, and is still the definitive reference on the subject today.  Just for fun I’m going to look at some of the structures discussed in the original book and see what the implementations would look like in F# and C#.  The original text provided samples in Standard ML, with an eppendix containing Haskell versions.  I won’t go into too much depth on the theory behind the structures, but I will try to point out the interesting bits.

Without further ado, lets get rolling with our first data structure, which is also Okasaki’s first: Lists

Specifically, we’re going to implement a singly-linked list, which can be used rather effectively as a LIFO stack.  To start off lets look at the F# version of the list, which is closest to what Okasaki listed in his book.  The basic list type looks like this:

type List<'a> =
| Empty
| Cons of 'a * List<'a>

This is a simple Discriminated Union, with two options, Empty, and something I’ve called Cons in honor of the Lisp folks. The Cons option is basically a tuple containing an element of type type ‘a, and a List of ‘a.  This by itself is reasonably uninteresting, so lets actually do something with this.

let isEmpty = function
    | Empty -> true
    | _ -> false

let cons head tail= Cons(head,tail)

let head = function
    | Empty -> failwith "Source list is empty"
    | Cons(head,tail) -> head

let tail = function
    | Empty -> failwith "Source list is empty"
    | Cons(head,tail) -> tail

let rec (++) leftList rightList = 
    match leftList with
    | Empty -> rightList
    | Cons(head,tail) -> Cons(head,tail ++ rightList)

let rec update list index value =
    match (list,index,value) with
    | (Empty,_,_) -> failwith "Source list of empty"
    | (Cons(_,tail),0,v) -> Cons(v,tail)
    | (Cons(_,tail),i,v) -> update tail (i - 1) v

Here we have some basic functions, an isEmpty check, a cons method (which creates a list), the head and tail functions, along with a ++ function, which appends two lists, plus an update method which changes the value of a particular element in the list.  Notice the update and ++ functions are both recursive, and in the case of the ++ function, it is not tail recursive. This is probably ok in this case since the performance of the ++ function is O(n) where n = length of the left list.  Both of these functions are also interesting because the F# compiler is unable to optimize them by converting them into a loop.

If we look at the C# version of these same structures things look pretty much the same:

public static class List
{
    public static List<T> Empty<T>()
    {
        return new EmptyList<T>();
    }

    public static List<T> Cons<T>(T head, List<T> tail)
    {
        return new List<T> { Head = head, Tail = tail };
    }
}
public class EmptyList<T> : List<T>
{
    public bool IsEmpty { get { return true; } }
}

public class List<T> : List
{
    public T Head {get; set; }
    public List<T> Tail {get; set; }

    public bool IsEmpty 
    {
        get { return false; }
    }

    public List<T> Update(int index, T value)
    {
        if(this.IsEmpty)
            throw new InvalidOperationException("You can't update an empty list");
        if(index == 0)
            return List.Cons<T>(value,this.Tail);
        return this.Tail.Update(index - 1, value);

    }

    public static List<T> operator +(List<T> leftList, List<T> rightList)
    {
        if(leftList.IsEmpty)
            return rightList;

        return List.Cons<T>(leftList.Head, leftList.Tail + rightList);
    }
}

Other than being almost twice as long, there are not many differences between the C# version of this structure and the F# version In this version I’ve opted to make the empty list a subclass of the List that has the IsEmpty property return true all the time.  There is also a static Empty<T>() method which returns an empty list.  A reasonable improvement could be to make this a singleton, so that empty lists would also share reference equality. Since the ++ operator in C# is not overloadable (and is a unary operator to boot) I’ve used an overload of the + operator for concatenating two lists.  The implementations are the same as the F# versions, though honestly recursion is a little strange in C#.  We still have the same performance characteristics, where appending an element is an O(n) operation, We also have the same issues with recursion, namely a stackoverflow if we have a large enough list.  Though, honestly with the performance of the update operation overall, you should probably find a new structure before you get to the point where your going to overflow your stack.

One very nice use for this particular structure is the LIFO stack.  Rather than the typical “push” and “pop” operations, we have the “cons” and “head”/”tail” operations (in the case of pop, you have “head” which gives you the elements, and “tail” which gives you the rest of the list).  This works well because pushing and popping are O(1).  This structure is not all that different than the built-in List type in F#, without the benefit of the additional functions (filter, map, tryFind, etc).  Thought it would be reasonably trivial to implement these in a recursive fashion.

 

That’s it for this segment…up next we’re going to look at using an immutable binary tree to implement a Set….good stuff for sure.

by ·0 Comments

As you may have guessed from the title, I’ve started doing some work with F#.  Initially I was somewhat reluctant to go down the F# path because some of the more interesting aspects of the other functional languages I’ve been exploring are not present…specifically the type systems behind Scala and Haskell, the laziness of Haskell, and the concurrent programming model of Erlang.  In spite of these perceived downfalls, there were some definite plusses, namely interoperability with everything .Net, immutability by default, and the wonderful concise programing model of a functional language.

So with these benefits in mind I set about figure out what F# was all about.  The language itself is based strongly on OCaml, and I’ve not had any experience with OCaml, so I was unsure what to expect.  I decided to find a book on the subject, and I wish I could tell you for sure which one it was, but it was long ago, and for some reason when I look at all of the F# books on Safari none of them seem to fit the bill…The closest seems to be Expert F# 2.0, so we’ll assume that one was it for now.  Regardless, I read the entire thing over the course of about 3 days (started on a Friday, and had made my way through by Sunday).  I didn’t go through any exercises, or really try to write any code along the way, since I really just wanted to figure out what the language was all about.  I should point out that I’ve tried at least once before to make my way through an F# book, and didn’t have much luck…this time round it was smmoooooth.  I think the biggest reason was that I already had a pretty solid grasp of the core concepts in functional languages.  Things like functional composition, pattern matching, and working with immutable data types are central to just about every functional language, and F# is no different, so my learning experience was really just a matter of mapping those concepts onto the correct syntactic elements in my head.  By the time it was all over I felt pretty comfortable with the basics of the language.

Shortly after reading the book I decided to actually try writing something real and useful…this proved to be a bit more of a challenge.  There are a few reasons for this…a big part was that organizing a functional project is different than organizing an OO project.  This was complicated by the fact that the first task I set myself on was re-writing something I had in C# in F#.  This was supposed to be more than just a syntactic translation, but also an attempt to see if my hunch that the problem being solved was effectively a functional problem, and so would lend itself well to a real functional language.  The problem was I was used to thinking about the problem in terns of the classes I had already created, and in F# those concepts were not there.  Before long, though, I had adjusted my thinking, and the more time I spent working on the problem the more I found myself enjoying F#.  After that initial experience (which was mostly academic, in that it was not intended to go “live”) I found myself wanting to explore more with the language, and so I’ve been looking for reasons to use it.  I’m not going to go into all of the ways I’ve managed that here, but I did want to share some observations:

  • My initial reluctance based on the perceived drawbacks were largely my own naivety.  While it is true that there are no higher-kinded types, and therefore no type constructors, this does not make the programing experience that much worse.  Granted there are some kinds of things that will be duplicated, which folks using Haskell would be able to do away with by harnessing the power of the type system, but this does not make F# useless by any stretch.  As a matter of fact F# exposes some capabilities of the CLR that C# does not, including being able to specify wildcard types, which allow you to say “I have a parameterized type, but I don’t care about the specific type of the parameter”, and even some Structural Typing, which provides a way to constrain types by specifying the methods those types should have.
  • The let construct is deceptively simple when you first encounter it.  Initially it seems like just a way to specify a variable or function name…it becomes interesting though when you realize that the fact that there is a single construct for both means that the two are effectively the same thing. Combine with this the fact that they can be nested, and you have an extremely versatile construct.  I assume this comes directly from the OCaml heritage of F#
  • Pattern matching is just awesome.
  • Working with Object Oriented concepts is jarring, and feels….awkward.  I have no proof, but I can’t help but think this is intentional. While F# is not a “pure” language like Haskell, it still tries to be “functional by default”.  The standard types that you work with all the time, like tuples and lists, are immutable, as are the let bindings.  You have to be specific if you want the mutable versions of any of these.  I can’t help but think the fact that it is easier (or should I say more natural) to work with pure functional types and immutable data structures is a design feature of the language.

The biggest problem I have with F# at this point is that it is clear that it is still a second-class citizen in the VisualStudio world.  While it shipped with VS 2010, a lot of the other tooling doesn’t support it.  Things like the built in analysis tools, just don’t work.  Even the syntax highlighting is less impressive than C#.  There is also the fact that there are no built-in refactorings for F#.  Event third-party tools like Resharper and CodeRush don’t have support.  This is really sad, since the language itself is really a joy to work with.  There is still a perception that it is largely academic, and you can’t do any real work in it.  This is unfortunate, since in our normal day-to-day programming lives there are some problems that are just functional in nature.  In general, functional programing is all about asking questions and getting answers.  Contrast this with OO, which stresses a “Tell don’t ask” paradigm.  If you divide your application into sections which are suited to “telling” vs “asking” then you may find that you can write certain parts functionally very easily, and others OO equally easy.  Wouldn’t it be amazing if people started choosing their languages based on the nature of the problem to be solved, rather than simply because “I’m a C# developer”.