Implementing a Stack in F#. Tail Recursion.

Since Push requires stacks to manipulate its data, we need an implementation of this data structure. There is of course a .NET implementation, however, it is not a “functional” data structure, in a sense that it is mutable. It is easy enough to implement our own, purely functional, immutable stack.

F# list is a logical choice for an underlying implementation. It derives from Seq (i.e. implements all IEnumerable flavors), has a useful length property which we would like to have for our stack as well:

    [<StructuredFormatDisplay("{StructuredFormatDisplay}")>]
    type Stack<'a> = 
        | StackNode of 'a list
        with
            member private t.StructuredFormatDisplay = 
                if t.length = 0 then "()"
                else
                    let str = t |> Seq.fold (fun st e -> st + e.ToString() + "; ") "("
                    str.Substring(0, str.Length - 2) + ")" 

            member t.length =
                t |> Seq.length

            member internal t.asList = 
                match t with StackNode(x) -> x

            member t.isEmpty = t.length = 0

            interface IEnumerable<'a> with
                member x.GetEnumerator() = (x.asList |> List.toSeq).GetEnumerator()

            interface IEnumerable with
                member x.GetEnumerator() =  (x.asList |> List.toSeq).GetEnumerator() :> IEnumerator

What remains is to implement basic operations, which are all static members of the Stack module.

    let peek = function
        | StackNode([]) -> Unchecked.defaultof<'a>
        | StackNode(hd::tl) -> hd
 
    let pushStack hd tl = 
        match tl with
        |StackNode(x) -> StackNode(hd::x)
 
    let pop = function
        | StackNode([]) -> Unchecked.defaultof<'a>, StackNode([])
        | StackNode(hd::tl) -> hd, StackNode(tl)
    

These are pretty straightforward. pop function has a slight quirk: we would like to return both the value of the head of the stack as well as “the rest” of the stack. So the return type in this case is a tuple.

Another slight irregularity: stack functions work on any kinds of instantiated stack object. pop would return something even if the stack is empty. This is done to conform to the Push language “absolute robustness” rule. A syntactically correct program is guaranteed to execute.

A noteworthy function is popMany. Its implementation shows off a cool feature of functional languages: tail call elimination. Any recursive function, where a call to itself produces a return value which is then immediately returned, is called tail recursive. F# optimizes tail recursive functions by handling recursive calls on the same stack frame as the tail call itself (rather than creating a new stack frame for each recursive call). This normally means significant performance advantages, not to mention eliminates any danger of running out of stack.

   let popMany n (stack : Stack<'a>) =
        let noopReturn = [], stack
        if stack.length = 0 then noopReturn
        else
            match n with
            | x when x <= 0 || stack.length < n -> noopReturn
            | x -> 
                let rec popManyTail n st acc =
                    match n with
                    | 0 -> acc   // exit recursion
                    | _ -> 
                        let hd, tl = List.head st, List.tail st
                        popManyTail (n - 1) tl (hd::fst acc, StackNode(tl)) //keep track of intermediate results
                popManyTail n stack.asList ([],empty) // call the actual worker function

It is very easy to write tail-recursive functions by accumulating results(when tail recursion is possible). Here is the pattern:

1. Identify recursion exit (in this case – nothing more needs to be popped off the stack).
2. Carry the accumulated result as part of the method signature: in this case, the function keeps track of the results of its intermediate calls by adding these results to the accumulator argument of popManyTail, which it eventually returns.
   The accumulator is of type: ‘a list * Stack<‘a>. The list of popped values (in reverse order of their position on the stack) is combined with the remainder of the stack in a tuple.
3. Call the actual tail recursive function with the seed value of the accumulator

In our implementation, we handle the edge cases of popMany first and then write the tail recursive function without worrying about anything going wrong.