In this article, I will present a JavaScript ES6 implementation of a lazily-evaluated linked list data structure. The recursively-defined linked list is an important collection type in many functional programming languages. In the Haskell language, which inspired this project, the list datatype fills the role that arrays occupy in JavaScript. Since this list type is defined using recursion, it is possible to generate and evaluate list elements on demand, rather than at the time of the list’s creation (that’s the “lazy” part), thereby making infinite lists not only feasible but relatively straightforward.

I rely on the new `Proxy`

API from ES2015 (aka ES6) as a means of indirection for generating both finite and infinite ranged lists in JavaScript. Generators also make an appearance here, so this is a good opportunity to explore and actually use some of the latest extensions to the language while learning more about functional programming (a topic I discussed more explicitly in a prior article). The code presented here is adapted from my **lazy-linked-lists** npm module. The complete library is available as open source on GitHub, and, since we’re exploring laziness, I put the example code used specifically in this article into a separate GitHub Gist.

If you haven’t looked at `Proxy`

yet, it’s going to turn your world upside down. Whether that’s a good thing or not will depend on your perspective. Along with its counterpart `Reflect`

, `Proxy`

brings the full range of metaprogramming powers to bear on humankind’s most prolific programming language. As the term implies, *metaprogramming* entails the writing of code that is able to inspect and modify itself. In other words, it is programming “one level up” in the abstraction hierarchy, or the programming of programming itself.

A functional programmer might regard this sort of messing about with semantics as anathema and its mere possibility evidence of a failed language design. If functional programming’s greatest virtue is referential transparency, `Proxy`

enables willful obfuscation. Although prior versions of JavaScript let you do metaprogramming to an extent, the ES2015 specification put this power front and center by making it a first class citizen. Whether or not this is a power that programming languages *should* have (Brendan Eich, for one, thinks that proxies are awesome), it ironically gives those of us coming from the functional world some extra ability to wedge our favorite language idioms into JavaScript more easily.

The `Proxy`

API provides the means for intercepting the ordinary processes of a running application. This is accomplished by associating a target object with another object that *acts on its behalf*, i.e. as a *proxy*. The proxy object, in turn, filters incoming operations on the target object through methods, or “traps,” defined on a designated “handler” object. For example, you can *trap* attempts to `get`

the values of an object’s properties:

classSecret {

constructor(msg) {this.info = msg }

}lethandler = {

get: (target, prop) =>

prop === "info" ? "Too many secrets" : target[prop]

}letmakeSecret = msg =>newProxy(newSecret(msg), handler)lets1 =newSecret("Confidential information")

lets2 = makeSecret("More confidential information")

s1.info// "Confidential information"

s2.info// "Too many secrets"

In this simple example, we have a tiny wrapper class called `Secret`

that serves as a prototype for objects we might use to hide sensitive information. Rather than exposing the class itself to users of our API, we might offer instead a custom constructor function. Doing so allows us to customize the way that a `Secret`

will behave in certain circumstances. Here, the function `makeSecret`

doesn’t return the new `Secret`

object itself but a proxy object that will act on its behalf. All “messages,” so to speak, directed to a given `Secret`

will pass through its respective proxy first. And we can trap all, some, or none of those messages. The `Secret`

proxy only traps attempts to read, or `get`

, the value of the `info`

property. In fact, all attempts to read properties of `Secret`

are intercepted, because the handler object defines a `get`

method. But the logic of that method only interferes with requests to get the `info`

property. Instead of returning that value, the proxy returns a prescribed default value (one that is dear to the hearts of 1990s spy caper aficionados). You’ll note, of course, that this is hardly a full-proof mechanism for data hiding, but a more ambitious program, perhaps one that implements membranes, could certainly use `Proxy`

for that purpose.

We can apply the same technique to create a functional interface for arbitrary-length linked lists. Since we’re in ES6 land, let’s start by defining a simple class for our list type:

classList {

constructor(x, xs) {

this.head = () => x

this.tail = () => xs

}

}

This will be a fairly straightforward functional data structure. The constructor function for `List`

takes a value `x`

as the first element, or head, of a new list object and another list `xs`

