represent data sturcture using function

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

represent data sturcture using function

raeck@msn.com

Merry Christmas!
Hope everybody is enjoying the Christmas!

I am doing some readings and I found something seems to be interesting.

People sometime will try to represent a quantity-regard-only data structure
(such a order-regadless List) using functions instead of ta concrete data
structure (like the haskell build-in []), any particular reason for this?

For example,
> data Sex = Male | Female
> classA :: Sex -> Int
> classA Male = 100
> classA Female = 200

when I should prefer the above solution instead of using a concrete data structure
such as [] to represent the classA members?

It seems to be very difficult to change the number of Male or Female if a concrete data
structure is not used. Is it possible change the number of Male in classA when represent
classA using function?

Thank you very much!

Best wishes,
Raeck


_________________________________________________________________
It?s the same Hotmail?. If by ?same? you mean up to 70% faster.
http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_122008
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20081229/78f7e2f7/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] represent data sturcture using function

David Menendez-2
2008/12/29 Raeck chiu <[hidden email]>:

> People sometime will try to represent a quantity-regard-only data structure
> (such a order-regadless List) using functions instead of ta concrete data
> structure (like the haskell build-in []), any particular reason for this?
>
> For example,
>> data Sex = Male | Female
>> classA :: Sex -> Int
>> classA Male = 100
>> classA Female = 200
>
> when I should prefer the above solution instead of using a concrete data
> structure such as [] to represent the classA members?

One important difference between Sex -> Int and [(Sex,Int)] is that
the first guarantees exactly one Int per Sex and has no underlying
order. (That is, [(Male,100),(Female,200)] and
[(Female,200),(Male,100)] are distinct lists but represent the same
map.)

> It seems to be very difficult to change the number of Male or Female if a
> concrete data structure is not used. Is it possible change the number of Male in classA
> when represent classA using function?

Here's the simplest way:

    update k v map = \k' -> if k' == k then v else map k'

Note that it requires an Eq instance for Sex.

    let classA' = update Male 150 classA
    in (classA' Male, classA' Female)
=
    (150,200)

--
Dave Menendez <[hidden email]>
<http://www.eyrie.org/~zednenem/>
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] represent data sturcture using function

Ryan Ingram
On Sun, Dec 28, 2008 at 10:13 PM, David Menendez <[hidden email]> wrote:

> 2008/12/29 Raeck chiu <[hidden email]>:
>> It seems to be very difficult to change the number of Male or Female if a
>> concrete data structure is not used. Is it possible change the number of Male in classA
>> when represent classA using function?
>
> Here's the simplest way:
>
>    update k v map = \k' -> if k' == k then v else map k'
>
> Note that it requires an Eq instance for Sex.
>
>    let classA' = update Male 150 classA
>    in (classA' Male, classA' Female)
> =
>    (150,200)

Of course this version of update leaks crazy amounts of memory:

> let bigmap = iterate (update Male 150) classA !! 100000
> bigmap Male

"bigmap" leaves a huge chain of thunks pointing at each other, which
can never be freed.

Using functions is mathematically more elegant than some concrete data
structure (which might require Eq or Ord or other constraints, and
have multiple observable representations for the same map, or have
maps that don't include every element).

However, "generic maps" have been improving a lot recently, especially
with data families in the new GHC.   You use an abstract type (k :->
v) to represent the map; this type is semantically equivalent to (k ->
v) via some observation function for generic maps, but has a compact
representation.  For example:

> class MapKey k where
>    data k :-> v
>    newMap :: (k -> v) -> (k :-> v)
>    fetch :: (k :-> v) -> (k -> v)
>    update :: (k,v) -> (k :-> v) -> (k :-> v)
>    empty :: v -> (k :-> v)
>    empty = newMap (const v)

> instance MapKey Bool where
>    data Bool :-> v = BoolMap v v
>    newMap f = BoolMap (f False) (f True)
>    fetch (Boolmap t f) v = if v then t else f
>    update (True, t) (BoolMap _ f) = Boolmap t f
>    update (False, f) (BoolMap t _) = Boolmap t f

"fetch" converts this representation of a total function over k, into
an actual function.  The representation of k :-> v might vary
depending on k; Int might use IntMap, (k1,k2) can compose maps:

> instance (MapKey k1, MapKey k2) => MapKey (k1,k2) where
>    newtype (k1,k2) :-> v = PairMap (k1 :-> (k2 :-> v))
>    ...

> instance (MapKey k1, MapKey k2) => MapKey (Either k1 k2) where
>    data (Either k1 k2) :-> v = EitherMap (k1 :-> v) (k2 :-> v)
>    ...

This gives you the same benefits as the function approach but without
the terrible performance issues.  You do need to write instances for
your types, though, although most can be easily derived from the
instances for pairs, Either, and Integer.

See http://www.haskell.org/haskellwiki/GHC/Indexed_types for more.

  -- ryan
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] represent data sturcture using function

Ryan Ingram
Bonus points if you find the stupid bug in my code :)

  -- ryan

On Mon, Dec 29, 2008 at 1:48 AM, Ryan Ingram <[hidden email]> wrote:

> On Sun, Dec 28, 2008 at 10:13 PM, David Menendez <[hidden email]> wrote:
>> 2008/12/29 Raeck chiu <[hidden email]>:
>>> It seems to be very difficult to change the number of Male or Female if a
>>> concrete data structure is not used. Is it possible change the number of Male in classA
>>> when represent classA using function?
>>
>> Here's the simplest way:
>>
>>    update k v map = \k' -> if k' == k then v else map k'
>>
>> Note that it requires an Eq instance for Sex.
>>
>>    let classA' = update Male 150 classA
>>    in (classA' Male, classA' Female)
>> =
>>    (150,200)
>
> Of course this version of update leaks crazy amounts of memory:
>
>> let bigmap = iterate (update Male 150) classA !! 100000
>> bigmap Male
>
> "bigmap" leaves a huge chain of thunks pointing at each other, which
> can never be freed.
>
> Using functions is mathematically more elegant than some concrete data
> structure (which might require Eq or Ord or other constraints, and
> have multiple observable representations for the same map, or have
> maps that don't include every element).
>
> However, "generic maps" have been improving a lot recently, especially
> with data families in the new GHC.   You use an abstract type (k :->
> v) to represent the map; this type is semantically equivalent to (k ->
> v) via some observation function for generic maps, but has a compact
> representation.  For example:
>
>> class MapKey k where
>>    data k :-> v
>>    newMap :: (k -> v) -> (k :-> v)
>>    fetch :: (k :-> v) -> (k -> v)
>>    update :: (k,v) -> (k :-> v) -> (k :-> v)
>>    empty :: v -> (k :-> v)
>>    empty = newMap (const v)
>
>> instance MapKey Bool where
>>    data Bool :-> v = BoolMap v v
>>    newMap f = BoolMap (f False) (f True)
>>    fetch (Boolmap t f) v = if v then t else f
>>    update (True, t) (BoolMap _ f) = Boolmap t f
>>    update (False, f) (BoolMap t _) = Boolmap t f
>
> "fetch" converts this representation of a total function over k, into
> an actual function.  The representation of k :-> v might vary
> depending on k; Int might use IntMap, (k1,k2) can compose maps:
>
>> instance (MapKey k1, MapKey k2) => MapKey (k1,k2) where
>>    newtype (k1,k2) :-> v = PairMap (k1 :-> (k2 :-> v))
>>    ...
>
>> instance (MapKey k1, MapKey k2) => MapKey (Either k1 k2) where
>>    data (Either k1 k2) :-> v = EitherMap (k1 :-> v) (k2 :-> v)
>>    ...
>
> This gives you the same benefits as the function approach but without
> the terrible performance issues.  You do need to write instances for
> your types, though, although most can be easily derived from the
> instances for pairs, Either, and Integer.
>
> See http://www.haskell.org/haskellwiki/GHC/Indexed_types for more.
>
>  -- ryan
>
Reply | Threaded
Open this post in threaded view
|

'Iterating a data type'

raeck@msn.com
Are there anyway to express the "iterating" of a user-defined data type in
Haskell?

For example, in

> data Shape = Square | Circle | Triangle

how can I 'iterate' them and apply them all to the same function without
indicating them explicitly?
such as [func Square, func Circle, func Triangle].
Can I use a form similar to the following case in a list instead:

> Numbers = [1,2,3,4,5]

> [func x | x <- Numbers ]

Actually what I want is to obtain all the possible values of a data type
(Shape).

Thank you very much!

Best wishes,

Raeck

Reply | Threaded
Open this post in threaded view
|

'Iterating a data type'

Paul Visschers-2
You actually have two different questions. The first about iteration can
be done by the function map in the following way:

Instead of [func Square, func Circle, func Triangle] you use:
map func [Square, Circle, Triangle].

The list comprehensions should also work:
[func x | x <- [Square, Circle, Triangle]]

Now as for obtaining/generating all values of Shape, the easiest way is
to make Shape an instance of Enum, like this:
data Shape = Square | Circle | Triangle deriving Enum

You can then generate a list of all the values by:
enumFrom Square

You use Square here because it is the first constructor of Shape, and
you want to enumerate them all.

I hope this helps,

Paul

[hidden email] wrote:

> Are there anyway to express the "iterating" of a user-defined data type
> in Haskell?
>
> For example, in
>
>> data Shape = Square | Circle | Triangle
>
> how can I 'iterate' them and apply them all to the same function without
> indicating them explicitly?
> such as [func Square, func Circle, func Triangle].
> Can I use a form similar to the following case in a list instead:
>
>> Numbers = [1,2,3,4,5]
>
>> [func x | x <- Numbers ]
>
> Actually what I want is to obtain all the possible values of a data type
> (Shape).
>
> Thank you very much!
>
> Best wishes,
>
> Raeck
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] represent data sturcture using function

Ryan Ingram
In reply to this post by Ryan Ingram
On Mon, Dec 29, 2008 at 4:29 AM,  <[hidden email]> wrote:
> Would you please give me a complete example of code that I could have more
> information
> on the idea?

Sure, I put up an example at http://ryani.freeshell.org/haskell/gmap.hs

class MapKey k where
    data (:->) k :: * -> *
    newMap :: (k -> v) -> (k :-> v)
    fetch  :: (k :-> v) -> (k -> v)
    update :: k -> (v -> v) -> (k :-> v) -> (k :-> v)
    assign :: k -> v -> (k :-> v) -> (k :-> v)
    assign k v m = update k (const v) m
    empty  :: v -> (k :-> v)
    empty = newMap . const

with instances & associated data types:

instance MapKey () where
    -- A single value
    newtype () :-> v = UMap v

instance MapKey Bool where
    -- A value for False and True
    data Bool :-> v = BMap v v

instance (MapKey k1, MapKey k2) => MapKey (k1,k2) where
    -- A "curried" map
    newtype (k1,k2) :-> v = PMap (k1 :-> k2 :-> v)

instance (MapKey k1, MapKey k2) => MapKey (Either k1 k2) where
    -- sub-maps for Left k1 and Right k2
    data (Either k1 k2 :-> v) = EMap (k1 :-> v) (k2 :-> v)

instance MapKey k => MapKey (Maybe k) where
    -- Now we can build up from existing structures!
    newtype (Maybe k) :-> v = MaybeM (Either () k :-> v)

instance MapKey k => MapKey [k] where
    -- Value for [] and map for (head:tail)
    --
    -- Note that this includes a recursive ([k] :-> v) map
    -- in the pair map (k,[k]) :-> v
    data [k] :-> v = ListM v ((k,[k]) :-> v)

instance MapKey Positive where
    -- We just convert a positive number into
    -- a list of Bools, then make a map of those
    newtype Positive :-> v = PosMap ([Bool] :-> v)

instance MapKey Integer where
    -- Now an integer is either negative, zero, or positive.
    -- So we store a map for negative numbers, a zero value,
    -- and a map for positive numbers.
    data Integer :-> v = IntMap (Positive :-> v) v (Positive :-> v)

The rest of the class functions are reasonably easy to derive from
their type and these data types.

  -- ryan
Reply | Threaded
Open this post in threaded view
|

Enum and Bounded in generic type

raeck@msn.com
Hi, how can I make the following code work? (show all the possible values of
a type 'a')

> showAll :: (Eq a, Bounded a, Enum a) => a -> [a]
> showAll a = [minBound..maxBound]::[a]

it keeps saying that I could fix the problem by adding (Enum a) and (Bounded
a) the the context, but I failed when I try.

anything goes wrong?

Thanks!

Raeck

Reply | Threaded
Open this post in threaded view
|

Enum and Bounded in generic type

Philippa Cowderoy
[-cafe left out]

On Tue, 2008-12-30 at 17:12 +0000, [hidden email] wrote:
> Hi, how can I make the following code work? (show all the possible values of
> a type 'a')
>
> > showAll :: (Eq a, Bounded a, Enum a) => a -> [a]
> > showAll a = [minBound..maxBound]::[a]
>
> it keeps saying that I could fix the problem by adding (Enum a) and (Bounded
> a) the the context, but I failed when I try.
>

The problem is the inner annotation, ::[a]. It's not the same a as in
(Eq a, Bounded a, Enum a) => a -> [a], and in Haskell98 it can't be. I'm
not surprised that's confused you! If you remove the inner annotation it
should work fine though.

You can go a step further and make showAll a value rather than a
function:

showAll = [minBound..maxBound]

