## 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:

- Identify recursion exit (in this case – nothing more needs to be popped off the stack).
- 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. - 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.

Reblogged this on A Journey Through Code.