I was away in North Uist during the summer and due to the wonderful lack of connectivity I decided to get on with learning all about Haskell. Having been using a functional style for a while now I wanted to get right into the guts and have a poke around. I saw Monoids and Monads lurking on the horizon but starting out easy is always the best bet.
Length of a list
The lengthOfList function is an example of a recursive function, that is a function that calls itself as part of a calculation. Finding the length of a list involves breaking the list into it's head and tail. The head is counted as one element and the process is repeated with the tail of the list. We need a base case to tell the recursion where to stop. In this problem when we get to the point where we run out of elements (i.e. we get the empty list as the tail) we add 0 and don't call the function anymore.
Haskell allows you to state your cases using pattern-matching. Inputs are checked against each case top to bottom with most specific cases at the beginning. The pattern-matching also gives us the head and tail for free using the cons (:) infix function.
In most cases a recursion can be removed in favour of a fold. Folding maps over each item in a list, accumulating a final result. In the examples below a point-free style is used to return partially-applied fold functions whose accumulator function simply adds one after each item is mapped. Ramda calls a left-fold, reduce.
Note below how the new arrow functions allow us to remove the function fluff and see the lambda!
Reversing a list
Let's look at taking a list and reversing it. Again this can be written as a recursive function. Each time the function is called it operates on the tail of the list until we run out of elements i.e. the empty list.
In Haskell the concatenation (++) operator is slow compared to the cons (:) operator since Haskell uses a linked list structure . This makes it really easy to add an element to the head of any list. The implementation below shows the use of a local function for the recursive part of the computation. This allows us to start of with the empty list and progressively add elements to the head.
As usual we can rewrite a recursive function as a fold and it's presented below in a point-free style.
We see here again how the new arrow functions give us all the readability of the Haskell syntax and more of it's terseness.
Note here that the the lambda function is just the : operator with the arguments flipped. We can therefore use the flip function to reserve them.
Remove an entry at a certain index
Reading the Haskell code below we are given a list l and a position p at which to remove the element. The result is a list of x's. The code after the pipe defines how the x's will be chosen. We use the zip function to generate pairs of each element and an index for that element. The [1..] range utilises Haskell's laziness and we pick as many indicies as required from an 'infinite' list of natural numbers in the zip function. So for a list [2,3,4,2] we would get pairs (2,1), (3,2), (4,3), (2,4) and we didn't need to worry about the length of the list.
As the pairs are generated lazily there is a check to see if the generated index is not the same as our position p. If it is then the pair is not selected. Even though the pairs are generated we only select the list part for the final output.