Haskell Foldable Wats

Inspired by Haskell Foldable Wats on the Haskell mailing lists.

Do you know what happens if you ask Haskell for the minimum value of a two-element tuple?

Prelude> minimum (1,2)
2

Not particularly intuitive, is it? Let's work out why this happens.

First, let us see how minimum itself is defined. A Hoogle query produces the following result:

minimum :: Ord a => [a] -> a

That function certainly cannot work with a tuple because it requires a list as its argument. GHCi offers us an alternative, more general version, which is now the one used in base (Hoogle's information appears to be out of date):

Prelude> :t minimum
minimum :: (Ord a, Foldable t) => t a -> a

In the Data.Foldable source, we finally find the cause of our concern:

-- | The least element of a non-empty structure.
minimum :: (Foldable t, Ord a) => t a -> a
minimum = foldr1 min

At each step, a right fold with min takes the element in the accumulator and an element from the structure—in our case, the tuple—compares them, and keeps the smaller one in the accumulator. To keep the function polymorphic, the initial accumulator value is not supplied explicitly; the first value from the structure is used instead. This logic is provided by foldr1, a version of the right fold for non-empty Foldable types:

-- | A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty structures.
--
-- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@
foldr1 :: (a -> a -> a) -> t a -> a
foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                (foldr mf Nothing xs)
  where
    mf x m = Just (case m of
                     Nothing -> x
                     Just y  -> f x y)

If the structure being folded is empty, foldr returns Nothing, which fails the fromMaybe check and raises an error. Otherwise, when the structure is non-empty, mf wraps the first value in the structure in Just on the first step, after which the fold proceeds as usual. If we assume that the elements of a tuple structure are the first and second values of the tuple, everything should work as expected, and the minimum element of (1,2) should be one.

All that remains is to recall the definition of foldr for a tuple—the problem can only be hiding there. And indeed it is:

instance Foldable ((,) a) where
    foldMap f (_, y) = f y
 
    foldr f z (_, y) = f y z

A right fold over a two-element tuple ignores its first element and applies the supplied function f to the tuple's second element and the initial value. In other words, a two-element tuple is a container that stores only its second element. This is sensible behaviour because we have no guarantee that the types of the first and second elements are compatible. As a result, however, a right fold without an initial value never even calls the function: it simply returns the tuple's second element!

Prelude> foldr1 min (1,2)
2
Prelude> foldr1 (*) (1,2)
2
Prelude> foldr1 (+) (1,2)
2

Thanks to lazy semantics, even the following works:

Prelude> foldr1 (+) (undefined,2)
2
Prelude> foldr1 undefined (undefined,2)
2

Likewise, every library function that uses a right fold will produce an unintuitive result for people who are only beginning to tie their lives to Haskell.

Prelude> sum (3,2)
2
Prelude> prod (3,2)
2
Prelude> or (True,False)
False

The problem would not be quite so significant if it were not for the widespread habit of writing things like:

type MyComplex = (Double,Double)

People then wonder what on earth is happening to their programs. The link at the beginning of the article leads to a heated discussion about “how we ended up here”, “this nonsense did not happen in the old days [of Haskell 98]”, and much else besides. It is a highly entertaining read. SPJ has already weighed in—on the side of those calling for the destruction of Foldable (,) a—so the matter will presumably be resolved somehow. In the meantime, we can draw three simple conclusions:

1. Implementing everything under the sun through Foldable works well only when every Foldable instance is sensible, unlike tuples.
2. Tuples should be used only for temporary values, not as important types in the logic of a program.
3. A custom record type should always be preferred over a tuple.