# A JavaScript WAT and monoidal folds

We suppose all programming languages have the occasional *wat* We believe the origin of this use of the term is from this lightning talk by Gary Bernhardt., some function or behavior that is surprising and makes you think, “wait, what?” From time to time, one of these will go viral on Twitter, and we all have a good laugh-cry at how absurd programming can be.

When this tweet first appeared in our timelines,

Fortunately, JavaScript has always supported #alternativefacts

`Math.min() < Math.max() => false`

we had a chat about it, compared it to Haskell’s equivalents, and tried to figure out how another language might do better.

We’re going to use this as an excuse here to talk about folds, monoids, and why you should care.

## The WAT

```
> Math.min() < Math.max() false
```

This may or may not surprise you, depending on how you think of these functions. In JavaScript, `Math.min`

JavaScript: `Math.min()`

documentation. returns one of the following:

- The smallest number passed to it (if all of the arguments are numbers);
`NaN`

if any parameter isn’t a number;`Infinity`

when applied to zero arguments.

Whereas `Math.max`

JavaScript: `Math.max()`

documentation. returns:

- The
*largest*number passed to it; `NaN`

if any parameter isn’t a number;`-Infinity`

when applied to zero arguments.

That’s how you get the perhaps unexpected behavior above: `Math.min()`

is `Infinity`

and `Math.max()`

is `-Infinity`

, so the expression reduces to `Infinity < -Infinity`

. This is false, because infinity is greater than negative infinity.

In Haskell, the situation is different but hardly better:Haskell: `minimum`

documentation

Haskell: `maximum`

documentation

```
λ> minimum [] < maximum []
*** Exception: Prelude.minimum: empty list
```

What’s going on here?

JavaScript has defined values for these functions to return when they are given an empty collection of arguments. But in Haskell, there is no such value defined for these functions. This isn’t, as it happens, quite true. There is a value they could return (`Nothing`

), if the return type were `Maybe a`

instead of `a`

. But they were written to throw an exception anyway – for “historical reasons,” we assume. See here for source code. How they should behave when they are given no arguments is undefined, so it just spits this nasty exception at us.

## JavaScript versus Haskell

We will be comparing Haskell with JavaScript, but one difficulty with that is Haskell has two functions where JavaScript has one – or, Haskell has four where JavaScript has two. JavaScript has `Math.min`

and `Math.max`

but Haskell has `minimum`

, `min`

, `maximum`

, and `max`

. Let’s take a moment to understand why. To avoid doubling the discussion, we’ll focus on the “minimum” functions.

Haskell has two functions, `min`

and `minimum`

, that are closely related but different. `min`

is the simpler of the two. The `min`

function takes exactly *two* arguments. This is the type signature of `min`

:

```
min :: Double -> Double -> Double
-- 1 2 3 4
```

- This double colon syntax means “has the type”. All functions and all values in Haskell have a type, and this syntax is used to annotate a name with a type.
- This is the first argument. It’s a value of type
`Double`

. - This is the second argument, also a value of type
`Double`

. - This is the return or result value. For
`min`

, it will be the lesser of the two arguments.

But Haskell makes a stronger distinction between a thing and a list of those things. Because we have static types that resolve at compile time, we must make the distinction up front about whether we have a single value or an arbitrarily long list of them. And so, we have the `minimum`

function; in contrast to `min`

, the `minimum`

function takes *one* argument, but the argument is a list and can be as long as you like.

`minimum :: [Double] -> Double`

This takes a list of `Double`

numbers and returns one of those values. Since this is the `minimum`

function, it returns whichever is smallest. `minimum`

reduces the list to a single value by recursively applying `min`

to pairs of elements from the list. In this way, `minimum`

is more complicated than `min`

and relies on `min`

for its implementation.

Instead of providing only the more general `minimum`

function, Haskell’s `base`

package provides you with both. Most of the time when you want `min`

, it’s because you’re implementing something that will work over a large collection of values, such as a list of them, but `min`

and the other basic functions in the `Ord`

typeclass are exposed in the `base`

library to provide those building blocks and also to provide a conceptual basis for what *ordering* means.

We got a bit ahead of ourselves, because above we showed you the types of the `min`

and `minimum`

functions specialized to the type `Double`

. In fact, they work with many types – most numbers, and some other things, such as alphabetic characters, as well. What all those types have in common is a concept of being *ordered*. The `Ord`

typeclass defines the set of functions that represent the essence of what it means for values to be orderable or comparable. A partial list of the functions in `Ord`

