Introduction

In an Earlier Article I implemented a stack in C#, an OO first language. Here I will implement the same structure in a functional first language, F#.

For those not familiar with F#, it is part of the ML family of languages which have existed almost as long as C. F# originated within Microsoft so is a .NET language but has been open sourced and given to its community, the F# Software Foundation now manage and maintain it.

It is described as a functional first languagen meaning it's intended to be used in a functional style but has full access to the mutable world of the .NET platform and all the libraries that has. It is also fully cross platform via Mono.

Stacks

Image by Maxtremus - Own work, CC0

To recap stacks, they are a simple LIFO (Last In First Out) structure, you push values onto them and pop them off again. The values are popped off in the reverse order to how they were added. Hence LIFO.

You can refer to my previous article for a bit more detail, linked above. That said the API breakdown in the following section should detail everything.

Right into the code

Time to jump right in. I will break the stack down line by line, all 5 lines of the implementation.

type stack<'a> = {value: 'a Option; count: int; next: stack<'a> Option}

This defines my storage for the stack, a simple linked list that tracks its size. Carries the value or nothing, running count and either the previous item or nothing.

I have used the Option type to manage if value and next contain something or not, similar in nature to a nullable type but far more explicit about it.

let emptyStack = {value = None; count = 0; next = None}

This is the stack you start all new stacks from. It has no value, no tail stack and a count of 0, as the name implies an empty stack.

let push v s = {value = Some v; count = s.count + 1; next = Some s}

Push takes in a value followed by the stack push onto, the order of the arguments is very important. By putting the stack as the last argument we can pipe operations together with the pipeline operator |> as you will see later. It returns a new stack with the supplied value as the new head.

Before I go any further I need to point out, all these function definitions are statically typed! F# type inference is really good, it knows v must be an `a Option and s is a stack.

let pop s = match s.next with | Some next -> next | None -> s

Pop disposes of the current head by returning the tail as the new stack. This is an example of being forced to handle Option. stack.next can be a Some of the stack tail or None. If it is None I return the same stack given, nothing to pop so you get the same stack back.

let isEmpty s = s.count = 0

Check if the stack is empty. So clean and noise free :)

So that is it, just 5 lines of code.

type stack<'a> = {value: 'a Option; count: int; next: stack<'a> Option}
let emptyStack = {value = None; count = 0; next = None}
let push v s = {value = Some v; count = s.count + 1; next = Some s}
let pop s = match s.next with | Some next -> next | None -> s
let isEmpty s = s.count = 0

If you compare this to Building an Immutable Stack in C# you will notice two things:

• The C# code actually looks similar if you strip away all the type information noise in the code, they are the same code. The order of the arguments is swapped though as C# chains functions in a different way.
• This implementation does not throw exceptions while the C# one does. In functional programming you use different ways to handle "fail" cases, you are more honest about it. In pop it was the easiest path was that you can't pop off the end of the stack. In the same way, value being an Option type means that you are forced to handle the no value. F# has powerful tools for this, I will dig into them more in later articles.

And now to test it out, you will see the pipeline operator in action used to chain function calls. The pipeline operator takes the lhs and feeds it as the last argument of the function on the rhs. This nifty little trick is what C# extension methods "simulate" in the way they can be chained together. I feel this is far more honest and flexible about it :)

[<EntryPoint>]
let main argv = 
    // NO mutation at all below

    // = Some 20, Some 10
    let initialStack = emptyStack |> push 10 |> push 20

    // = Some 15, initialStack
    let branch1 = initialStack |> push 15
    let currentValue = branch1.value
    let currentCount = branch1.count 

    // = Some 25, initialStack
    let branch2 = initialStack |> push 25

    // cant pop off the end
    let popAll = branch2 |> pop |> pop |> pop |> pop
    // branch2 still exists untouched

    // = None
    let emptyValue = popAll.value 

    // Here I create a new pop operation that pops the stack
    // it is given 5 times. It has the same signature as pop
    let popDontStop = pop >> pop >> pop >> pop >> pop >> pop

    // So we can do this :)    
    // pop pop pop pop pop
    let flushed = branch1 |> popDontStop

    // End main, return 0
    0 

Hope you enjoyed that short journey into F#. It is an interesting flexible language that is worth learning, let me know if you want to see more in the comments.

Woz