as the tail, or *the rest of the list*. If you’re familiar with lower-level implementations of linked lists, you can think of the list object as a node comprising two cells: the head is the value (or label) of the node, and the tail is a pointer to the next node. The last value in any given list is always an empty list. The `head`

and `tail`

properties are defined to return not raw values but functions, in keeping with the functional paradigm and as some slight protection against tampering. Imagine them not as nullary functions but as equivalent to identity functions applied to their arguments (and if you were to parameterize that identity function instead, you’d have a monad, but I promised myself I wouldn’t discuss monads in this article).

In fact, the entire class declaration is just a special kind of function. Debates about the usefulness of OOP concepts notwithstanding, ES6 classes do possess one salient attribute that we can take advantage of here: you cannot directly invoke them as functions. Objects defined as classes can only be constructed with the `new`

keyword; the class `constructor`

function then ensures that `new`

“does the right thing.” And debates about the propriety of `new`

itself notwithstanding, this attribute allows us to hide the class declaration (for example, by not exporting it) and supply our own custom constructor function instead. In a way, we’re using the most controversial syntax in JavaScript against itself. Here’s the code we need for the interface that we *do* want to export:

constemptyList =newList()constisEmpty = xs => xs === emptyListconstcons = (x, xs) =>newList(x, xs)constlist = (...as) =>

as.length === 0 ? emptyList :newList(as.shift(), list(...as))consthead = xs => {

if(isEmpty(xs)) {throwError('EmptyListError') }

returnxs.head()

}consttail = xs => {

if(isEmpty(xs)) {throwError('EmptyListError') }

returnxs.tail()

}

In Haskell, a list is a sum type that requires two constructors: one that creates an empty list, and one that recursively creates a new list from a value (the head) and “more list” (the tail). Since JavaScript does not have sum types, the above implementation is a bit jury-rigged. But it works. The `emptyList`

object is simply a symbolic placeholder. It doesn’t pass any arguments to `List`

, so both the head and tail of an empty list are `undefined`

. Since we don’t want the `List`

constructor to be invoked directly anyway, this is fine: there is only one empty list for all occasions in our program, it is constructed once and only once, and it is `emptyList`

. We also provide a function for checking whether a list is empty, a frequent necessity where recursion and base cases are concerned.

The other constructor is `cons`

. `cons`

, like the `List`

class it wraps, *cons*tructs a new list from a value `x`

and another list `xs`

. `x`

is prepended onto `xs`

. If `xs`

is the empty list, then `cons`

simply creates a new single element list. Obviously, there is opportunity for abuse here, and a more comprehensive implementation of `cons`

would validate and possibly even type check `x`

. You could also create a curried version and make it truly functional, but for explanatory purposes I am trying to omit as much noise as possible.

The `list`

function is here for convenience, since we can’t create our own syntactic sugar for declaring lists of multiple elements. `list`

takes zero or more arguments and recursively consumes them until the arguments array (cleanly provided by the rest operator, another ES6 feature) is empty, at which point it reaches `emptyList`

as a base case. The function call `list(1,2,3)`

is equivalent to `cons(1, cons(2, cons(3, emptyList)))`

. `head`

and `tail`

are accessor functions for those respective properties. As in the Haskell Prelude, they are partial functions, which is not ideal, but again, they will suffice for demonstration purposes.

Since JavaScript is just going to treat our lists as objects, we’d like a way to print list values nicely. So let’s add a custom `valueOf`

method:

