---
title: Linked List Operations
date: "2019-06-08"
series:
  - programming
  - functional programming
  - elixir
  - haskell
  - ocaml
  - reasonml
---

I like [linked lists](https://en.wikipedia.org/wiki/Linked_list).
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](#haskell)[^1], [ReasonML](#reasonml)[^2], [OCaml](#ocaml)[^3], [Elixir](#elixir)[^4], and [F#](#f)[^5].

### Haskell

```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

```reason
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

```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

```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&#35;

```fsharp
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!

[^1]: https://www.haskell.org/
[^2]: https://reasonml.github.io/
[^3]: https://ocaml.org/
[^4]: https://elixir-lang.org/
[^5]: https://fsharp.org/
[^6]: https://github.com/sean-clayton/linked-list/


Series: ocaml