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

Claus Reinke claus.reinke at talk21.com
Sun Oct 19 10:32:08 EDT 2008

```>> (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

```