Hi, Having read some tutorials, I would like to start using Haskell "for real", but I have some questions about data structures. 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? 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 to fill the new data structure. How to do this sensibly? Thanks, Tamas
Tamas K Papp wrote:
Hi,
Having read some tutorials, I would like to start using Haskell "for real", but I have some questions about data structures.
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?
Read http://haskell.org/haskellwiki/Modern_array_libraries It sounds like you need Data.Array (lazy) or Data.Array.Unboxed (strict)
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
to fill the new data structure. How to do this sensibly?
Your definition is almost clear. mapV takes the i :: (State,State,Int) index of an entry in V' and takes the whole old array V and computes the value at location i in V'. data State = Low | High deriving (Eq,Ord,Ix) -- assuming Ix is derivable... type TypeV = Array (State,State,Int) Double -- or UArray instead of Array mapV :: TypeV -> (State,State,Int) -> Double mapV = undefined valueit :: TypeV -> TypeV valueit oldV = listArray (minI,maxI) [ mapV oldV i | i <- range (minI,maxI) ] where minI = (Low,Low,0) maxI = (High,High,n) -- or move mapV to where clause; it can still use oldV valueit :: TypeV -> TypeV valueit oldV = listArray (minI,maxI) [ mapV i | i <- range (minI,maxI) ] where minI = (Low,Low,0) maxI = (High,High,n) mapV :: (State,State,Int) -> Double mapV = undefined
Thanks,
Tamas
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
Matthias Fischmann wrote:
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 | ...
Surely you meant to say | type TypeV = Array Point Double Cheers, Ben
Benjamin Franksen wrote:
Matthias Fischmann wrote:
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 | ...
Surely you meant to say
| type TypeV = Array Point Double
Cheers, Ben
And type Value = Double newtype PointNat = PointNat Int deriving (...Ix) type Point = (State,State,PointNat) Or even type TypeVof a = Array PointNat a type TypeV = TypeVof Value I did not even run the code I wrote through ghci, I was just showing what it could look like. And stop calling me Shirley.
Chris Kuklewicz wrote:
Benjamin Franksen wrote:
Matthias Fischmann wrote:
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 | ...
Surely you meant to say
| type TypeV = Array Point Double
Cheers, Ben
And
type Value = Double newtype PointNat = PointNat Int deriving (...Ix) type Point = (State,State,PointNat)
Or even
type TypeVof a = Array PointNat a type TypeV = TypeVof Value
I did not even run the code I wrote through ghci, I was just showing what it could look like.
And stop calling me Shirley.
Dear Chris, Could you please be a bit more explicit? Have I offended anyone? Or else, how do I have to understand this comment other than as a rebuke? And how comes you answer this as if you were the one who posted the code, and not a person named Matthias Fischmann? Please note that English is not my native tongue so there is always the possibility that I misunderstood something, or that I express myself badly and so cause misunderstandings. Is the expression "Surely you meant to say <whatever>" perceived as offending or arrogant, perhaps? In this case I would gladly apologize and assure everyone that this was not intended! I posted this correction only in order to avoid confusion for the OP, who described himself as a beginner with regard to Haskell. I didn't mean to be nitpicking or anything like that. If I have made a mistake, either technically or by chosing the wrong words, then please tell me so. Your answer to my other posting today is of a similar nature, i.e. completely obscure to me, and totally disregarding the essence of my question. If there is something personal involved here (for which I can't imagine any reason other than the above mentioned one) maybe it would be better to clearly say so (and sort this out in private and not on this list). Clueless, Ben
And stop calling me Shirley.
Could you please be a bit more explicit? Have I offended anyone?
This is a reference to a joke from the movie Airplane: "Surely, you can't be serious." "I am serious, and stop calling me Shirley." I imagine it meant nothing personal. Jared. -- http://www.updike.org/~jared/ reverse ")-:"
Benjamin Franksen wrote:
Chris Kuklewicz wrote:
Benjamin Franksen wrote:
Matthias Fischmann wrote:
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 | ... Surely you meant to say
| type TypeV = Array Point Double
True, I did make that mistake.
Cheers, Ben And
type Value = Double newtype PointNat = PointNat Int deriving (...Ix) type Point = (State,State,PointNat)
Or even
type TypeVof a = Array PointNat a type TypeV = TypeVof Value
I did not even run the code I wrote through ghci, I was just showing what it could look like.
And stop calling me Shirley.
Dear Chris,
Could you please be a bit more explicit? Have I offended anyone? Or else, how do I have to understand this comment other than as a rebuke? And how comes you answer this as if you were the one who posted the code, and not a person named Matthias Fischmann?
Sorry for the misunderstanding. No one has been offended or given offense. The Surely/Shirley is a reference to the classic 1980 motion picture "Airplane!" in which the humor includes a repeated motif [1]:
Rumack: Mr. Striker, the passengers are getting worse. You must land soon. Ted Striker: Surely there must be something you can do. Rumack: I'm doing everything I can... and stop calling me Shirley.
Ted Striker: Surely you can't be serious. Rumack: I am serious... and don't call me Shirley.
Please note that English is not my native tongue so there is always the possibility that I misunderstood something, or that I express myself badly and so cause misunderstandings. Is the expression "Surely you meant to say <whatever>" perceived as offending or arrogant, perhaps? In this case I would gladly apologize and assure everyone that this was not intended!
Nothing was offensive or arrogant.I just saw it as an opportunity to reference the joke.
I posted this correction only in order to avoid confusion for the OP, who described himself as a beginner with regard to Haskell. I didn't mean to be nitpicking or anything like that. If I have made a mistake, either technically or by chosing the wrong words, then please tell me so.
Your answer to my other posting today is of a similar nature, i.e. completely obscure to me, and totally disregarding the essence of my question. If there is something personal involved here (for which I can't imagine any reason other than the above mentioned one) maybe it would be better to clearly say so (and sort this out in private and not on this list).
I am sorry my other posting was off topic. Sometimes I contribute what occurs to me instead of what is relevant. Cheers, Chris [1] http://www.imdb.com/title/tt0080339/quotes
Chris Kuklewicz wrote:
Benjamin Franksen wrote:
Chris Kuklewicz wrote:
I did not even run the code I wrote through ghci, I was just showing what it could look like.
And stop calling me Shirley. [...] Could you please be a bit more explicit? Have I offended anyone? Or else, how do I have to understand this comment other than as a rebuke? And how comes you answer this as if you were the one who posted the code, and not a person named Matthias Fischmann?
Sorry for the misunderstanding. No one has been offended or given offense. The Surely/Shirley is a reference to the classic 1980 motion picture "Airplane!" in which the humor includes a repeated motif [1]:
Rumack: Mr. Striker, the passengers are getting worse. You must land soon. Ted Striker: Surely there must be something you can do. Rumack: I'm doing everything I can... and stop calling me Shirley.
Ted Striker: Surely you can't be serious. Rumack: I am serious... and don't call me Shirley.
Nothing was offensive or arrogant.I just saw it as an opportunity to reference the joke.
Ahh, I'm very glad to hear that. It seems the misunderstanding was completely on my part. Did a little research and found quite a number for websites citing dialogs from this movie. I begin to understand that it must have been cult...
I am sorry my other posting was off topic. Sometimes I contribute what occurs to me instead of what is relevant.
I can happily live with that ;-) (although I'd still be interested what prompted you to post this code which I admittedly did not fully understand). And sorry for dragging this (completely off-topic) stuff out here on the list. I'll shut up now. Cheers, Ben
Hello Benjamin, Wednesday, August 30, 2006, 11:40:09 PM, you wrote:
Matthias Fischmann wrote:
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 | ...
Surely you meant to say
| type TypeV = Array Point Double
which will require 128 gigs of memory for 32-bit cpus and even slightly more for 64-bit ones :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On Thursday 31 August 2006 09:09, Bulat Ziganshin wrote:
Hello Benjamin,
Wednesday, August 30, 2006, 11:40:09 PM, you wrote:
Matthias Fischmann wrote:
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 | ...
Surely you meant to say
| type TypeV = Array Point Double
which will require 128 gigs of memory for 32-bit cpus and even slightly more for 64-bit ones :)
Wow, that's bad. But then the situiation isn't really much better with a simple Array Int Double, values of which would always use up all my memory. Surely you don't mean that ;) Ben
On Thu, Aug 31, 2006 at 11:09:07AM +0400, Bulat Ziganshin wrote:
Hello Benjamin,
Wednesday, August 30, 2006, 11:40:09 PM, you wrote:
Matthias Fischmann wrote:
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 | ...
Surely you meant to say
| type TypeV = Array Point Double
which will require 128 gigs of memory for 32-bit cpus and even slightly more for 64-bit ones :)
Bulat, Can you please explain this? The following code works fine for me, and I don't have that much RAM ;-) It seems I am not getting something. import Data.Array data State = Low | High deriving (Eq,Ord,Ix,Show) other :: State -> State other High = Low other Low = High type Point = (State,State,Int) type TypeV = Array Point Double f (Low,Low,a) = a matrix = array ((Low,Low,0),(Low,Low,4)) [(i,f(i)) | i <- range ((Low,Low,0),(Low,Low,4))] Thank you, Tamas
Hello Tamas, Friday, September 1, 2006, 1:52:03 PM, you wrote:
| type Point = (State, State, Int) | type TypeV = Array Point Double
which will require 128 gigs of memory for 32-bit cpus and even slightly more for 64-bit ones :)
Bulat,
Can you please explain this? The following code works fine for me, and I don't have that much RAM ;-) It seems I am not getting something.
sorry, it was entirely my mindbug - i imagined that such type means that array should contain elements for every possible combination of State+State+Int :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (6)
-
Benjamin Franksen -
Bulat Ziganshin -
Chris Kuklewicz -
Jared Updike -
Matthias Fischmann -
Tamas K Papp