How to create an Haskell array from a function

Question

For caching purposes, I want to create an array, which maps input values of the function to output values. I know, that my function will be used only in this specific range, I think about something like this:

MyType = ... deriving (Ix)

myFunction :: MyType -> foo

myCache = createArrayFromFunction (start,end) myFunction

Is this possible or do I just think "not functional" and there is another solution. I need arrays, because I need O(1) access to the members and know the length from the beginning.

Answer 1

If you just want to create a cache, then you can just use listArray and map, as long as you have a list of all your indices:

myCache :: Array MyType Foo
myCache = listArray (start,end) . map myFunction $ range (start,end)

I assumed that MyType has an Enum instance here; if it doesn't, you'll need some other way to generate a list of valid inputs, which depends on your type. As Reid Barton pointed out, this is what range is for.

Another option, if you want to present a function to the user, would be

myInternalFunc :: MyType -> Foo
myInternalFunc mt = (complex calculation) (using mt)

myFuncCache :: Array MyType Foo
myFuncCache = listArray (start,end) . map myFunction $ range (start,end)

myFunction :: MyType -> Foo
myFunction = (myFuncCache !)

Then you wouldn't export myInternalFunc from your module; you probably wouldn't export myFuncCache either, but I could imagine needing it. If you aren't in a module, you could put myInternalFunc in a let- or where-block within myFuncCache. Once you do this, myFunction mt just does a cache lookup, and so is O(1).

Answer 2

If you're looking at arrays then also consider Vector. Aside from fusion and powerful splicing function, an important difference worth noting is Vectors are all Int indexed. Using this library your generation function is:

generate :: Int -> (Int -> a) -> Vector a