sean.wtf · 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¹, ReasonML², OCaml³, Elixir⁴, and F#⁵.

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⁶, 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!