[Haskell-cafe] data structures question

[Matthias Fischmann]

On Wed, Aug 30, 2006 at 03:11:35PM +0200, Tamas K Papp wrote:
> [...]
> 
> The mathematical description of the problem is the following: assume
> there is a function V(a,b,theta), where a and b can have two values,
> High or Low, and theta is a number between zero and n (n is given).
> The range of V is the real numbers.
> 
> Then there is an algorithm (called value iteration, but that's not
> important) that takes V and produces a function of the same type,
> called V'.  The algorithm uses a mapping that is not elementwise, ie
> more than the corresponding values of V are needed to compute a
> particular V'(a,b,theta) -- things like V(other a,b,theta) and
> V(a,b,theta+1), where
> 
> data State = Low | High
> other :: State -> State
> other High = Low
> other Low = High
> 
> Question 1: V can be represented as a 3-dimensional array, where the
> first two indices are of type State, the third is Int (<= n).  What
> data structure do you suggest in Haskell to store V?  Is there a
> multidimensional array or something like this?

There are: http://haskell.org/onlinereport/array.html

(There are other implementations with destructive updates and a more
comfortable API, but pure Haskell98 is probably the best thing to
start with.)

The trick is that Int is not the only index data type, but tuples of
index data types are, too.  Do this:

| type Point = (State, State, Int)
| type TypeV = Array State Double
| 
| matrix :: TypeV
| matrix = array bounds values
|    where
|    ...

> Let's call this structure TypeV.
> 
> Question 2: I would like to write
> 
> valueit :: TypeV -> TypeV
> valueit V = mapondescartesproduct [Low,High] [Low,High] [0..n] mapV where
> 	    -- mapV would calculate the new V' using V
> 	    -- mapV :: State -> State -> Int -> Double

I think Array.ixmap is pretty much doing what you want, with slightly
different typing.

hth?
matthias
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060830/23eaec25/attachment.bin