Why does length return 1 for a tuple with 2 elements, and gives an error for a tuple with more elements?
You have encountered a Haskell cause célèbre that has sparked much discussion and gnashing of teeth.
Basically, for the purposes of Foldable
(the typeclass that provides length
), 2-tuples are not considered a container of two elements, but a container of one element accompanied by some context.
You can extract a list of elements of type a
from any Foldable a
. Notice that for 2-tuples the type variable of the Foldable
is that of the second element of the tuple, and it can be different from the type of the first element.
If you had a ('c',2) :: (Char,Int)
tuple, it would be no mystery that you couldn't extract two Int
s in that case! But when the types are equal it becomes confusing.
As for why length (1::Int, 1::Int, 1::Int)
fails, 3-tuples don't have a Foldable
instance defined, but perhaps they should have one, for consistency. 3-tuples would also have length 1.
By the way, the Identity
functor, that could be considered a kind of 1-tuple, is also Foldable
and of course has length 1 as well.
Should the Foldable
instance for tuples exist at all? I think the underlying philosophy in favor of yes is one of, shall we call it, "plenitude". If a type can be made an instance of a typeclass in a well defined, lawful way, it should have that instance. Even if it doesn't seem very useful and, in some cases, may be confusing.
I like danidiaz's answer because it provides the high-level intuition about how the Foldable
instance for tuples works and what it intuitively means. However it seems there is still some confusion about the mechanics of it; so in this answer I will focus on the "behind-the-scenes" bits. The full text of the Foldable
instance in question is available online and looks like this:
instance Foldable ((,) a) where
foldMap f (_, y) = f y
foldr f z (_, y) = f y z
You can already see from this instance that the first part of each tuple is completely ignored in all Foldable
methods. However, to complete the picture, we need to look at the definitions for minimum
and length
. Since this instance does not include definitions for minimum
and length
, we should look at the default definitions for these. The class declaration for Foldable
looks like this (with irrelevant bits elided):
class Foldable t where
length :: t a -> Int
length = foldl' (\c _ -> c+1) 0
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
where f' x k z = k $! f z x
minimum :: forall a . Ord a => t a -> a
minimum = fromMaybe (error "minimum: empty structure") .
getMin . foldMap (Min #. (Just :: a -> Maybe a))
So now, let's expand these definitions and see where they get us.
length (a, b)
= { definition of length }
foldl' (\c _ -> c+1) 0 (a, b)
= { definition of foldl' }
foldr (\x k z -> k $! (\c _ -> c+1) z x) id (a, b) 0
= { definition of foldr }
(\x k z -> k $! (\c _ -> c+1) z x) b id 0
= { beta reduction }
id $! (\c _ -> c+1) 0 b
= { id $! e = e }
(\c _ -> c+1) 0 b
= { beta reduction }
1
Note that the conclusion holds regardless of what we plug in for a
and b
. Now let's do minimum
. For our purposes, we will replace (#.)
with (.)
-- the only difference is efficiency, which we don't care about for this particular line of reasoning.
minimum (a, b)
= { definition of minimum }
( fromMaybe (error "minimum: empty structure")
. getMin
. foldMap (Min . Just)
) (a, b)
= { definition of (.) }
( fromMaybe (error "minimum: empty structure")
. getMin
) (foldMap (Min . Just) (a, b))
= { definition of foldMap }
( fromMaybe (error "minimum: empty structure")
. getMin
) ((Min . Just) b)
= { definition of (.) }
fromMaybe (error "minimum: empty structure")
(getMin (Min (Just b)))
= { definition of getMin }
fromMaybe (error "minimum: empty structure") (Just b)
= { definition of fromMaybe }
b