Writing more functional JS by looking at Haskell

Andrew Drummond
Sep 6, 2018 · 16 min read

Functional programming is like, so hot right now.

Aw jeez

Functional programming is one of the areas of programming that has always fascinated me.

While I was a student at Penn I took one of the computer science intro classes in the engineering college, where we spent a solid 8 weeks on OCaml. OCaml is strictly typed, and uses many functional programming concepts — at first, I couldn’t stand it. I was previously familiar with python and object oriented, loosely typed programming, and so working with OCaml was beyond weird, a little like playing Fifa with different controller settings.

As much as I was weirded out at first, when we switched over to Java I found I actually wanted to go back. I realized my OCaml code was much cleaner, easier to read, and once compiled, there weren’t any unexpected errors (like nullpointerexceptions…).

Even after attending a code bootcamp and becoming extremely familiar with JavaScript, my past with OCaml still tugged at me — I wanted to get back to practicing more functional code.

In this post I’ll be taking a look at another functional programming language: Haskell, and writing some typical JavaScript functions from scratch in Haskell. Then, looking at the Haskell code, I’ll write a write a functional programming version of these functions in JavaScript.

For those readers that have absolutely no idea what Haskell looks like, here’s a sneak peak at a simple add function:

add :: Integer -> Integer -> Integer
add x y = x + y

Just keep reading, it’ll get better.

Here’s the roadmap:

  1. Basics of functional programming (i.e. Lambda calculus, what makes functional programming functional)
  2. What the hell is Haskell?
  3. How do we use this statically typed, functional programming language and recursion to do things like reduce an array to a single value, apply a function to each element of an array, or even sort elements of an array?
  4. How can we replicate these fun functional functions in JavaScript?
  5. Does this mean JavaScript can be functional?

Just google image search lambda calculus

What is the mathematical basis for functional programming? (you probably didn’t think to yourself)

Functional programming is based on a school of abstract mathematics called lambda calculus.

A calculus is just a way of moving symbols around on a page. Lambda calculus is about evaluating and defining functions

Lambda calculus is based on lambda notation — basically an alternative way of representing things like variables or functions in math. And when I say ~alternative~ I really just mean it’s different from what you were probably taught in math class about how to write functions and variables, and how to think about them. That’s what makes lambda calculus particularly confusing to digest at first.

So how does this lambda calculus (methodology for moving symbols around on a page) go about defining and evaluating functions?

It focuses on:

  • Application of a function by using simple expressions
  • Abstraction of a function using generic variables that can represent anything
  • Grouping of expressions so that they can compose other expressions

Let’s look at a few examples:

x is a variable. x is technically a lambda expression

t is also a variable, and is thus also a valid lambda expression

Because these are both valid lambda expressions, we can apply them in a function (or, as it’s technically called — a ~lambda abstraction~)

The above represents an abstract function that takes a variable x, which represents anything and returns a variable t, which also represents anything.

It’ll be a little clearer once we see a familiar example. Let’s take the function:

f(x) = x + 2

To represent this in lambda notation all we’d have to write is:

The lambda function takes an x, which returns that x plus two.

To write something like “function that takes an x returns a function that takes a y returns a function that takes a z that returns an n” could be written as:

At this point, any JavaScript developers will be remarking at the similarity of the above to arrow functions in JavaScript…

const x => y => z => { n can be anything here }

Yes, JS arrow functions follow the lambda calculus notation!

Lamba calculus also uses variable binding — once a value or function is assigned to a variable it cannot be overwritten. In the expression above, the variables x, y and z are all bound to represent a certain (albeit, abstract) portion of that function.

We can then take these immutable lambda expressions and compose them together to make larger, more complex functions:

Don’t worry about what this is supposed to represent, it’s just supposed to be a visual for what composing many functions on one line looks like.

There’s so much more to lambda calculus than what I’ve glossed over, but I’m going to cut myself off here to avoid falling down the endless rabbit hole of explaining everything you can do with this type of calculus. Hopefully these brief examples have provided some canvas, on which I can begin to explain functional programming.

