Simplee.Data 1.0.3

Simplee.Data

Library Simplee.Data v1.0.3 implements operations on common data structures to be used by all other Simple projects. The namespace of the library is Simplee.Data.

Here is the main functionality exposed:

1. Stack free monad
2. Queue free monad
3. Binary tree and Zipper

1. Stack

1.1 The Free Monad

The library exposes a free monad for stack operations. The stack monad comes with 3 instructions:

1. push instruction which pushes a value on top of the stack
2. pushb instruction which pushes a list of values on top of the stack.
3. pop instruction which extracts the value from the top of the stack.
4. popb instruction which extracts a set of values from the top of the stack.
5. peek instruction which returns the value from the top of the stack without removing it from the stack.

The instructions use the error type provided in Simplee.Common package in order to return the evantual failures.

1.2 Computation Builder

This monad is wrapped within stk, a computation expression builder.

The user can construct flows into an imperative way using this builder.

    let flow = stk {
        let! _ = stkpush 10
        let! _ = stkpeek ()
        let! r = stkpop ()
        return r
        }

1.3 Built-in Interpreters

The flows generated with the builder can be interpreted using built-in interpretors. The library provides two interpretors:

1. stklstr - an interpretor that transfors a flow of instructions into a listing.
2. stkim - an interpretor that implements an in-memory stack which can have or not an upper limit.

Here is an example for the stack lister:

    flow
    |> stklst (fun () -> 10)
    |> List.iter (lstrln2str >> printfn "%s")

And here is an example for the in-memory stack:

    flow
    |> stkimrun (stkimE 10)        // start with an empty stack with upper limit set to 10
    |> fst
    |> printfn "Stack: %O"

There are several convenience function which can create an in-memory stack: stkimEU, stkimE, stkimA where you can set the upper limit of the stack and/or the initial values in the stack.

1.4 User-Defined Interpreters

A user can implement its own interpreter (eg. the stack is implemented on a database). The user will have to implement push, pop, peek, and pur functions, which stand for each of the stack instructions and for the function that return the final result of the workflow.

One of the arguments for these functions is the state instance which can be used to pass and or reuse information from one instruction to the next one. For example this state is the in-memory list of values for the in-memory interpreter. In the case of the lister, the state is the current line in the listing and the collection of listing lines accumulated so far.

Here is an example of the implementation for the push function:

    let private push (SLister (ln, _, _) as s) v =

        (ln, "psh", v |> sprintf "%A")
        |> SLstrLn
        |> lstappnd s,

        () |> Ok

2. Queue

2.1 The Free Monad

The library exposes a free monad for queue operations. The queue monad comes with 3 instructions:

1. enqueue instruction which enqueues a value at the end of the queue.
2. dequeue instruction which extracts the value from the begining of the queue.
3. peek instruction which returns the value from the begining of the queue without remove it from the queue.

The instructions use the error type provided in Simplee.Common package in order to return the evantual failures.

1.2 Computation Builder

This monad is wrapped within queue, a computation expression builder.

The user can construct flows into an imperative way using this builder.

    let flow = queue {
        let! _ = queenq 10
        let! _ = quepeek ()
        let! r = quedeq ()
        return r
        }

3. Binary Tree

The library exposes the BinTree generic type representing a binary tree which stores values in its leaf nodes. Along with the these tree data types, the library provides different patterns.

3.1 Zipper Compuration Expressions

The zipper allows you to navigate in a tree. It comes along with a computation expression builder, binzipper. You can use these structures to navigate and manipulate the values in a tree as shown in the below example:

    let t = BinNode (
                BinNode (BinLeaf 1, BinLeaf 3), 
                BinNode (BinLeaf 7, 
                        BinNode (BinLeaf 12, BinLeaf 20))) 

    let z = t |> Ok |> btzipper
    let v = z >>= btzright >>= btzright >>= btzleft >>= btzval
    Assert.Equal (12 |> Ok, v)

    // Doubles the stored values in ALL leaves.
    let r = binzipper {
        for v in z do
        yield v * 2
        }

    let v = r >>= btzright >>= btzright >>= btzleft >>= btzval
    Assert.Equal ((12 * 2) |> Ok, v)

    // Update the stored values in specific sub-trees
    let r = binzipper {
        for x in z do 
            left
            map (x * 4)
            up
            right
            map (x / 2)
            root
        }
        
    let v = r |> btzipper >>= btzright >>= btzright >>= btzleft >>= btzval
    Assert.Equal ((12 / 2) |> Ok, v)