Memoizing a Haskell Array

Question

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.

Not sure what your problem is: crc32Table is already the memoized tbl function. — Ingo
– Ingo, Commented Apr 4, 2011 at 8:44
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
– luqui, Commented Apr 4, 2011 at 8:51
@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
– Ingo, Commented Apr 4, 2011 at 9:01
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
– augustss, Commented Apr 4, 2011 at 11:07

Community · Accepted Answer · 2017-05-23 11:47:41Z

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.

edited May 23, 2017 at 11:47

CommunityBot

11 silver badge

answered Apr 4, 2011 at 13:57

sclv

39k7 gold badges102 silver badges208 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Memoizing a Haskell Array

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related