We suppose all programming languages have the occasional watWe 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,
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.
Math.min() documentation. returns one of the following:
- The smallest number passed to it (if all of the arguments are numbers);
NaNif any parameter isn’t a number;
Infinitywhen applied to zero arguments.
Math.max() documentation. returns:
- The largest number passed to it;
NaNif any parameter isn’t a number;
-Infinitywhen applied to zero arguments.
That’s how you get the perhaps unexpected behavior above:
-Infinity, so the expression reduces to
Infinity < -Infinity. This is false, because infinity is greater than negative infinity.
What’s going on here?
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.
Math.max but Haskell has
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,
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
- 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
- This is the second argument, also a value of type
- 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
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
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 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
In summation, please peruse this list of example usages of
Math.min and consider corresponding ways to write the same expression in Haskell:
We can implement the
foldr that is similar to
foldr takes three inputs. Haskell:
- The first argument is a binary function. It takes two arguments, one of type
aand one of type
band returns a value of type
b. The two types,
b, could be different types, but they are often the same type.For example, if we are using
foldrto sum a list of
Integers, then both
ais the type of the values in the list, and
bis 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
(+) :: Num a => a -> a -> aHaskell:
min :: Ord a => a -> a -> aHaskell:
max :: Ord a => a -> a -> aHaskell:
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.
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 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.
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
-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.
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 listThis isn’t important for the current purpose, but the
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
min, which each compare two values of the same type and return the greater or lesser.
So, we have
min, and an identity. Now we can implement
We could implement a
maximum function similarly by changing the binary function from
max and the neutral value from
(-1/0). Using those in the REPL, we can see the desired behavior:
However, in Haskell,
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