classList {

constructor(x, xs) {

this.head = null

this.tail = null

this.head = () => x

this.tail = () => xs

}

valueOf() {

letvalue = xs =>

isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}`

returnisEmpty(this) ? `[]` : `[${value(this)}]`

}

}

Now, when we display list values, we get something reasonably legible:

letlst1 = list(1,2,3,4,5)

lst1.valueOf()// [1:2:3:4:5:[]]letlst2 = cons(0, lst1)

lst2.valueOf()// [0:1:2:3:4:5:[]]letlst3 = cons(0, cons(1, cons(2, cons(3, cons(4, cons(5, emptyList))))))

lst3.valueOf()// [0:1:2:3:4:5:[]]

head(lst1)// 1

tail(lst2).valueOf()// [1:2:3:4:5:[]]

isEmpty(tail(tail(tail(tail(tail(lst1))))))// true

I use colons instead of commas to avoid confusion with arrays, and to make its structure more obvious and more Haskell-y, but you can obviously print list values however you want (and look up: ES6 template literals!). The use of `valueOf`

in these examples is only necessary if your REPL doesn’t pretty print object properties by default (node does when it can, but browser consoles do not).

Another nice-to-have convenience that ES6 now lets us implement is custom iteration using generators and the so-called “well-known symbol,” `Symbol.iterator`

:

classList {

constructor(x, xs) {

this.head = null

this.tail = null

this.head = () => x

this.tail = () => xs

}

[Symbol.iterator]() {

constlistIterator =function*(xs) {

do{

yieldhead(xs)

xs = tail(xs)

}while(xs !== emptyList)

}

constgen = listIterator(this)

return{

next() {returngen.next() }

}

}

valueOf() {

letvalue = xs =>

isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}`

returnisEmpty(this) ? `[]` : `[${value(this)}]`

}

}

Now we can use lists in the same way we might use arrays — if for some reason we’re in the mood to use `for`

loops or have some other need for iterable objects:

letlst = list(1,2,3,4,5)

for(letvalueoflst) { console.log(value); }// 1

// 2

// 3

// 4

// 5

The next step is to recreate the functionality provided in Haskell by ranged list expressions. For example, the Haskell expression `[1..10]`

is a shortcut for constructing the list `[1,2,3,4,5,6,7,8,9,10]`

. Likewise, Haskell can also infer that when you type `[1,3..10]`

what you mean is `[1,3,5,7,9]`

. Let’s see how far we can get with this in JavaScript. First, we’ll define a function that recursively constructs a list of consecutive whole numbers:

constlistRange = (start, end) => {

if(start === end) {returnlist(start) }

if(start > end) {returnlistRangeBy(start, end, x => x - 1) }

returnlistRangeBy(start, end, x => x + 1)

}

We give this function two values for `start`

and `end`

, and it gives us back a list of the numbers between them. Note that the result list, unlike in Haskell, is inclusive of the starting value but exclusive of the ending value (as in Python); that this function only operates on numbers (a version for characters wouldn’t be too hard to design, however — see my library); and that if `start`

is greater than `end`

, the result list *counts down* instead of counting up:

listRange(1,10).valueOf()// [1:2:3:4:5:6:7:8:9:[]]

listRange(10,1).valueOf()// [10:9:8:7:6:5:4:3:2:[]]

The sharp-eyed will observe that this function doesn’t actually do much on its own. Rather, it passes off responsibility for the list construction itself to another, more general function: `listRangeBy`

. That function also creates a ranged list but parameterizes the “step” function used to increment the values, making it a more general case of `listRange`

and also making it sensible to simply define one in terms of the other. Finally, with `listRangeBy`

, we meet the proxies at the heart of this matter:

constlistRangeBy = (start, end, step) => {

if(start === end) {returnlist(start) }

letx = start

constxs = list(x)

constlistGenerator =function*() {

x = step(x)

while(start < end ? x < end : x > end) {

yieldlist(x)

x = step(x)

}

}

constgen = listGenerator()

consthandler = {

get:function(target, prop) {

if(prop === `tail` && isEmpty(tail(target))) {

constnext = gen.next()

if(next.done === false) {

target[prop] = () =>newProxy(next.value, handler)

}

}

returntarget[prop]

}

}

constproxy =newProxy(xs, handler)

returnproxy

}

This function is a little strange, and too imperative for a functional programmer’s taste, but it gets the job done. First, it takes the `start`

value and creates a singleton list with it. Next, it declares an internal generator function, tailored to the parameterized `step`

function, that will `yield`

subsequent singleton lists until it hits the `end`

. These new lists, when generated, are the “lazy” tails of the “list” (actually a proxy object) returned by the `listRangeBy`

