CODEWITHSUNDEEP
f#stackimmutability
Aphex
Aphex

Reputation: 408

Immutable data structures in F#

I am trying to implement a very trivial stack in F# using its built-in generic type. Coming from the imperative paradigm it can sometimes be hard to imagine how to avoid mutability.

What I have so far is a simple data structure with a push and pop operator:

type Stack<'a> =
    | Empty
    | S of 'a list
with
member L.Push x =
    match L with
    | Empty | S ([]) -> S ([x])
    | S (V) ->  S (x :: V)
member L.Pop = 
    match L with
    | Empty | S ([]) -> failwith "Error: Stack is empty"
    | S (v::_) -> v
end

My idea was to make the Stack hold an S of 'a list where we modify the list with the cons :: operator to not mutate the list S, but to replace it with S'. As of now, the stack can at most have one element, and it doesn't grow when pushing elements to it – likewise doesn't shrink when popped.

Can anyone give me a hint on how rewrite the structure/think about it differently?

Thank you!

Upvotes: 1

Views: 472

Answers (2)

David Raab
David Raab

Reputation: 4488

The built-in immutable list is already a valid Stack structure. The Push Operation is :: and you get the last item with Pattern Matching like let (first,rest) = list

If you want to create a Stack from Scratch. Here are some implementations.

1)
a) a stack is either empty
b) or a value and a reference to the previous Stack. 

type Stack<'a> =
    | Empty
    | Value of 'a * Stack<'a>

module Stack =
    let isEmpty = function
        | Empty   -> true
        | Value _ -> false
    let empty = Empty
    let push x stack = Value (x, stack) 
    let pop (Value (x, stack)) = x, stack


let stk =
    Stack.empty
    |> Stack.push 1
    |> Stack.push 2
    |> Stack.push 3

let rec loop stack =
    if   Stack.isEmpty stack
    then ()
    else
        let first, rest = Stack.pop stack
        printfn "First: %d" first
        loop rest

loop stk

You also could choose a record as the underlying data-structure.

type Stack<'a> = {
    Value: 'a option
    Next:  Stack<'a> option
}

This way, a Stack with three elements looks like.

{Value=Some 3; Next=
    {Value=Some 2; Next=
        {Value=Some 1; Next=
            {Value=None; Next=None}}}}

You also could choose a class with a value and next field and use null for the last element.

The important thing is how to work with those structures. The way to work with immutable data-structures is by using recursive functions instead of looping.

Creating a tail-recursive function that visits each element and executes a function on every element is the fold function, comparable to a forEach.

Upvotes: 0

Aron
Aron

Reputation: 9258

You could do this in a more functional way by simply having a list act as the stack. Instead of methods you can make push and pop be functions instead. 

// Returns the new stack
let push item stack = item :: stack

// Returns (item, newStack) tuple or throws if stack is empty
let pop stack =
    match stack with
    | [] -> failwith "Stack is empty"
    | item :: newStack -> item, newStack


// Example usage

let stack = []

let populatedStack = push "hello" stack
// populatedStack = ["hello"]

let item, emptiedStack = pop populatedStack
// item = "hello"
// emptiedStack = []

Upvotes: 5

Related Questions