[Haskell] Re: Compilation of big, static tables

Simon Marlow simonmarhaskell at gmail.com
Thu Feb 23 07:35:51 EST 2006


Malcolm Wallace wrote:
> Stefan Karrmann <S.Karrmann at web.de> wrote:
> 
> 
>>can ghc compile huge tables into efficient code if they are constant
>>at compile time?
> 
> 
> I have a related but different question.  If I have large, statically
> defined tables of data e.g.
> 
>     table = listArray (0,max) [ [1,2,3,4]
>                               , [5,6,7,8,9,10]
>                               , [11,12,13]
>                               ...
>                               ]
> 
> i.e. no computation is required, can these be compiled directly to a
> space-efficient lookup structure?  Compilers might do something
> reasonable for large static strings of chars, but they cannot do the
> same for arrays.  The trouble is that the Array types are abstract, so
> one cannot use the natural literal constructor.
> 
> What I would really like is a syntax to statically construct an array,
> without having to compute it from a list.  I'm not sure that even
> Template Haskell can help here, since there is no normal form for it to
> translate to.

This has always been a weakness in GHC, and perhaps in Haskell itself. 
In theory GHC could compile a completely static array declaration (like 
yours above) into a static array, but it doesn't.  It's not trivial to 
do, because it involves unrolling the (recursive) definition of 
listArray, or perhaps some special-case code to spot array/listArray 
applied to static lists.

Happy & Alex use the hack of encoding static arrays as strings and using 
peek to access the data at runtime, FWIW.

Cheers,
	Simon


More information about the Haskell mailing list