## DEV Community 👩‍💻👨‍💻 is a community of 930,237 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

JavaScript Joel

Posted on • Updated on

# Creating a linked list using only Function Combinators 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 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

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?

``````/* ☝️ 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:

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

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

``` ``` ``` ///////////////////////////////////////////////////////////// // // // 📌 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 } }) ```

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.

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

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:

``````const node = V
``````

and we can create nodes like this:

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

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

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

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

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

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

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

Run it all again with our new functions.

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

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

``````// 💥 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:

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

This neat trick was the inspiration for an entire article The easiest problem you cannot solve. 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.

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

# Count that List

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

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

# Map that List

Mapping is similar to an `Array`.

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

# Filter

Filtering is also similar to an `Array`.

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

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

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

Unless it was written like this:

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

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

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

We could also write `tap` like this:

``````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! ## Top comments (18) JavaScript Joel

Thanks! It's a topic most people aren't interested in, so I hope I was able to make it interesting! JavaScript Joel

I believe this is a problem with the runkit embed on the site. I just confirmed that the code itself does run in Chrome.

Does the Runkit embed show on your screen are you able to see the code? I'm not seeing any problems on my computer. JavaScript Joel

Ahh I see it now! It looks like the first two runkit embeds are working. The others following do not. I have opened up a support ticket on Github for this issue.

github.com/forem/forem/issues/9773 JavaScript Joel

Awesome. Looks like I had to resave the page. rhymes

Loved it, and thank you for using RunKit!

One thing: is there a reason why the combinators are named I, K, V, B instead of having more mnemonic names? JavaScript Joel • Edited on

Oh this is the fun part. Maybe I should have mentioned it in the article. A lot of the combinators do go by other names. But my favorite names for function combinators actually come from To Mock a Mockingbird. In To Mock a Mockingbird, they are named after birds!

The Combinator Birds (for I, K, V, B) are:

B - Bluebird
K - Kestrel
V - Vireo

and my absolute favorite is

I - Identity Bird

because it is also famously referred to as The Idiot!

The letters are probably because function combinators come from maths. And math people just like single letters. (I'm just guessing at this) rhymes

Thank you!

I'll call them Identity, Bluebird, Kestrel and Vireo :D Jochem Stoel

Its called functional. xD JavaScript Joel

Thanks for pointing me there!

I really only knew about the CodePen embeds and those didn't work for what I wanted. JavaScript Joel • Edited on

Thanks! I'm hoping to use runkit more in my posts. I wish I had some stats on how many actually are using it.

Cheers! JavaScript Joel

Thanks! I have a few more articles at about 90%. I just need to spend some time to get them over the finish line.

Cheers!

#### Head to your account's Settings to...

🌚 Enable dark mode
🔠 Change your default font
📚 Adjust your experience level to see more relevant content