# Linked List Operations

I like linked lists.
They are *super* simple data structures and are really fun to implement!
Whenever I pick up a language I think writing a linked list module is a great way to learn lots about a languge.
You can do lots of different operations on a list and functional languages tend to create really simple ways of implementing a linked list.
The `fold`

/`reduce`

function is also a super powerful tool to many other implement utility functions on a recursive data structure like a linked list as well!

Here, I'm going to implement a tiny linked list library containing a
`head`

, `tail`

, `fold`

, `map`

, and `length`

function in
Haskell^{1}, ReasonML^{2}, OCaml^{3}, Elixir^{4}, and F#^{5}.

### Haskell

```
module LinkedList where
data LinkedList a = Node a (LinkedList a) | Nil
llHead :: LinkedList a -> a
llHead (Node a _) = a
llTail :: LinkedList a -> LinkedList a
llTail Nil = Nil
llTail (Node _ a) = a
llFold :: b -> (b -> a -> b) -> LinkedList a -> b
llFold acc _ Nil = acc
llFold acc f (Node x xs) = llFold (f acc x) f xs
llMap :: (a -> b) -> LinkedList a -> LinkedList b
llMap f Nil = Nil
llMap f (Node x xs) = Node (f x) (llMap f xs)
llLength :: LinkedList a -> Int
llLength Nil = 0
llLength xs = llFold 0 (\a _ -> succ a) xs
```

### ReasonML

```
module LinkedList = {
type t('a) =
| Nil
| Node('a, t('a));
let head =
fun
| Nil => Nil
| Node(x, _) => x;
let tail =
fun
| Nil => Nil
| Node(_, xs) => xs;
let rec fold = (acc: 'a, f: ('a, 'b) => 'a, l: t('b)): 'a =>
switch (l) {
| Nil => acc
| Node(x, xs) => fold(f(acc, x), f, xs)
};
let rec map = (f: ('a) => 'b, l: t('a)): t('b) =>
switch (l) {
| Nil => Nil
| Node(x, xs) => Node(f(x), map(f, xs))
}
let length = l => fold(0, (a, _) => a + 1, l);
};
```

### OCaml

```
module LinkedList =
struct
type 'a t =
| Nil
| Node of 'a* 'a t
let head = function
| Nil -> Nil
| Node (node, _) -> node
let tail = function
| Nil -> Nil
| Node (_, list) -> list
let rec fold (acc : 'a) (f : 'a -> 'b -> 'a) (l : 'b t) : 'a =
match l with
| Nil -> acc
| Node (x, xs) -> fold (f acc x) f xs
let rec map (f : 'a -> 'b) (l : 'a t) : 'b t =
match l with
| Nil -> Nil
| Node (x, xs) -> Node ((f x), (map f xs))
let length = fold 0 (fun a _ -> a + 1)
end
```

### Elixir

```
defmodule LinkedList do
defstruct [:value, :next]
def head(%LinkedList{value: nil, next: nil} = ll), do: ll
def head(%LinkedList{value: value}), do: value
def tail(%LinkedList{value: nil, next: nil} = ll), do: ll
def tail(%LinkedList{next: next}), do: next
def fold(%LinkedList{value: nil, next: nil}, _fun), do: %LinkedList{value: nil, next: nil}
def fold(%LinkedList{value: value, next: %LinkedList{value: nil, next: nil}}, _fun), do: value
def fold(%LinkedList{value: value, next: next}, fun) do
fold(next, value, fun)
end
def fold(%LinkedList{value: nil, next: nil}, initial_value, _fun) do
initial_value
end
def fold(%LinkedList{value: value, next: next}, initial_value, fun) do
fold(next, fun.(initial_value, value), fun)
end
def length(%LinkedList{value: nil, next: nil}), do: 0
def length(%LinkedList{next: next}), do: 1 + LinkedList.length(next)
def map(%LinkedList{value: nil, next: nil}, _fun), do: %LinkedList{value: nil, next: nil}
def map(%LinkedList{value: value, next: next}, fun) do
%LinkedList{value: fun.(value), nex: map(next, fun)}
end
end
```

### F#

```
module LinkedList =
type LinkedList<'a> =
| Nil
| Node of 'a * LinkedList<'a>
let head =
function
| Nil -> Nil
| Node(x, _) -> x
let tail =
function
| Nil -> Nil
| Node(_, xs) -> xs
let rec fold acc f l =
match l with
| Nil -> acc
| Node(x, xs) -> fold (f acc x) f xs
let rec map f l =
match l with
| Nil -> Nil
| Node(x, xs) -> Node((f x), (map f xs))
let length l = fold 0 (fun a _ -> a + 1) l
```

Language features like currying, pattern matching, and type-safety are super nice when doing exercises like this. When I began to write this post I challenged myself to try it out in Haskell to learn some of the language, so it was a very fun task to actually dig into some Haskell syntax to figure out how to do it all.

A fun observation I noticed is that most of these languages all pretty much look like one another.
I my first linked list module was written in JavaScript some years ago, where I then converted it into Elixir^{6}, but with many more functions.
Once I had that knowledge as baseline, I was able to convert it to all of these other functional languages with relative ease.
After looking at and writing in these languages I would have to say Haskell is probably my favorite to think in while writing.
The type syntax is great and the language as a whole is super minimal, which is great for any language, in my opinion!

I highly encourage you all to try out some of these languages and write a program or two!