:

```
class Eq a => Ord a where
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
max :: a -> a -> a
min :: a -> a -> a
```

The `Ord`

typeclass declares these functions but does not implement them because the implementation varies based on what `a`

is. If you can implement these functions sensibly for a given type, You don’t have to write implementations for all the functions in a typeclass. Many typeclasses, including `Ord`

, have one or two functions that you must implement for your type, and the rest can be inferred or derived from those. So, if you implement `(<=)`

for a type, you get the rest of the ordering functions for free. then that type is orderable and has access to all of these functions and, more generally, to all functions that are defined to work with `Ord`

constraints, which includes `sort`

.

JavaScript made a different choice about how this should all work than Haskell did, so `Math.min`

can take different numbers of arguments where Haskell’s versions cannot. Haskell does not really have an equivalent to the variadic syntax of JavaScript, although lists and some similar data structures can be used similarly.

In summation, please peruse this list of example usages of `Math.min`

and consider corresponding ways to write the same expression in Haskell:

JavaScript | Haskell |
---|---|

`Math.min(4,5)` | `min 4 5` |

`Math.min(...[4,5])` | `minimum [4,5]` |

`Math.min(4,5,6)` | `min 4 (min 5 6)` ^{†} |

`Math.min(...[4,5,6])` | `minimum [4,5,6]` |

^{†} This one isn’t as much of a direct translation as the others, because there isn’t quite an analog in Haskell to variadic functions in JavaScript.

## Folds reduce

Regardless of how the JavaScript functions may be implemented, we can see from their behavior that they are at least conceptually similar to the Haskell functions. They take a collection of items, apply an operation that compares two values at a time over that collection, keeping track of the current state, and return a final result. In Haskell, we do this with a *fold*; you might know the concept of folding in JavaScript by the name `reduce`

.JavaScript: `Array.reduce()`

documentation

We can implement the `minimum`

and `maximum`

functions in Haskell to mimic the behavior of the JavaScript functions using a function called `foldr`

that is similar to `reduce`

. Folds in Haskell can be used on data structures other than lists, but we’ll stick with talking about lists in this article as that most closely mimics the variadic nature of the JavaScript functions.

`foldr`

takes three inputs.Haskell: `foldr`

documentation

```
foldr :: (a -> b -> b) -> b -> [a] -> b
-- 1 2 3
```

- The first argument is a binary function. It takes two arguments, one of type
`a`

and one of type`b`

and returns a value of type`b`

. The two types,`a`

and`b`

, could be different types, but they are often the same type. For example, if we are using`foldr`

to sum a list of`Integer`

s, then both`a`

and`b`

are`Integer`

.`a`

is the type of the values in the list, and`b`

is the type of the “start” or identity value. - The second is some starting or neutral value for the operation. We’ll address this in more detail in a moment.
- The third is a collection, such as a list, of values of type
`a`

. The square brackets are list syntax in Haskell.

The second argument – that neutral initial value – is worth making a further comment about. When we talk about folds in Haskell, that argument is commonly called the “start” or “acc” value – “acc” being short for “accumulator.” It is often the *identity value* of the operation, but it’s also where the “state” of the computation “accumulates” as the function is recursively applied over the collection.

An identity value for an operation is a value that doesn’t change the value of any other arguments:

- Adding any number to zero gives you back that number; zero is the identity value of the binary operation
*addition*for integers and some, but not all, types of numbers. - Multiplying by one always gives you the number you started with; one is the identity value of the binary operation
*multiplication*defined over integers and so on. - Adding any list to an empty list and you just get back the list you started with; an empty list is an identity value for the binary operation
*list concatenation*.

Addition and multiplication over integers and concatenation of lists are *monoids*.

## Folds, identities, monoids

When we fold, the operation we use to “fold up” the collection is a binary operation, such as addition or `min`

or `max`

.

`(+) :: Num a => a -> a -> a`

Haskell:`(+)`

documentation`min :: Ord a => a -> a -> a`

Haskell:`min`

documentation`max :: Ord a => a -> a -> a`

Haskell:`max`

documentation

By *binary* we mean that it takes two arguments. It is also usually the case that you could reparenthesize a succession of such operations and not change the outcome (the property known as *associativity*). Some folding functions, such as `foldr`

, may be used with non-associative folding functions, such as subtraction or exponentiation. Some folds, such as `foldMap`

