Unlifted data types

[Richard Eisenberg]

On Sep 9, 2015, at 8:57 AM, Simon Peyton Jones <simonpj at microsoft.com> wrote:

> |  I mean that, for example, `length` will work over both strict lists
> |  and lazy lists. It will infer the strictness of its argument through
> |  ordinary type inference. So users have to be aware of strictness, but
> |  they will be able to use the same functions in both cases.
> 
> I didn't understand that.  You mean that 'length' will be levity-polymorphic, but 'map' will not?  What are the rules for determining which is which?  (Which functions, exactly, can be levity-polymorphic???
> 

No functions (excepting `error` and friends) are truly levity polymorphic. We use levity polymorphism in the types to get GHC to use its existing type inference to infer strictness. By the time type inference is done, we must ensure that no levity polymorphism remains, because the code generator won't be able to deal with it.

For example, `map :: (a -> b) -> [a] -> [b]` has 4 places where levity polymorphism comes into play: the type a, the type b, the source list, and the result list. Any of these could be lazy or strict. And, I believe, all the combinations make sense. This means that we have one source Haskell declaration -- map -- that corresponds to 16 compiled functions. Obviously we wish to optimize somehow, and perhaps if we can't, this idea is bogus. But this is the basic idea.

To be clear, nothing is different about `length` than `map` -- the fact that length is a consumer is utterly irrelevant in my example.

Richard