function. The head is the evaluated value of that particular node, but the rest of the list is considered “empty” until further calls for more list trigger subsequent evaluations. Each element of the tail is generated one at a time, on demand, and that is why we can say that these ranged lists are lazily evaluated.

The `handler`

object comes next. This particular handler, as in the `Secret`

example above, traps all attempts to `get`

the values of properties defined on the target `List`

. In this case, we’re only interested in the `tail`

property. When the value of a “target” list’s `tail`

is requested, instead of generating the entire rest of the list, the handler’s `get`

method calls the generator function, which yields only the next `head`

value—packaged up in another singleton list—and returns a new `Proxy`

object that “targets” that newly generated singleton list. The `tail`

of this new list is still `emptyList`

, even though it really isn’t as long as the generator is able to produce new values. But we pretend that it is as part of the logic of our proxy handler. In our lazy list world, any given tail evaluated by the handler is going to be either a singleton list or a list that has already been partially or completely evaluated. In the case of a singleton list, the handler initiates the creation of a series of proxies that continue trapping calls to evaluate these nested tails until the list is completely evaluated or no more values are requested.

This works, because list tails are evaluated recursively. Any function that recurses through a list will eventually hit `emptyList`

in its base case. For those lists that we have defined as lazy, the proxy handler checks whether the generator can yield another value if the tail of the list is empty. If it can, it returns a new proxy targeting a new list with that value as its head. If it can’t, it returns `emptyList`

as normal, which means the original list has been fully evaluated and subsequent calls for its tail will fall through the proxy undisturbed. In the case of a list that has already been partially evaluated, the handler code is skipped over until more values need to be generated—until, that is, the target list’s tail equals `emptyList`

. A completely evaluated list behaves identically to any other `List`

object.

Finally, to get this whole ball rolling, `listRangeBy`

creates a proxy object `proxy`

that targets the original singleton list `xs`

(the wrapper for our `start`

value) and returns `proxy`

, the filter at the head of the list line, in lieu of a “normal” `List`

object. We have now abstracted over lazy evaluation.

It works:

leteagerList = list(1,2,3,4,5,6,7,8,9,10)

eagerList.valueOf()// [1:2:3:4:5:6:7:8:9:10:[]]letlazyList = listRangeBy(1,100000, x => x + 3)

lazyList// List { head: [Function], tail: [Function] }

lazyList.valueOf()// RangeError: Maximum call stack size exceeded

Unfortunately, until proper tail calls finally make their way into JavaScript engines, extremely long lists are likely to blow up your stack frame when you try to perform certain operations. And speaking of extremely long lists… by using JavaScript’s handy `Infinity`

global, we can now implement analogous functions for conveniently constructing lazy lists of *infinite* length:

constlistInf = start => listInfBy(start, x => x + 1)constlistInfBy = (start, step) => listRangeBy(start, Infinity, step)

Since infinite lists are the coup de grâce of this little project, let’s define a few more basic list functions to better illustrate how they work:

constlength = xs => {

constlenAcc = (xs, n) =>

isEmpty(xs) ? n : lenAcc(tail(xs), n + 1)

returnlenAcc(xs, 0)

}constindex = (as, n) => {

if(n < 0 || isEmpty(as)) {throwError('OutOfRangeError') }

constx = head(as)

constxs = tail(as)

if(n === 0) {returnx }

returnindex(xs, n - 1)

}constlistAppend = (xs, ys) => {

if(isEmpty(xs)) {returnys }

if(isEmpty(ys)) {returnxs }

returncons(head(xs), listAppend(tail(xs), ys))

}consttake = (n, as) => {

if(n <= 0) {returnemptyList }

if(isEmpty(as)) {returnemptyList }

constx = head(as)

constxs = tail(as)

returncons(x, take(n - 1, xs))

}constdrop = (n, as) => {

if(n <= 0) {returnas }

if(isEmpty(as)) {returnemptyList }

constxs = tail(as)

returndrop(n - 1, xs)

}constmap = (f, as) => {

if(isEmpty(as)) {returnemptyList }

constx = f(head(as))

constxs = tail(as)

returncons(x, map(f, xs))

}