(For a more in-depth look, here’s an incredible video explanation by Fullstack instructor Gabriel Lebec: https://www.youtube.com/watch?v=3VQ382QG-y4)


So, I semi, sort-of, don’t really understand lambda calculus…what exactly is functional programming?

For the purposes of how I’ll be explaining it, functional programming is a programming paradigm — it’s just a way of thinking about programming, based on some key principles. We use paradigms to broadly classify programming languages by their features; classification, while rather arbitrary, tends to help with figuring out what these programming languages are best suited for, and for figuring out which are similar in nature.

That sounds alright…so what are the key principles that we use to group languages into the functional bucket?

Generally, we think of these:

  1. Pure functions: given the same input, the function always returns the same output, and has no side effects such as console logs, global variable mutations, etc…just like the lambda calculus!
  2. Function composition: two or more functions can be combined to produce a new function…also like the lambda calculus!
  3. No shared state: avoid the use of any variable, object or general memory that can be controlled by multiple parts of the program like think JavaScript closure or global variables…also like lambda calculus (ok you get the point)
  4. No state mutation: a variable or object cannot be changed after it has been created
  5. No side effects: a function cannot change anything about the program it runs on; nothing that the function produces is observable beyond the value it returns
  6. Higher order functions: functions that take a function as an argument, and potentially return a function (frequently used to handle generic data types)
  7. Declarative: functions describe the flow of data rather than steps used to calculate an end result — this one is a little harder to understand, but basically think of it as writing a short-and-sweet descriptive one-liner like:
filter (>3) [1, 2, 3, 4, 5]

Rather than saying:

let arr = [1, 2, 3, 4, 5];
let result = [];
for(let i = 0; i < arr.length; i ++) {
if(arr[i] < 3) {
result.push(arr[i]);
}
}

Think of declarative as the first one: we are declaring what we are doing with the data in very simple terms, while imperative is represented by the second: we are telling you the steps to reproduce our work.

(For more information on the exact fundamentals of functional programming, this helped me: https://medium.com/javascript-scene/master-the-javascript-interview-what-is-functional-programming-7f218c68b3a0)


Pretty sweet logo

So what is Haskell?

Haskell is just another programming language! It is a purely functional programming language, that is also statically typed, and lazy.

**Purely functional = There are no statements or instructions, only expressions which cannot mutate variables. It’s built into the language that variables or functions cannot be overwritten.

**Statically typed = all the types composed together by function application have to match up at compile time. Basically, you can’t declare something as an Int and use it as a Char in the function body — even if the types are abstract you have to use them consistently or the compiler will get mad.

**Lazy = Functions don’t evaluate their arguments. This just means that the Haskell console delays evaluation of a function until the value output of that function is needed — this is helpful in reducing memory usage.

(For more info: https://www.haskell.org/)

I’m not going to go into explaining every intricacy of the Haskell language, but I’ll do my best to explain what’s going on in the functions we’re writing, and hopefully it will become clear what the function expressions are indicating is happening.

First, it’s important to understand two concepts:

  • Function declaration: in Haskell, the function is declared before it is defined. Function declaration consists of the function name and its argument list along with its output. We saw this in the example add function from above:
add :: Integer -> Integer -> Integer

Our function, called “add” takes in two arguments: an Integer and an Integer and outputs an Integer. The notation “::” is what we use to declare something.

  • Pattern matching: define different methods that can be executed depending on their argument list. Here’s an example using the factorial function:
fact :: Int -> Int
fact 0 = 1
fact n = n * fact ( n - 1 )

We declared our function on line one. Then on line two we tell our function a method it should execute if it receives 0 as an argument. And finally on line 3 we tell our function what to do if it receives a generic integer “n”.

Is that function not beautiful?


Always ask the right questions

Time to rewrite some JavaScript functions!


  • Contains: write a function that takes in an Integer and a list of Integers, and will return true if the list contains the Integer, false if otherwise.

First, we need to declare our Haskell function. It’s name is contains, it takes an Int, an Int List (represented by the [Int] notation) and returns a Bool

contains :: Int -> [Int] -> Bool

Next, we need to address our base case with pattern matching: what is the most basic set of arguments, and what do we do in this case?

contains :: Int -> [Int] -> Bool
contains _ [] = False

*The _ operator in Haskell is a wildcard operator, which just means that it can represent anything

Basically we’re saying, given any input, if we get an empty list then we know that list doesn’t contain the input we’re looking for — return false!

What about the other cases…like if we receive literally any list of integers?

contains :: Int -> [Int] -> Bool
contains _ [] = False
contains el (x:xs)
| el == x = True
| otherwise = contains el xs

This is where it gets a little tricky if you aren’t familiar with pattern matching and recursion.

Now we’re pattern matching for an integer, called el, with a list, which we can represent in Haskell as:

(x:xs)

In Haskell, we can concatenate lists with the : operator. So the x:xs format above is a way of decomposing a list into it’s head, concatenated with the rest of the list.

[1, 2, 3, 4]     -- Original list
1:[2, 3, 4] -- what the x:xs represents

So we’re saying, if we receive an element that is an Int, and a list which isn’t empty, it has a head element, and a tail that is a list, perform these actions:

| el == x    = True
| otherwise = contains el xs

If our el is equal to the head of the list in this case, then return True, we’re done!

Otherwise is just another way of generically saying ‘the element didn’t equal x but we don’t care about the specifics’. Otherwise, call contains again with the same element we’re trying to find, and the list minus the head.

Then contains gets called again with the shorter list, checks if the head element of that list is equal to the element, if it is, we return true, and else, we do that again until we hit the empty list base case — where we return false!

contains :: Int -> [Int] -> Bool
contains _ [] = False
contains el (x:xs)
| el == x = True
| otherwise = contains el xs

Ta, da. Now, how would we write this in JavaScript in a way that maintains the immutability of our functions? Here’s the way I chose to do it, with arrow functions, currying and recursion.

const contains = el => arr => {
if(!arr.length) {
return false;
} else {
const head = arr[0];
const tail = arr.slice(1);
return head === el ? true : contains(el)(tail);
}
}

Since Haskell partially applies all functions, I made it so that our function returns a function that accepts another argument, which is then called when it receives that second argument. So, if you call the function like:

contains(3)

It will return a function that takes in an array, and will return true if that array contains three and false if not.

We can see that, while the function above looks different, it follows the same logic as the Haskell function.

First, we check if the array is empty, if so— return false!

Next, if that array is not empty, we check to see if the element is equal to the head of the array, if it is — return true! Else, call contains again with the same element, and with a copy of the original array, minus the first element. Using JavaScript, we were able to replicate the partial application functionality of Haskell, use recursion, make our code more declarative, and above all, keep our function pure!


Next example:

  • Map: given an array of items, apply a function to every element in that array

Now that we know how to declare a Haskell function we can go ahead and do that. We want a function that has the inputs:

  • A function (which takes in an a and spits out a b)
  • A list of a’s

and then outputs:

  • and spits out a list of b’s

Now we’re getting into the abstract data types — a and b are placeholders for pretty much anything, we just have to keep their implicit meaning consistent throughout the function.

map :: (a->b) -> [a] -> [b]

First things first: cover the base case! If we receive a function and an empty list…return an empty list!

map :: (a->b) -> [a] -> [b]
map f [] = []

Next, we cover the harder part, what to do if the list has stuff in it? Here, using the list head : tail format could be helpful again.

We could pattern match the list with a head, x and a tail xs in the format (x:xs), apply our function to x and concatenate that with the map function applied to the tail.

map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

And it works! We apply f to x, and concatenate that with all of the other results of our recursive call, which looks like this:

map (add 1) [1, 2, 3] -> 2 : map (add 1) [2, 3] -> 3 : map (add 1)..

and when we reach the base case, the final recursive call returns a [] instead of calling the function again, and we get our completed result:

2 : 3 : 4 : [] -> [2, 3, 4]

The map function probably seems pretty familiar from JavaScript! Let’s apply the Haskell concepts again:

const map = fun => arr => {
if(!arr.length) {
return [];
} else {
const head = arr[0];
const tail = arr.slice(1);
return [fun(head), ...map(fun)(tail)];
}
}

This one is very similar to the contains function, but here we use the JavaScript Array spread operator to concatenate the fun(head) with all of the subsequent recursive calls to the map function.


Next example! By now these might start to seem easy…?

  • Filter: given a conditional function that returns true or false, and an array of items, filter the array by the condition

You know the drill: declare our function first! We want a function that takes a function which takes an abstract type and returns a boolean, a list of an abstract type, and the broader function returns a list of that same abstract type.

filter :: (a -> Bool) -> [a] -> [a]

Next, address our base case:

filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []

And finally, the meat:

filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []
filter f (x:xs)
| f x = x : filter f xs
| otherwise = filter f xs

We grab the head and the tail of the list, if the function applied to the head returns true we concatenate the head with our recursive calls, else just make the recursive call until we hit the empty list condition!

Hmmm I wonder if the JavaScript application will look similar…

const filter = fun => arr => {
if(!arr.length) {
return [];
} else {
const head = arr[0];
const tail = arr.slice(1);
return (fun(head) ?
[head, ...filter(fun)(tail)]
:
filter(fun)(tail))
}
}

Note the use of the Array spread […] operator again!


Giphy just auto-redirects me to rick and morty now…

Almost done!

Time for the second-to-last example:

  • Reduce: given a function that combines two values, an array and a base case value, reduce that array into one value

Function declaration — our function has the following inputs:

  • a function that takes two abstract arguments, a and b, and returns an abstract type b
  • a list of abstract type a
  • a base case value of abstract type b

and outputs a value of abstract type b

reduce :: (a -> b -> b) -> b -> [a] -> b

Now, for the base case:

reduce :: (a -> b -> b) -> b -> [a] -> b
reduce f b [] = b

And finally the main case:

reduce :: (a -> b -> b) -> b -> [a] -> b
reduce f b [] = b
reduce f b (x:xs) = f x (reduce f b xs)

This one looks very similar to the others, and while it appears shorter, can be a bit more confusing.

In the secondary case, where we actually receive a list as input, we want to call that “combine” function that we have as an argument on the head of the list, with the second argument being the recursive call. It’s pretty hard to visualize what that’s doing right off the bat, so let’s take a look at an example:

Remember our add function?

add :: Integer -> Integer -> Integer
add x y = x + y

It takes one Integer, and another Integer, and spits out a result Integer! Aka it qualifies for our reduce’s input ‘combine’ function:

(a -> b -> b)

Now, for the example:

reduce add 0 [1, 2, 3, 4, 5]

First step:

We pattern match with the second case we defined:

reduce f b (x:xs) = f x (reduce f b xs)

To put it more concretely:

reduce add 0 1:[2, 3, 4, 5] = add 1 (reduce add 0 [2, 3, 4, 5])

So we end up calling reduce again

reduce add 0 2:[3, 4, 5] = add 2 (reduce add 0 [3, 4, 5])

And again…

reduce add 0 3:[4, 5] = add 3 (reduce add 0 [4, 5])

And again…

reduce add 0 4:[5] = add 4 (reduce add 0 [5])

And again……….

reduce add 0 5:[] = add 5 (reduce add 0 [])

And finally we get to:

reduce add 0 [] = 0

We return something instead of recursively calling the reduce function again!

By now our call stack looks like this:

add(1, add(2, add(3, add(4, add(5, 0)))))

and slowly it executes to one value!

add(1, add(2, add(3, add(4, 5))))

Then

add(1, add(2, add(3, 9)))

Then…

add(1, add(2, 12))

And finally…

add(1, 14)

Gee I wonder what that evaluates to…

15

That was a lot to trace, but hopefully the recursion process makes more sense as a result!

Before I forget, here’s that JS equivalent:

const reduce = combine => base => arr => {
if(!arr.length) {
return base
} else {
const head = arr[0];
const tail = arr.slice(1);
return combine(head)(reduce(combine)(base)(tail));
}
}

So it turns out we can actually apply these functional programming concepts in JavaScript: currying, partial application and pure functions…does this mean JavaScript is also a functional programming language???

JavaScript is a multi-paradigm language, supporting imperative/procedural programming along with OOP (Object-Oriented Programming) and functional programming. JavaScript supports OOP with prototypal inheritance.

(https://medium.com/javascript-scene/10-interview-questions-every-javascript-developer-should-know-6fa6bdf5ad95)

So, yes and no…

Functional programming means that the program is conceptualized as a evaluation of a function, rather than a control flow. The code is a description of functions, and has no inherent concept of a control flow.

JavaScript has got a control flow and is conceptualized as a imperative language.

(https://stackoverflow.com/questions/3962604/is-javascript-a-functional-programming-language)

*control flow: order in which individual statements, instructions or function calls of an imperative program are executed or evaluated

It doesn’t seem like there is a clear-cut answer when it comes to slicing programming languages into different paradigms, especially with a language as versatile as JavaScript. Feel free to comment if I’m wrong, but my main takeaway from this has been…JavaScript can be functional if you want it to be!


Andrew Drummond

Written by

Software Engineer @ Axoni, previously attempted to retain knowledge @ FullstackAcademy and @Wharton

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade