data structures question

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

data structures question

Tamas K Papp
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: data structures question

haskell-2
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: data structures question

Matthias Fischmann
In reply to this post by Tamas K Papp

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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: data structures question

Ben Franksen-2
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: data structures question

haskell-2
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.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: data structures question

Bulat Ziganshin-2
In reply to this post by Ben Franksen-2
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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: data structures question

Ben Franksen-2
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: data structures question

Ben Franksen-2
In reply to this post by haskell-2
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Re: data structures question

Jared Updike
> > 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 ")-:"
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Re: data structures question

haskell-2
In reply to this post by Ben Franksen-2
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Re: data structures question

Ben Franksen-2
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: data structures question

Tamas K Papp
In reply to this post by Bulat Ziganshin-2
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re[2]: Re: data structures question

Bulat Ziganshin-2
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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe