Creating a linked list using only Function Combinators
Tags: javascript, functional, showdev
Published: 2018-12-10 18:32:59

---
title: Creating a linked list using only Function Combinators
published: true
description: 
tags: JavaScript, functional, fp, showdev
---

[![ABC written on chalk board](https://thepracticaldev.s3.amazonaws.com/i/a3jxectuhua0l4degar6.jpg)](https://www.pexels.com/photo/abc-books-chalk-chalkboard-265076/)

Today I will demonstrate how to create a Linked List without any data structures like `Object` or `Arrays`; Instead, using Function Combinators.

I am assuming you are already familiar with what a linked list is. If you need a refresher on linked lists, check out [thank u, next: an introduction to linked lists](https://dev.to/aspittel/thank-u-next-an-introduction-to-linked-lists-4pph) by @aspittel.

My goal is to expose you something you may not have seen before. To show what is possible with currying, partial application, closures and function combinators. And most important of all, have a little fun while doing it.

⚠️ This article has runkit embedded in it. You are meant to run, modify, tweak, and play with the examples on this page.

# What The What is a Function Combinator?

Definition from [Thinking Functionally: Combinators](https://github.com/louthy/language-ext/wiki/Thinking-Functionally:-Combinators)

> The word "combinator" is used to describe functions whose result depends only on their parameters. That means there is no dependency on the outside world, and in particular, no other functions or global value can be accessed at all.

> In practice, this means that a combinator function is limited to combining its parameters in various ways.

That's a lot to take in, so maybe some examples will help?

```javascript
/* ☝️ These are combinators */
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
const B = a => b => c => a (b (c))
//        -    -    -    ---------
//         \   |   /        |
//           arguments   ---
//                      /
//       only arguments are used

/* 👎 These are not */
const nope = a => a.map(double)
//                  --- ------
//                 /           \    
//                /    ⚠️ reaching outside of the func
//               /
//     ⚠️ can't use map either.
const add => a => b => a + b
//                       -
//                      /
// ⚠️ Uh oh, `+` is not part of 'arguments'
```

To recap the code above: A combinator can _only_ use its arguments. That excludes external functions, methods, and operators!

Don't worry, it's okay to still be a little confused. (⊙_☉)

# Abandoning Structure

A typical linked list will use some sort of data structure like these:

```javascript
class Node {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

/* or */

const node = (data, next) => ({ data, next })

/* or */

const node = (data, next) => [ data, next ]
```

But we won't be using any of these data structures. We will be using Function Combinators.

Before we jump right into the deep end of the combinator pool, let's start with a basic function for our `node`:

```javascript
function node (data, next) {
//             ----  ----
//           /            \
//       our data       the next node
}
```

Now how do we access `data` and `next` without using `node` like an object? If you said `callbacks`, you were right!

{% runkit %}
/////////////////////////////////////////////////////////////
//                                                         //
// 📌 ATTENTION: You can modify and run these code blocks! //
//                                                         //
/////////////////////////////////////////////////////////////

function node (data, next, callback) {
  return callback(data, next)
}

// I can use bind to store my data and next values.
const head = node.bind(null, 'data', null)

// Use a callback to read the values from head.
head((data, next) => {
  return { data, next }
})
{% endrunkit %}

I don't really care for this implementation using `bind`. So I'm going to curry the `node` function so I can use partial application to apply `data` and `next`. This will have the same effect as using `bind` but with a much better syntax.

{% runkit %}
const node = data => next => callback => callback (data) (next)
//           ----    ----    --------              ----   ----
//             \       |        /                 /      /
//           parameters are curried        -------------
//                                       /    
// closures make data and next available
// to callback when it is finally called.

// I can use bind to store my data and next values.
const head = node ('data') (null)
//                 ------   ----
//                  /        /
//           We can partially apply the arguments `data` and null.

// Use a callback to read the values from head.
head (data => next => {
  return { data, next }
})
{% endrunkit %}

Now if you were paying very close attention, you might have noticed that `node` is identical to the `V` combinator above!

So now `node` can be reduced to:

```javascript
const node = V
```

and we can create nodes like this:

```javascript
const evenOdd = node ('Even') ('Odd')
const leftRight = node ('Left') ('Right')
const yesNo = node ('Yes') ('No')
```

If we were to look at a break down of what the partial application is doing, it would look something like this:

```javascript
// first copy the node function
const evenOdd = data => next => callback => callback (data) (next)

// apply 'Even' to data.
const evenOdd =         next => callback => callback ('Even') (next)

// apply 'Odd' to next.
const evenOdd =                 callback => callback ('Even') ('Odd')

// We end up with this:
const evenOdd = callback => callback ('Even') ('Odd')
```

`evenOdd` now takes a single parameter, the `callback`. The `callback` expects a function that looks like this:

```javascript
const callback = a => b => { /* ??? */ }
```

We are now at a point where we can start to play. Hit `play` on this runkit and modify the `callback` to return `'Left'`.

{% runkit
const V = a => b => c => c (a) (b)
%}
const node = V

const leftRight = node ('Left') ('Right')

// TODO: modify callback so the code returns 'Left'
const callback = a => b => {}

leftRight (callback) //=> 'Left'
{% endrunkit %} 

Now modify the code again to return `'Right'`.

Awesome! Now let's call the `'Left'` function `data` and the `'Right'` function `next`.

```javascript
const data = a => _ => a
const next = _ => b => b
```

Run it all again with our new functions.

{% runkit
const V = a => b => c => c (a) (b)
%}
const node = V
const data = a => _ => a
const next = _ => b => b

const leftRight = node ('Left') ('Right')

console.log (leftRight (data))
console.log (leftRight (next))
{% endrunkit %}

Did you notice `data` is also the same as our `K Combinator`?

```javascript
// 💥 BOOM!
const data = K
```

`next` almost matches the `K Combinator`, but it's a little different. `next` returns `b`, while `data` returns `a`. There is a little trick for that:

```javascript
// 🧙‍♀️ MAGIC!
const next = K (I)
```

This neat trick was the inspiration for an entire article [The easiest problem you cannot solve](https://dev.to/joelnet/the-easiest-problem-you-cannot-solve-2d3m). I bet you can solve this problem in less than 2 seconds now!

# Link that List

Let's translate what we have learned into a linked list.

{% runkit
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
%}
const node = V
const data = K
const next = K (I)
const Nil = Symbol('Nil') // Just an Object to detect the end.

const first = node ('1st') (Nil)
//                          ---
//                        /
// Nil signifies the end

const second = node ('2nd') (first)
//                           -----
//                         /
//   pass the first node in as the `next`

const third = node ('3rd') (second)
//                          -----_
//                         /
//   pass the second node in as the `next`

console.log (third (data)) //=> '3rd'
console.log (third (next) (data)) //=> '2nd'
console.log (third (next) (next) (data)) //=> '1st'
{% endrunkit %} 

# Count that List

We can create a simple function to enumerate the list and return a count.

{% runkit
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
%}
const node = V
const data = K
const next = K (I)
const Nil = Symbol('Nil')

const length = (list, value = 0) =>
  list === Nil
    ? value
    : length (list (next), value + 1)

const first = node ('1st') (Nil)
const second = node ('2nd') (first)
const third = node ('3rd') (second)

console.log (length (first)) //=> 1
console.log (length (second)) //=> 2
console.log (length (third)) //=> 3
{% endrunkit %} 

# Map that List

Mapping is similar to an `Array`.

{% runkit
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
%}
const node = V
const data = K
const next = K (I)
const Nil = Symbol('Nil')

// Don't worry about this implementation.
// It is just to demo the code below.
const map = func => list =>
  list === Nil
    ? list
    : node (func (list (data))) (map (func) (list (next)))

const first = node ('1st') (Nil)
const second = node ('2nd') (first)
const third = node ('3rd') (second)

const upper = x => x.toUpperCase()

const THIRD = map (upper) (third)

console.log (THIRD (data)) //=> '3RD'
console.log (THIRD (next) (data)) //=> '2ND'
console.log (THIRD (next) (next) (data)) //=> '1ST'
{% endrunkit %} 

# Filter

Filtering is also similar to an `Array`.

{% runkit
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
%}
const node = V
const data = K
const next = K (I)
const Nil = Symbol('Nil')

// Don't worry about this implementation.
// It is just to demo the code below.
const filter = predicate => list =>
  list === Nil ? list
  : predicate (list (data)) ? node (list (data)) (filter (predicate) (list (next)))
  : filter (predicate) (list (next))

const first = node (1) (Nil)
const second = node (2) (first)
const third = node (3) (second)
const fourth = node (4) (third)

const isEven = x => x % 2 === 0

const evens = filter (isEven) (fourth)

console.log (evens (data)) //=> 4
console.log (evens (next) (data)) //=> 2
{% endrunkit %} 

# But are Function Combinators really useful?

Sure, you should never create a linked list this way. Actually, you should never be creating a linked list, to begin with. So this is all just academic anyway.

Surprisingly, there are some practical uses for function combinators!

You might not recognize the `B Combinator`

```javascript
const B = a => b => c => a (b (c))
```

Unless it was written like this:

```javascript
const compose = f => g => x => f (g (x))
```

That's right! `compose` is just the `B Combinator`! If you were curious, `pipe` is the `Q Combinator`.

Another useful utility function is `always`. Ramda has an `always` in their library. You can also recreate it with a simple function combinator.

```javascript
const always = K

const awesome = always ('Awesome!')

awesome () //=> 'Awesome!'
awesome (123) //=> 'Awesome!'
awesome ('hello') //=> 'Awesome!'
```

`tap` is also a common function that I use often. It could be written like (below). It's great for managing side-effects.

```javascript
const tap = func => val => {
  func (val) // execute my side effect
  return val // return the original value
}
```

We could also write `tap` like this:

```javascript
const tap = S (K)
```

That's a lot of really useful stuff that can be created with function combinators!

# Summary

- We learned how to create a Linked List without using any Data Structures.
- We learned what function combinators are and how they can be useful.
- We learned how you can use currying, partial application and closures to store data.

Let me know what else you might have learned!

Let me know what you thought of the runkit examples. I am considering incorporating them more in my posts.

Do you want to learn more about function combinators? Let me know in the comments!

If you love Functional JavaScript, follow me here or on Twitter [@joelnet](https://twitter.com/joelnet)!

![Cheers!](https://thepracticaldev.s3.amazonaws.com/i/6jsy3a866frzp3u5oda0.jpg)