Linked list operations in a few functional languages

1-linkedlist.fs

// F#

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

2-linkedlist.hs

-- Haskell

data LinkedList a = Node a (LinkedList a) | Nil

head :: LinkedList a -> a
head (Node a _) = a

tail :: LinkedList a -> LinkedList a
tail Nil = Nil
tail (Node _ a) = a

fold :: b -> (b -> a -> b) -> LinkedList a -> b
fold acc _ Nil = acc
fold acc f (Node x xs) = fold (f acc x) f xs

map :: (a -> b) -> LinkedList a -> LinkedList b
map f Nil = Nil
map f (Node x xs) = Node (f x) (map f xs)

length :: LinkedList a -> Int
length Nil = 0
length xs = fold 0 (\a _ -> succ a) xs

3-linkedlist.re

// ReasonML

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);

4-linkedlist.ml

(* OCaml *)

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)

5-linkedlist.ex

# 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