`length`

and `index`

are similar to their array-based counterparts. `listAppend`

is similar to `concat`

in JavaScript (whereas `concat`

in Haskell takes a multi-dimensional list and flattens it). `take`

grabs the first `n`

elements from a list and returns them in a new list. `drop`

deletes the first `n`

elements and returns what’s left. `map`

, not surprisingly, applies the function `f`

to each element in the list `as`

. These functions work on both eagerly and lazily evaluated lists, including infinite lists, though some functions obviously won’t work on the latter (and might cause some weird behavior in your REPL):

leteagerList = list(1,2,3,4,5,6,7)

letlazyList = listRangeBy(1,1000, x => x * 2)

letinfiniteList = listInf(1)

head(eagerList)// 1

head(lazyList)// 1

head(infiniteList)// 1

tail(eagerList).valueOf()// [2:3:4:5:6:7:8:9:10:[]]

tail(lazyList).valueOf()// [2:4:8:16:32:64:128:256:512:[]]

tail(infiniteList).valueOf()// RangeError: Maximum call stack size exceeded

length(eagerList)// 7

length(lazyList)// 10

length(infiniteList)// RangeError: Maximum call stack size exceeded

index(eagerList, 3)// 4

index(lazyList, 9)// 512

index(infiniteList, 10000)// 10001

listAppend(eagerList, lazyList).valueOf()// [1:2:3:4:5:6:7:1:2:4:8:16:32:64:128:256:512:[]]

listAppend(lazyList, infiniteList).valueOf()// List { head: [Function], tail: [Function] }

index(listAppend(lazyList, infiniteList), 100)// 91

listAppend(infiniteList, eagerList).valueOf()// RangeError: Maximum call stack size exceeded

take(5, eagerList).valueOf()// [1:2:3:4:5:[]]

take(5, lazyList).valueOf()// [1:2:4:8:16:[]]

take(5, infiniteList).valueOf()// [1:2:3:4:5:[]]

drop(5, eagerList).valueOf()// [6:7:[]]

drop(5, lazyList).valueOf()// [32:64:128:256:512:[]]

drop(5, infiniteList).valueOf()// RangeError: Maximum call stack size exceededletf = x => x * 10

map(f, eagerList).valueOf()// [10:20:30:40:50:60:70:[]]

map(f, lazyList).valueOf()// [10:20:40:80:160:320:640:1280:2560:5120:[]]

map(f, infiniteList).valueOf()// RangeError: Maximum call stack size exceeded

map(f, take(10, infiniteList)).valueOf()// [10:20:30:40:50:60:70:80:90:100:[]]

In the last example, we can’t perform lazy mapping (though in principle it’s possible), but we *can* compose `map`

with another function that *does* produce a finite list and map over that.

While we’re translating Haskell functions into JavaScript, why not import the basic functions for generating other kinds of infinite lists, too? These can be handy when you need to work with streams of values:

constiterate = (f, x) => listInfBy(x, x => f(x))constrepeat = a => cons(a, listInfBy(a, a => a))constreplicate = (n, x) => take(n, repeat(x))

`iterate`

repeatedly applies the given function `f`

to the value `x`

. `repeat`

returns an infinite list of the same value. `replicate`

simply returns a list of `n`

elements that are all of value `x`

. There’s one more function, `cycle`

, that deserves special mentioning, because it requires a special implementation. `cycle`

takes a list and infinitely repeats it. Our regular `listRangeBy`

function cannot handle this case, however, so we must provide a slightly altered version of it for `cycle`

:

constcycle = as => {

if(isEmpty(as)) {throwError('EmptyListError') }

letx = head(as)

letxs = tail(as)

constc = list(x)

constlistGenerator =function*() {

do{

x = isEmpty(xs) ? head(as) : head(xs)

xs = isEmpty(xs) ? tail(as) : tail(xs)

yieldlist(x)

}while(true)

}

constgen = listGenerator()

consthandler = {

get:function(target, prop) {

if(prop === `tail` && isEmpty(tail(target))) {

constnext = gen.next()

target[prop] = () =>newProxy(next.value, handler)

}

returntarget[prop]

}

}

constproxy =newProxy(c, handler)

returnproxy

}

