1

Continuing with my looking into CRCs via Haskell, I've written the following code to generate a table for CRC32 calculation:

crc32Table = listArray (0, 255) $ map (tbl 0xEDB88320) [0..255]

tbl polynomial byte = (iterate f byte) !! 8
    where f r = xor (shift r (-1)) ((r .&. 1) * polynomial)

This correctly generates the table. I want to make frequent accesses to this table but 1) don't want to hardcode the results into code and 2) don't want to recalculate this table every time I reference it.

How would I memoize this array in Haskell? The Haskell memoization pages haven't given me any clues.

Muchin
  • 4,887
  • 4
  • 23
  • 25
  • 1
    Not sure what your problem is: crc32Table is already the memoized tbl function. – Ingo Apr 04 '11 at 08:44
  • Really? How do I tell if it is already memoized? – Muchin Apr 04 '11 at 08:51
  • 1
    memoizing is the process of indexing a *function*'s arguments by a data structure. Array is already a data structure, so memoizing doesn't really make any sense. – luqui Apr 04 '11 at 08:51
  • @Muchin, you could use `Debug.Trace` and `crc32Table = trace "Evaluating" $ listArray (0, 255) ...`. That will print "Evaluating" whenever the expression is evaluated. If it is memoized, it should only print "Evaluating" once. – luqui Apr 04 '11 at 08:52
  • 1
    @Muchin - unless crc32Table is a function or something like Num a => Array a, you can be pretty sure that it is only computed once. – Ingo Apr 04 '11 at 09:01
  • I was under the impression that if I called crc32Table over and over, it would re-create the array over and over. But now, I don't understand when Haskell will cache the array and when it recreates it. – Muchin Apr 04 '11 at 09:02
  • 1
    But you don't call crc32Table, you just index into it. Anything at the top level will persist as long as you can reference it. – augustss Apr 04 '11 at 11:07

1 Answers1

4

The discussion at this question should help explain what's going on: When is memoization automatic in GHC Haskell?

As folks have said in comments, crc32Table, if it is monomorphically typed should only be computed once and retained.

Community
  • 1
  • 1
sclv
  • 38,665
  • 7
  • 99
  • 204