6

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?

Improve this question
1

2 Answers 2

Reset to default
4

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
Improve this answer
3
  • "As for efficiency, typeclasses means lugging potentially lugging typeclass's dictionary and defaulting to Integer which is much more expensive than Int." Perhaps you might want to explain why the compiler cannot simply replace the generic code with the concrete version. A human can do it, so why couldn't (or shouldn't) a compiler not do this as well? Doesn't GHC have a SPECIALIZE pragma just for this? If so, why is this pragma needed instead of inferred? Commented Sep 10, 2013 at 21:53
  • What happens if the code is called with dozens or hundreds of types? It can be a source of unnaceptable code bloat if you keep specializing Commented Sep 10, 2013 at 23:33
  • @ThomasEding GHC does attempt to optimize and specialize where possible, but it isn't guaranteed to IIRC. See classes jim but not as we know them by spjThe bigger problem is the the default Integer Commented Sep 10, 2013 at 23:38
4

Aside from usability, the reason seems to indeed be to avoid performance degradation. In the recent Foldable in GHC7.10 Prelude's FAQ

length is left ungeneralized with regards to the numeric type primarily because genericLength has 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.

Improve this answer
4
  • 1
    Is there not a way to define optimized genericLength implementations for each concrete type? (And then if the concrete type that is used is not one in that set then just use the general, slow, implementation.) Then when the compiler knows what type it wants to use, it could switch it out for that. Commented Mar 28, 2016 at 23:04
  • RULES can probably be used for this, but I'm not sure if specializing on the return type might be an issue... a couple of relevant SE links: stackoverflow.com/questions/19745038/… stackoverflow.com/a/10535043/293735 Commented Mar 29, 2016 at 0:27
  • @beradrio it seems like the problem that was encountered in the first link was due to typeclasses right? So return type as long as its a concrete type should work ok? Commented Mar 29, 2016 at 1:15
  • Yes, I just linked them because they are relevant to understand RULES used for specialization (the manual deals has only a small example, with no further discussion) Commented Mar 29, 2016 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.