which we’ll look at in the next lesson, can only work with associative operations, such as addition or multiplication. Such folds are *monoidal* as they require a *monoid* to work. This monoid part will be important when we look at the actual functions in Haskell.

We can consider a set (such as integers) together with such an operation over it as a single structure. If there is an *identity* or neutral element of the set for the operation, that structure is called a *monoid*. If there is not an identity element, the structure is merely a *semigroup*. Every monoid is also a semigroup, but not every semigroup is a monoid.

In JavaScript, finding the minimum or maximum of a collection of values is a *monoidal* operation: it uses a binary, associative operation to reduce the collection, and there are identities defined for those operations; `Infinity`

for `Math.min`

and `-Infinity`

for `Math.max`

. Having those identity values means that when no arguments are passed to the function, there is still a value it can return.

Let’s take a moment and convince ourselves that `Infinity`

and `-Infinity`

*are* identity values for these functions. If we think of an identity value as the value that always returns the other argument (to a binary function) unchanged, then they do suit this purpose.

The `min`

function compares two values of the same type and returns the smaller, or minimum, of the two. It’s the function that we’ll use to fold up our list of floating point numbers. If you are comparing two values, any value will be smaller than `Infinity`

, so passing `Infinity`

in as one of the arguments to `min`

`Infinity`

and `-Infinity`

are not Haskell code, so we have to use these division equations for those values. will return the other value unchanged. No matter how big your number is, it will be less than `Infinity`

. Yes, yes, unless it *is* Infinity, in which case it’s just the same.

```
λ> min (100000) (1/0)
100000.0
```

We’ll ignore some details of how folds recurse in Haskell, but we can think of it peeling one value of type `a`

off the list, passing it as one argument to the folding function, and then updating the “state” in the form of changing the “acc” value of type `b`

for the next iteration. In the first application of the binary function, you need a “start” value to serve as the other argument (along with one of the values in the list) since we only peel one value out of the collection at a time.

Let’s look at a hypothetical example. We can write a `sum`

function like this:

The first argument to `foldr`

is a binary operation, `(+)`

. The second argument is the identity value for integer addition. The third is the list of integers. `foldr`

begins evaluating its function applications at the end of the list This isn’t important for the current purpose, but the `r`

in `foldr`

stands for “right” meaning “right-associative”. It groups the function applications from the right; that’s why it’s the last element of the list that gets passed to the addition operation first. The left-associating variant, called `foldl`

exists, but we do not usually recommend using it (the reasons are really out of the scope of this article). so it takes the last element of the list and the “start” value – 0 in this case – as the two arguments to the first addition.

`sum [1, 2, 3, 4, 5]`

evaluates like this:

`1 + (2 + (3 + (4 + (5 + 0))))) (`

If we pass an empty list, analogous to an empty set of arguments, to the folding function, it will return that start or neutral value as the result. So, the start value isn’t *just* the identity for the operation or the place where the state of each computation gets tracked; it’s also our default return value in case the function doesn’t have any other arguments to apply to.

## JavaScript in Haskell

We can implement `maximum`

and `minimum`

in Haskell in ways that are analogous to the JavaScript by making that start value `Infinity`

or `-Infinity`

. Then when we pass it an empty argument, it will return that value and give us the same behavior as the JavaScript. Our binary operation will be `max`

and `min`

, which each compare two values of the same type and return the greater or lesser.

```
λ> :type min
min :: Ord a => a -> a -> a
λ> :type max
max :: Ord a => a -> a -> a
λ> min 3 6
3
```

So, we have `foldr`

, `min`

, and an identity. Now we can implement `minimum`

, the JavaScript way.

That should be equivalent to the following in JavaScript:

We could implement a `maximum`

function similarly by changing the binary function from `min`

to `max`

and the neutral value from `(1/0)`

to `(-1/0)`

. Using those in the REPL, we can see the desired behavior:

```
λ> minimum []
Infinity
λ> maximum []
-Infinity
λ> minimum [] < maximum []
False
```

However, in Haskell, `minimum`

and `maximum`

are written to be more general than this. The way we’ve written it here will only work with certain types of numbers, Haskell has a lot of types of numbers, including bounded `Int`

types, unbounded `Integer`

s, and various fractional and floating point types. Since integer division by zero results in a “divide by zero” exception, rather than “infinity”, we can’t use these functions as written with integers, but it seems clear we’d want to have a `minimum`

and `maximum`

function that could. but the real functions work with values of many types. Next we’ll look at a way to preserve the generality of the functions while keeping the JavaScript behavior.