(I've left out the type annotations, but you can put ":t
[minBound..maxBound]" into ghci or hugs if you want one)

--
Philippa Cowderoy <[hidden email]>
I left the snappy .sigs on the other computer

Reply | Threaded
Open this post in threaded view
|

Enum and Bounded in generic type

Paul Visschers-2
You seem to be having some trouble with the type system, not just in
this instance. I found when I was learning Haskell that when this
happens, it is useful to not add type annotations, then load it up in
GHCi and see what it comes up with (with the aforementions :t option).
Then you can see why that makes sense and possibly change the function.
Once you're happy with the function and are confident you understand its
type, go ahead and put the type annotation back into your source code.

I also found it useful to play around with various expressions and see
what their types where. Especially with things like partial application,
function composition and monadic functions.

Paul

Philippa Cowderoy wrote:

> [-cafe left out]
>
> On Tue, 2008-12-30 at 17:12 +0000, [hidden email] wrote:
>> Hi, how can I make the following code work? (show all the possible values of
>> a type 'a')
>>
>>> showAll :: (Eq a, Bounded a, Enum a) => a -> [a]
>>> showAll a = [minBound..maxBound]::[a]
>> it keeps saying that I could fix the problem by adding (Enum a) and (Bounded
>> a) the the context, but I failed when I try.
>>
>
> The problem is the inner annotation, ::[a]. It's not the same a as in
> (Eq a, Bounded a, Enum a) => a -> [a], and in Haskell98 it can't be. I'm
> not surprised that's confused you! If you remove the inner annotation it
> should work fine though.
>
> You can go a step further and make showAll a value rather than a
> function:
>
> showAll = [minBound..maxBound]
>
> (I've left out the type annotations, but you can put ":t
> [minBound..maxBound]" into ghci or hugs if you want one)
>
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Enum and Bounded in generic type

Robert Greayer
In reply to this post by raeck@msn.com
Raeck said:

> Hi, how can I make the following code work? (show all the possible values of a type 'a')

>> showAll :: (Eq a, Bounded a, Enum a) => a -> [a]
>> showAll a = [minBound..maxBound]::[a]

What you are really looking for, I think, is a polymorphic value of type [a], where a is some enumerable, bounded type.

allValues :: (Enum a, Bounded a) => [a]
allValues = [minBound .. maxBound]

You can omit the type signature, but then you'll run into the monomorphism restriction (which you'll can turn off with, e.g. -XNoMonomorphismRestriction)


     
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] 'Iterating a data type'

Luke Palmer-2
In reply to this post by raeck@msn.com
On Mon, Dec 29, 2008 at 6:24 PM, <[hidden email]> wrote:

> Are there anyway to express the "iterating" of a user-defined data type in
> Haskell?
>
> For example, in
>
>  data Shape = Square | Circle | Triangle
>>
>
> how can I 'iterate' them and apply them all to the same function without
> indicating them explicitly?
> such as [func Square, func Circle, func Triangle].
> Can I use a form similar to the following case in a list instead:
>
>  Numbers = [1,2,3,4,5]
>>
>
>  [func x | x <- Numbers ]
>>
>
> Actually what I want is to obtain all the possible values of a data type
> (Shape).


For "enum" style data, where all the constructors have no arguments, you can
do deriving (Bounded, Enum), so:

data Shape = Square | Circle | Triangle
  deriving (Bounded,Enum)

Then:

numbers = [minBound..maxBound] :: [Shape]

Luke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20081229/a5358a1f/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] Enum and Bounded in generic type

Derek Elkins
In reply to this post by raeck@msn.com
On Tue, 2008-12-30 at 17:12 +0000, [hidden email] wrote:
> Hi, how can I make the following code work? (show all the possible values of
> a type 'a')
>
?
> > showAll :: (Eq a, Bounded a, Enum a) => a -> [a]
> > showAll a = [minBound..maxBound]::[a]

The bottom 'a' has nothing to do with the 'a' in the type signature.
Your code is equivalent to
?
> > showAll :: (Eq a, Bounded a, Enum a) => a -> [a]
> > showAll a = [minBound..maxBound]::[b]

Which is not type correct as [minBound..maxBound] :: (Bounded a, Enum a) => [a]
You don't need that type annotation (or the type signature for that matter), so just omit it.

Reply | Threaded
Open this post in threaded view
|

Re: [Haskell-cafe] represent data sturcture using function

David Menendez-2
In reply to this post by Ryan Ingram
On Mon, Dec 29, 2008 at 4:48 AM, Ryan Ingram <[hidden email]> wrote:
> On Sun, Dec 28, 2008 at 10:13 PM, David Menendez <[hidden email]> wrote:
>> Here's the simplest way:
>>
>>    update k v map = \k' -> if k' == k then v else map k'

> Of course this version of update leaks crazy amounts of memory:
>
>> let bigmap = iterate (update Male 150) classA !! 100000
>> bigmap Male
>
> "bigmap" leaves a huge chain of thunks pointing at each other, which
> can never be freed.

Sure. It's slow, too. If you want a map that you can update, you're
usually much better off with a concrete data structure.

--
Dave Menendez <[hidden email]>
<http://www.eyrie.org/~zednenem/>