Implementation of the stack, queue and soundboard in the F # language in a functional style

I recently got acquainted with the concept of functional programming. Perhaps in this article I reinvent the wheel, but I believe that these actions are very useful for learning, as well as for a clearer understanding of functional programming.

Let's try to implement the basic data types: the stack, the queue, and the decks — in F #, using pure functions whenever possible. Naturally, they will be based on lists.

First of all, it is necessary to define the pure function. The simplest definition is: a function is called pure if it is deterministic and has no side effects.
')
The determinism of a function means that it produces the same result for the same set of arguments.
Side effects of functions are changing global variables, exception handling, I / O operations, and so on.

Stack

First of all, let's start with the stack. In F #, the main data type for storing several elements of the same type is not an array, but a list. If we are faced with the task of turning the list into a stack, what functions will we need?

First, we need a function to add an item to the top of the stack. This function is traditionally called push. However, this function does not particularly interest us, since it is very simply implemented:

let push stk el = el :: stk 

A fairly simple function that has the type 'a list ->' a -> 'a list , but not all further functions will allow you to treat yourself in such a simple way.

Much more interesting is the case of pushing the top of the stack, especially if we limit ourselves to pure functions. How do we cope with this task?


To do this, it’s enough to remember that when defining the pop function, there were always two approaches: either an object was pushed out of the top of the stack and simultaneously removed from it, or a method was first called to get the value of the top, and then a method to remove the top.

The first approach cannot be performed in a functional style, since this is a clear example of a function with a side effect: the stack value is returned as a result of the function, and its removal is a side effect.
Moreover, using the first approach, we also lose the determinism of the function: applying it to the same stack instance will give us a different result.

So let's stop on the second approach. To do this, we write two functions: head, which will return a value at the top of the stack, and pop, which will return a list that has no vertex.

We will deal with the first. What do we need to return? There are two possible options: the stack is empty or the stack is not empty. If the stack is not empty, then everything is clear: we derive the element from the vertex. And if the stack is empty? After all, instead of conditional statements in F #, pattern matching is used. We have a limitation that when using different templates, data of the same type must be returned. Come to the aid of so-called. optional types that take values Some (x) or None .

Now we can write a function:

 let head stk = match stk with |[] -> None |hd :: _ -> Some(hd) 

If we look at the type of the head function, we will see that it is of the type 'a list ->' a option , that is, it takes a list as a parameter and returns a value of an optional type.
The function works as follows: accepting the stk list, it looks at its value. If it is empty, that is, stk = [], then it returns None, which corresponds to the fact that this list has no vertex, if not empty, it separates the first element of the list from the rest and returns it in the form of an optional type. The underscore in pattern matching means that it does not matter what should be in this place.
At the same time, our function is pure: determinism is present, there are no side effects.

Looking at this function, now we can easily write the pop function, which will be somewhat symmetrical, but will not need an optional type, since the role None will execute an empty list:

 let pop stk = match stk with |[] -> [] |_:: tl -> tl 

This function has the type: 'a list ->' a list

Thus, the following code gives us all the functions for working with the stack.

 let push stk el = el :: stk let head stk = match stk with |[] -> None |hd :: _ -> Some(hd) let pop stk = match stk with |[] -> [] |_ :: tl -> tl 

Turn

The queue differs from the stack in that the addition of a new element occurs at the end of the list, and the extraction occurs from the beginning of the queue. We implement the functions add (add an item to the queue), head (who is currently in the queue) and delque (remove the item from the queue). And if the head and delque functions are beyond doubt, then an attempt to write let head = que :: el will lead to a compilation error, since the operator :: has the type 'a ->' a list -> 'a list , i.e., the left operand can not be a list.

The problem is solved again using pattern matching, but now we use recursive functions in order to get to the end. If the queue is empty, then it doesn’t matter to add from the end or from the beginning, since there are none, so add to the beginning, which will be the end at the same time. If the list is not empty, then we divide it into the first element and all the others, and apply our function recursively to the remaining elements of the list.

 let rec add que el = match que with |[] -> el :: [] |hd :: tl -> hd :: (add tl el) 

Thus, the full set of functions for the queue has the form:

 let rec add que el = match que with |[] -> el :: [] |hd :: tl -> hd :: (add tl el) let head que = match que with |[] -> None |hd :: _ -> Some(hd) let delque que = match que with |[] -> [] |_ :: tl -> tl 

Dec

The most interesting data structure is the decks, or the bidirectional queue, i.e. the addition and deletion of elements can occur both from the beginning and from the end. By analogy with the functions head and pop for the stack, we introduce the functions tail and delend for the deck. Here the implementation will be more interesting. We need the last element, but in functional programming there are no cycles. How should we be? Once again, recursion comes to the rescue, but it is too early to rejoice.
If we write completely by analogy:

 let rec tail deq = match deq with |[] -> None |_ :: tl -> tail tl 

then we will successfully get None for any argument . This is due to the fact that any list in F # is represented as a = a :: [] , i.e., if we unwind the tangle of the list in succession, then in the end we will have nothing left.
This problem is solved by adding just one condition, if we recall that the operator :: has the type 'a ->' a list -> 'a list , i.e., the operand to the left of :: must have the type of the list element, and not be the list itself, so change the code as follows:

 let rec tail deq = match deq with |[] -> None |hd :: [] -> Some(hd) |_ :: tl -> tail tl 

The modified function will now work correctly, since the recursion will end on the last element of the deck and return it safely.

We figured it out, but what do we do with the delend function? We need to replace the last item in the list, but how to do it? Let's recall that the operator :: returns a list and is associative to the right, which allows us to consider the following code:

 let rec delend deq = match deq with |[] -> [] |hd1 :: hd2 :: [] -> hd1 :: [] |hd :: tl -> hd :: (delend tl) 

Here it is, our desired code. Thanks to the operator :: on the right side, we will not lose the beginning of the list, and the recursion will end on the penultimate element of the list, creating a new list without the former last element.

Thus, for the deck, we get the following set of functions:

 let addbegin deq el = el :: deq let rec addend deq el = match deq with |[] -> el :: [] |hd :: tl -> hd :: (addend tl el) let head deq = match deq with |[] -> None |hd :: _ -> Some(hd) let delbegin deq = match deq with |[] -> [] |_ :: tl -> tl let rec tail deq = match deq with |[] -> None |hd :: [] -> Some(hd) |_ :: tl -> tail tl let rec delend deq = match deq with |[] -> [] |hd1 :: hd2 :: [] -> hd1 :: [] |hd :: tl -> hd :: (delend tl) 

Thanks for attention! Any code written in this article can be tested in any environment that allows programming under F #