# Linked List Operations

06/08/20191 Min Read — #programming #functional programming #elixir #haskell #ocaml #reasonml

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 Haskell1, ReasonML2, OCaml3, Elixir4, and F#5.

``````module LinkedList where

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

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

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 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 =
| Nil
| Node of 'a * LinkedList<'a>

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

Previous
Good Stuff #1
Next
Good Stuff #2
{"ft_lang_label":"__label__en","ft_lang_prob":0.6971354,"math_prob":0.8926957,"size":4652,"snap":"2019-35-2019-39","text_gpt3_token_len":1405,"char_repetition_ratio":0.17448364,"word_repetition_ratio":0.14679912,"special_character_ratio":0.32932073,"punctuation_ratio":0.17097415,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9842459,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-09-16T16:50:59Z\",\"WARC-Record-ID\":\"<urn:uuid:4a05f6cf-dbc0-4f20-bf4e-42af06cb1dbd>\",\"Content-Length\":\"126342\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ab675111-98ce-451e-8198-c2a4dec4d1fe>\",\"WARC-Concurrent-To\":\"<urn:uuid:871eb0ce-24f9-4dbe-b4c6-0fd7226698a3>\",\"WARC-IP-Address\":\"167.99.4.63\",\"WARC-Target-URI\":\"https://www.sean.wtf/linked-list-operations/\",\"WARC-Payload-Digest\":\"sha1:3Z5M75K7YWNUERYUPGSIPG2IEHNMTPNS\",\"WARC-Block-Digest\":\"sha1:U2O5L3QWJCLWPHO3ZBBOV27ZTSQ5VJH3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-39/CC-MAIN-2019-39_segments_1568514572879.28_warc_CC-MAIN-20190916155946-20190916181946-00314.warc.gz\"}"}