[Haskellcafe] data structures question
Matthias Fischmann
fis at wiwi.huberlin.de
Wed Aug 30 09:33:51 EDT 2006
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 3dimensional 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 nontext attachment was scrubbed...
Name: not available
Type: application/pgpsignature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskellcafe/attachments/20060830/23eaec25/attachment.bin
More information about the HaskellCafe
mailing list