[Haskell-cafe] is 256M RAM insufficient for a 20 millionelementInt/Int map?

[Claus Reinke]

>> (hint to ghc hackers: 'Data.Map.Map Int !Int' and '[!a]' would really be useful!-),
> 
> I can't figure out what that means though.  Strictness is not a
> property of types or of values, it is a property of functions.   [!]
> is not a subtype of [] ; IOW, there is no a such that [a] = [!Int]
> (where [!Int] is a list with strict values).  For example, if we
> allowed this, the following property breaks:
> 
>  length xs == length (map f xs)
> 
> Since it is not true on strict lists.

I'm not entirely sure this couldn't be worked out. Let's say that
every type breaks into terminating and non-terminating computations:

    a = !a | ^a

For your equation to break, you're assuming implicit conversions
between some 'a' and '!a', ie, something like

    (undefined :: a) :: !a
    (const undefined :: a -> b) :: !a -> !a

But those shouldn't typecheck! We can't decide termination, so not
all objects of type 'a' can be classified into the subtypes '!a' or '^a'.
Membership in '!a' can be constructive only, and map for strict lists 
would have a type somewhat like this

    mapS :: !(!a -> !a) -> [!a] -> [!a]

Without a function, 'mapS' can't construct an element-strict result list,
hence the first '!' (and 'mapS undefined' won't typecheck). Nor can it
do so without a function that can construct (or pass on) strict elements,
hence the '!' on the result type of the parameter function (so 'mapS 
(const undefined)' won't typecheck, either). Since there are no ways 
of producing an arbitrary '!a' out of thin air, polymorphic parameter 
functions will have type '!a->!a' (if 'a' gets specialised, eg to 'Int',
then trivial 'Int->!Int' functions are possible).

Being conjured out of thin air, none of this might not hold up under 
closer scrutiny, but papers like [1] suggest that it isn't entirely out of
reach  - further references or counterexamples appreciated!-)

Claus

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8984
    Unboxing using specialisation, Simon L. Peyton Jones and Patrick M. Sansom