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.

This is entirely functional (and I do it quite often). In fact, you can define a createArrayFromFunction function so that your code will work. — Reid Barton
– Reid Barton, Commented Oct 17, 2010 at 14:13

Antal Spector-Zabusky · Accepted Answer · 2010-10-17 14:54:58Z

6

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).

edited Oct 17, 2010 at 14:54

answered Oct 17, 2010 at 13:48

Antal Spector-Zabusky

36.8k7 gold badges79 silver badges143 bronze badges

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

4 Comments

Reid Barton Over a year ago

Use range (start, end) (haskell.org/ghc/docs/6.12.1/html/libraries/base-4.2.0.0/…), not [start..end].

Antal Spector-Zabusky Over a year ago

@Reid: Thanks! I don't use Arrays much.

fuz Over a year ago

The reason is just, that I know, that my function takes only some 500 specific input values, but it takes a long time to calculate the results. Thx.

nont Over a year ago

Can anyone tell me if this array cache is calculated lazily?

Thomas M. DuBuisson · Accepted Answer · 2010-10-17 19:10:39Z

3

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

answered Oct 17, 2010 at 19:10

Thomas M. DuBuisson

64.9k7 gold badges114 silver badges170 bronze badges

2 Comments

fuz Over a year ago

The problem is: I want something which isn't Int indexed.

Thomas M. DuBuisson Over a year ago

If you have an Enum then what you are using IS Int indexed in a manner of speaking. Indeed, if your type is an instance of Ix it shouldn't be hard to make a wrapper around Vector for your indexing needs.

Collectives™ on Stack Overflow

How to create an Haskell array from a function

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related