A JavaScript WAT and monoidal folds

This may or may not surprise you, depending on how you think of these functions. In JavaScript, Math.minJavaScript: 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.maxJavaScript: 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.

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:

1. 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.
2. This is the first argument. It’s a value of type Double.
3. This is the second argument, also a value of type Double.
4. 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.

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:

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:

^† 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.

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

1. 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 Integers, 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.
2. The second is some starting or neutral value for the operation. We’ll address this in more detail in a moment.
3. 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.

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 -> aHaskell: (+) documentation
• min :: Ord a => a -> a -> aHaskell: min documentation
• max :: Ord a => a -> a -> aHaskell: 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.

evaluates like this:

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.

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 Integers, 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.