# Functional linked lists

Consider the implementation of linked lists through closures .

To denote lists, we will use a notation similar to Haskell:,

I chose JavaScript as the implementation language.

To work with linked lists, the following basic primitives are required:

Creating a list of two items is as follows:

Function implementation

The function is

Implementation

It remains to implement an empty list (

In this way

A simple program illustrating the construction and traversal of a list:

For the resulting data structure, higher-order functions can be implemented, for example

This will allow us to work with our lists in a functional style:

Other associated functions (

When writing an article, not a single array was damaged.

Anticipating the picture of a trolley from bread: this is certainly not an applied solution. Moreover, at work for such a commit, they can easily and unconstrainedly tear off their hands. What to do next with this knowledge is up to you.

Github: github.com/mvasilkov/functional-js

To denote lists, we will use a notation similar to Haskell:,

`x:xs`

where `x`

is the beginning of the list ( `head`

), and `xs`

is continued ( `tail`

). I chose JavaScript as the implementation language.

### Construct a list

To work with linked lists, the following basic primitives are required:

`nil`

- an empty list, `prepend`

( `cons`

) - an insert function at the top of the list, `head`

and `tail`

. Creating a list of two items is as follows:

```
prepend('a', prepend('b', nil))
// 'a' -> 'b' -> nil
```

Function implementation

`prepend`

:```
function prepend(x, xs) {
return function (select) {
return select(x, xs)
}
}
```

The function is

`select`

needed to access free variables ( `x:xs`

). Implementation

`head`

and `tail`

amounts to a call-list feature with the desired value `select`

:```
function select_head(x, xs) { return x }
function select_tail(x, xs) { return xs }
function head(a) { return a(select_head) }
function tail(a) { return a(select_tail) }
```

It remains to implement an empty list (

`nil`

):```
function nil() { return nil }
```

In this way

`head(nil) === tail(nil) === nil`

.#### Usage example

A simple program illustrating the construction and traversal of a list:

```
var a = prepend('a', prepend('b', nil))
// 'a' -> 'b' -> nil
head(a) // => 'a'
head(tail(a)) // => 'b'
head(tail(tail(a))) // => nil
while (a !== nil) {
console.log(head(a))
a = tail(a)
}
```

### Higher Order Functions

For the resulting data structure, higher-order functions can be implemented, for example

`map`

:```
function map(fn, a) {
if (a === nil) return nil
return prepend(fn(head(a)), map(fn, tail(a)))
}
```

This will allow us to work with our lists in a functional style:

```
var a = prepend(1, prepend(2, prepend(3, nil)))
// 1 -> 2 -> 3 -> nil
function power_of_2(x) { return 1 << x }
var b = map(power_of_2, a)
// 2 -> 4 -> 8 -> nil
```

Other associated functions (

`filter`

, `reduce`

) are offered to the reader as homework.### Such things ™

When writing an article, not a single array was damaged.

Anticipating the picture of a trolley from bread: this is certainly not an applied solution. Moreover, at work for such a commit, they can easily and unconstrainedly tear off their hands. What to do next with this knowledge is up to you.

Github: github.com/mvasilkov/functional-js