JavaScript, like life, is a little bit messy sometimes. Let’s see what these functions do:

letlst1 = iterate(x => x + 2, 0)

take(10, lst1).valueOf()// [0:2:4:6:8:10:12:14:16:18:[]]letlst2 = repeat(7)

take(20, lst2).valueOf()// [7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:[]]letlst3 = replicate(5, 23)

lst3.valueOf()// [23:23:23:23:23:[]]letlst4 = cycle(list(5,4,3,2,1))

index(ls4, 5)// 5

index(lst4, 10)// 5

index(lst4, 100)// 5

index(lst4, 104)// 1

If we want, we can use infinite lists to create even more specialized sorts of streams or as part of the implementations of well-known algorithms:

constbooleans = cycle(list(false, true))constfib = n => n < 2 ? n : fib(n - 1) + fib(n - 2)constfibs = n => map(fib, take(n, listInf(1)))constfact = n => n === 1 ? n : fact(n - 1) * nconstfacts = n => map(fact, take(n, listInf(1)))constsqrt = (a0, eps, n) => {

constwithin = (eps, rest) => {

leta = index(rest, 0)

letb = index(rest, 1)

returnMath.abs(a - b) <= eps ? b : within(eps, drop(1, rest))

}

constnext = (n, x) => (x + n / x) / 2

returnwithin(eps, iterate(next.bind(null, n), a0))

}

index(booleans, 20)// false

index(booleans, 10001)// true

index(fibs(10), 9)// 55

facts(5).valueOf()// [1:2:6:24:120:[]]

sqrt(1,0,2)// 1.414213562373095

sqrt(1,0,144)// 144

An infinite list of alternating booleans might come in handy as a filter for even or odd numbers or if you’re creating something else that entails an alternating pattern (such as shading for table rows). With a stream of values, you can just grab however many you need and not have to code the logic for counting them up. The fibonacci and factorial examples, aside from being the most famous recursion examples ever, show how you can use infinite lists to algorithmically produce custom series of values. The `sqrt`

function shown here uses an infinite list to compute the square root of a number `n`

, with a tolerance `eps`

, and starting with an initial estimate `a0`

. This example of the Newton-Raphson method for calculating square roots is adapted from Why Functional Programming Matters by John Hughes — essential reading, indeed.

There you have it: lazy, functional, infinite lists in JavaScript with various operations you might perform on them! Once again, please see my library on GitHub for even more `List`

functions, including functions to take and drop elements conditionally, filter lists, sort lists, zip lists, and more. The full class definition also provides list equality checking, all the standard comparison methods, and implementations for common algebraic interfaces, such as monoid, foldable, functor, and monad (oops). In addition, the complete library better supports strings, which I ignored for the sake of simplicity in this article. Functions for converting between lists and JavaScript arrays and strings are also supplied. For type-checked and curried versions of all of these functions, see my more comprehensive library of Haskell functions translated into JavaScript: **maryamyriameliamurphies.js**.

The linked list is an ideal data structure for functional programming: it’s easy to define recursively, and it fits snugly into compositions of functions. A functional linked list is so straightforward to implement because it’s a mathematical object, not an abstraction over finite blocks of computer memory that must be procedurally manipulated or, as in JavaScript, a specialized record type. With a more purely functional language, we can describe this collection type as a simple formula and not have to worry about memory, pointers, or anything else the actual machine cares about but we, as programmers, do not. Furthermore, algebraic data types, scary as they may sound, can make our data so much easier to organize and our code so much easier to read and, as the saying goes, reason about.

The whole definition of a list in Haskell, for example, is `data [] a = [] | a : [a]`

. That one snippet of code accomplishes essentially the same thing as my entire class — and it’s all thanks to the power and expressivity of sum types. Most languages have product types. Few have sum types. The JavaScript `Object`

is a product type, because every object contains a field for every possible value. The `List`

