Haskell often provides two versions of a given function f, i.e:
f :: Int ...
genericF :: Integral i => i ...
There exist many standard library functions with those two versions: length, take, drop, etc.
Quoting the description of genericLength:
The genericLength function is an overloaded version of length. In particular, instead of returning an Int, it returns any type which is an instance of Num. It is, however, less efficient than length.
My question is: where does the efficiency loss comes from? Can’t the compiler detect that we are using genericLength as an Int and therefore us length for better performance? Why isn’t length generic by default?
1
It’s the same reason as why we have map and fmap. Error messages/usability for newbies.
It’d by mighty confusing for many a new programmer to write
myLength = subtract 1 . genericLength
x = myLength [1, 2, 3] :: Int
y = myLength [1, 2, 3] :: Integer
and get an error complaining about the monomorphism restriction. Plus which do you prefer
Couldn't match expected type "Integer" with type "Bool"
or
No instance for Num Bool arising from usage ....
It’s simply a matter of usability.
Furthermore, in a lot of cases you end up just wanting defaulting anyways, such as with function composition
evenElems = even . subtract 1 . genericLength
vs
default ()
evenElems = even . genericLength -- Error ambiguous type variable.
Here we just want GHC to “pick” a random Num type and we really don’t care which (it’s Integer IIRC).
If everything was fully generic the defaulting rules would get um.. murky. Since As of right now there are only 4 things that are automatically available as defaults and no way to set anything fine grained (per function).
As for efficiency, typeclasses means lugging potentially lugging typeclass’s dictionary and defaulting to Integer which is much more expensive than Int.
There are alternative preludes (I think classy prelude is unmaintained, but interesting) that do attempt to be as generic as possible. Using them is as simple as
{- LANGUAGE NoImplicitPrelude #-}
import My.Super.Awesome.Prelude
3
Aside from usability, the reason seems to indeed be to avoid performance degradation. In the recent Foldable in GHC7.10 Prelude’s FAQ
lengthis left ungeneralized with regards to the numeric type primarily becausegenericLengthhas absolutely abysmal performance. One of the pragmatic guidelines we followed is that we can’t make code slower.
By looking at the implementation:
length
{-# NOINLINE [1] length #-}
length :: [a] -> Int
length l = lenAcc l 0#
lenAcc :: [a] -> Int# -> Int
lenAcc [] a# = I# a#
lenAcc (_:xs) a# = lenAcc xs (a# +# 1#)
genericLength
genericLength :: (Num i) => [a] -> i
{-# NOINLINE [1] genericLength #-}
genericLength [] = 0
genericLength (_:l) = 1 + genericLength l
length has a tail-recursive implementation, and the helper function lenAcc can probably be inlined. This might explain the difference, but I’m not sure if there’s more to it.
4