we defined above is not a true sum type, but it does reproduce the functionality of a type that contains *either* one value or set or values *or* another value or set of values. Where product types represent *and*, sum types represent *or*. You wouldn’t go without *or* in your boolean logic, so why go without it in your type system? Without the ability to define types as disjoint, you are trapped in a world of artificial hierarchies and over-specified abstractions. That’s what you get when everything is a product type, when you have no choice but to define custom types (i.e. classes) as aggregates of values rather than alternatives *among* values. If you’ve ever had trouble stitching a pile of objects together in an effort to model inconsistent data, then you know the pain whereof I speak. And now you have a remedy. With sum types, you can more easily adapt your model to the messy world of data rather than trying to force data to conform to your model. In functional programming, we prefer Proteus to Procrustes. And we prefer flexible lists to rigid arrays. JavaScript’s built-in `Array`

type has made great strides toward becoming more functional, but it is still essentially a hack. Fortunately, JavaScript has higher-order functions, so we can do our own hacking, too.

#### Postscript — Binary Trees

The methods I demonstrate in this article to implement a linked list can, in principle, also be used for other linked structures. If a given data type has an obvious recursive definition, it won’t be too much trouble to apply to it the same logic. Let’s briefly look at binary trees. We can define a binary tree in Haskell as follows: `data Tree a = Leaf | Node (Tree a) a (Tree a)`

. Like our `List`

type above, `Tree`

is a sum type, which means any given `Tree`

will be *either* a `Leaf`

*or* a `Node`

. `Leaf`

is like `emptyList`

: it’s the natural base case or terminal point of the structure. Whereas a linked list terminates at only one point, however, a tree can have multiple branches, each one of which could have further branches, all of them ending in terminal points. Here’s a basic implementation of this same structure in JavaScript, complete with functions for inserting into a tree and for displaying tree values in the usual orderings (converted into arrays for the sake of ease):

classTree {

constructor(left, label, right) {

this.left = () => left

this.label = () => label

this.right = () => right

}

}constleaf =newTree()constnode = (left, label, right) =>newTree(left, label, right)constinsert = (x, t) => {

if(t === leaf) {returnnode(leaf, x, leaf) }

if(x === t.label()) {returnt }

if(x < t.label()) {

returnnode(insert(x, t.left()), t.label(), t.right())

}

returnnode(t.left(), t.label(), insert(x, t.right()))

}constpreorder = t => t === leaf ? [] :

[t.label()]

.concat(preorder(t.left())

.concat(preorder(t.right())))constinorder = t => t === leaf ? [] :

inorder(t.left())

.concat([t.label()]

.concat(inorder(t.right())))constpostorder = t => t === leaf ? [] :

postorder(t.left())

.concat(postorder(t.right())

.concat([t.label()]))

And now let’s construct a test tree and try out our little library of functions:

lettree = leaf

letsquares = listInfBy(1, x => x * 2)

letcubes = listInfBy(1, x => x * 3)

for(letvalueoftake(10, squares)) { tree = insert(value, tree) }

preorder(tree)// [1,2,4,8,16,32,64,128,256,512]

inorder(tree)// [1,2,4,8,16,32,64,128,256,512]

postorder(tree)// [512,256,128,64,32,16,8,4,2,1]for(letvalueoftake(5, cubes)) { tree = insert(value, tree) }

preorder(tree)// [1,2,4,3,8,16,9,32,27,64,128,81,256,512]

inorder(tree)// [1,2,3,4,8,9,16,27,32,64,81,128,256,512]

postorder(tree)// [3,9,27,81,512,256,128,64,32,16,8,4,2,1]

After learning about functional linked lists, binary trees should be a piece of cake. Just for fun, I used an infinite list of squares to generate the example tree above, then mixed it up with a stream of cubes. Why? To illustrate function composition one more time. The power of functional programming comes from the accumulation of all these little concepts. Keep learning them, and keep growing your toolkit. The implementation of lazy binary trees I leave as an exercise for the reader.

Hacker Noon is how hackers start their afternoons. We’re a part of the @AMIfamily. We are now accepting submissions and happy to discuss advertising &sponsorship opportunities.

To learn more, read our about page, like/message us on Facebook, or simply, tweet/DM @HackerNoon.

If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!