Functional - types sharing their values

Author

types sharing their values

danilla

2005-11-16, 7:58 am

Hello, folks.

I'd like to introduce a problem to you and ask for your opinion on how
it can be best solved.

The problem is that we have a number of objects which fall into number
of overlapping, orthogonal categories. Say, we have
Shape, Color, Owner
myball <- spherical red me
moon <- spherical yellow nobody
friendshouse cubic red my friend

Then, we need to uniformly work sometimes with all objects, sometimes
with all red objects, etc. Working uniformly means at least being able
to store them in one list.

Then, it should be the type system what prevents passing a cubic thing
to a function which works with spherical ones, say. In other words,
these kinds of error should be determined statically. That's the most
interesting constraint.

I've had a number of ideas.

1.
Pretty straightforward and working.
Having a data declaration for each combination of categories. That is,
we'd have
data SphericalRedMine = Myball | Etc...
data SphericalYelloNobodys = Moon | Etc...
and so on
Then we'd have the following definitions for sets
data RedThing = C1 SphericalRedMine | C2 CubicRedMine |
CubicRedMyFreinds | Etc..
data RedSphericalThing ....
....
It is in a sense straightforward but seems intolerably ugly. The number
of data decls gets pretty large. And in a function working with, say,
cubic things we will have to cope with all those data constructors and
will have to treat separately the cases for red cubic things, my cubic
things and so on.

2.
Type classes
Here we make our things types. They don't hold any values but are types
to exploit the mechanism of multiple inheritance provided by type
classes. The things could be given
newtype MyBall = MyBall ()
newtype Moon = Moon ()
.....
and then
instance Red MyBall where
instance Spherical MyBall where
....
This is just a sketch of an idea. In this primary version it dosn't
allow storing the things in a list. Well this would help:
make all thing types instance of a big Things class and
data Thing = forall a. (Things a) a
And the idea of making functions, that work with some subset of all
things, class-members
doesn't seem very attractive to me. And actually the whole idea of
making things types doesn't seem either :) The code would be far from
concise and clear, I believe. What do you think?

3.
Generalised data types
we describe these sets as types:
newtype Spherical = Spherical ()
newtype Cubic = Cubic ()
newtype Red = Red ()
.....
then we give the Thing type
data Thing shape color owner where
MyBall :: Thing Spherical Red Mine
Moon :: Thing Spherical Yellow Nobodys
....
It's good to have functions
radius :: Thing Spherical a b -> Int
askToDescribe :: Thing a b MyFreinds -> String
etc...
Still, we can't store things in a list. A forall decl would help again.
But having all those spherical,red,yellow as dummy types seems to be a
nuisance again. What do you think?

I'm not sure if I stated the problem very well. Your replies will show
whether I did or not.
Thank you

Joachim Durchholz

2005-11-16, 7:02 pm

danilla schrieb:
> I'm not sure if I stated the problem very well. Your replies will show
> whether I did or not.

The description seems clear enough to me.

I have another possibility: try storing closures. I.e. "canned function
calls" if you will.
E.g. in OO land, you store a set of "things" (say, TwoDObjects) in a
polymorphic list, so you can iterate over the list and call "Draw" on
each of them.
In FPL land, wrap each of the different kinds of objects in a Draw call
(but leave out the parameters that should be filled in later), then
store those "incomplete calls" (i.e. closures) in the list. Later,
iterate over the list and call the closures.

Hope this was clear (and correct) enough to help :-)

Regards,
Jo

Dirk Thierbach

2005-11-18, 3:57 am

danilla <danilla@pisem.net> wrote:

> Type classes
> Here we make our things types. They don't hold any values but are types
> to exploit the mechanism of multiple inheritance provided by type
> classes.

If you haven't come across this idea before, have a look at "Phantom
Types" on the Haskell Wiki.

> The things could be given
> newtype MyBall = MyBall ()
> newtype Moon = Moon ()
> ....
> and then
> instance Red MyBall where
> instance Spherical MyBall where
> ...
> This is just a sketch of an idea. In this primary version it dosn't
> allow storing the things in a list. Well this would help:
> make all thing types instance of a big Things class and
> data Thing = forall a. (Things a) a

If you want to store things in the same list, that means that you
want to access them in some uniform way. So in what way would you
like them to access? Once you've figured that out, make it a method
of the corresponding type class. Then you can have something
like

class Red where f :: ...
class Round where g :: ...

and then

processReds :: Red a => [a] -> ...
processReds l = map f l

processRounds :: Round a => [a] -> ...
processRounds l = map g l

or something similar.

> And the idea of making functions, that work with some subset of all
> things, class-members doesn't seem very attractive to me.

It would be easier to discuss this if you could make your example
more concrete.

> And actually the whole idea of making things types doesn't seem
> either :)

Well, you don't "make the things types", you introduce new phantom types
to allow some classification.

> The code would be far from concise and clear, I believe. What do you
> think?

As I said, you'd have to make your example more specific, but this
option is the one I would try first.

- Dirk

Dinko Tenev

2005-11-18, 3:57 am

Dirk Thierbach wrote:
> If you want to store things in the same list, that means that you
> want to access them in some uniform way. So in what way would you
> like them to access? Once you've figured that out, make it a method
> of the corresponding type class. Then you can have something
> like
>
> class Red where f :: ...
> class Round where g :: ...
>
> and then
>
> processReds :: Red a => [a] -> ...
> processReds l = map f l
>
> processRounds :: Round a => [a] -> ...
> processRounds l = map g l
>
> or something similar.

That still won't allow him to store apples and oranges in the same list
even though they're all Round. He'd need something like:

data RoundWrapper = Round a => Wrap a

processRounds :: [ RoundWrapper ] -> ...
processRounds l = map (\Wrap a -> g a) l

Cheers,
D. Tenev

Dirk Thierbach

2005-11-18, 7:56 am

Dinko Tenev <dinko.tenev@gmail.com> wrote:
> That still won't allow him to store apples and oranges in the same list
> even though they're all Round. He'd need something like:
>
> data RoundWrapper = Round a => Wrap a

Of course they have to be of the same type to be able to be stored in
the same list -- if that was the question, he needs the existential
types, or, as you say, a wrapper. He could also just define them as
an identical type. It all depends on what these things actually are, so
he has to make the example more concrete.

I was trying to address his question about crosscutting similarities
in serveral different ways.

- Dirk

Jon Harrop

2005-11-23, 7:00 pm

danilla wrote:
> I'd like to introduce a problem to you and ask for your opinion on how
> it can be best solved.
>
> The problem is that we have a number of objects which fall into number
> of overlapping, orthogonal categories. Say, we have
> Shape, Color, Owner
> myball <- spherical red me
> moon <- spherical yellow nobody
> friendshouse cubic red my friend
>
> Then, we need to uniformly work sometimes with all objects, sometimes
> with all red objects, etc. Working uniformly means at least being able
> to store them in one list.

Perhaps:

4. Polymorphic variants:

type shape = [ `Spherical | `Cubic ]
type color = [ `Red | `Yellow ]
type owner = [ `Me | `Nobody | `MyFriend ]
type t = shape * color * owner

let myball = (`Spherical, `Red, `Me)
let moon = (`Spherical, `Yellow, `Nobody)
let friendshouse = (`Cubic, `Red, `MyFriend)

With those definitions we can create a list of any type:

# let a : t list = [myball; moon; friendshouse];;
val a : t list =
[(`Spherical, `Red, `Me); (`Spherical, `Yellow, `Nobody);
(`Cubic, `Red, `MyFriend)]

or a list that is statically checked to contain only red things:

# let b : (shape * [ `Red ] * owner) list = [myball; friendshouse];;
val b : (shape * [ `Red ] * owner) list =
[(`Spherical, `Red, `Me); (`Cubic, `Red, `MyFriend)]

For example, the following fails (the OCaml top-level highlights "moon")
because the moon is not red:

# let b : (shape * [ `Red ] * owner) list =
[myball; moon; friendshouse];;
This expression has type shape * [> `Yellow ] * [> `Nobody ]
but is here used with type shape * [ `Red ] * owner

You can also dispatch by subset in pattern matches. For example, "#red"
matches any red object:

# let color = function
(_, #red, _) -> "red"
| _ -> "not red";;
val color : 'a * [> red ] * 'b -> string = <fun>

# List.map color [myball; moon; friendshouse];;
- : string list = ["red"; "not red"; "red"]

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

Dinko Tenev

2005-11-24, 3:58 am

I am not familiar with ML & Co, and thus I might be asking a stupid
question, but I just have to ask: where exactly did "#red" come from?

Jon Harrop wrote:
[...]
> You can also dispatch by subset in pattern matches. For example, "#red"
> matches any red object:
>
> # let color = function
> (_, #red, _) -> "red"
> | _ -> "not red";;
> val color : 'a * [> red ] * 'b -> string = <fun>
[...]

Jon Harrop

2005-11-24, 7:57 am

Dinko Tenev wrote:
> I am not familiar with ML & Co, and thus I might be asking a stupid
> question, but I just have to ask: where exactly did "#red" come from?

This (polymorphic variants) is OCaml specific. The "#red" means any
constructor from the polymorphic variant type called "red"... which I
forgot to define. Oops.

You can either define it:

# type red = [ `Red ];;
type red = [ `Red ]

# let color = function
(_, #red, _) -> "red"
| _ -> "not red";;
val color : 'a * [> red ] * 'b -> string = <fun>

or you can specify this constructor directly in the "color" function:

# let color = function
(_, `Red, _) -> "red"
| _ -> "not red";;
val color : 'a * [> `Red ] * 'b -> string = <fun>

Sorry about that.

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

christophe.poucet@gmail.com

2005-11-24, 7:57 am

Hello,

I think there seems to be a bit of confusion between the different
posts. As I read through the original post, I had a reaction similar
to Jon Harrop. In fact, for a closed set of attributes you don't need
to use polymorphic variants. But then as I read further, it seems that
the original poster does not want to have data stored in his objects
that represents whether an object is red or yellow. But actually have
different types (and why he wants this, I do not know). In this case,
the suggestiion offered by Jon Harrop does not work as it bases itself
on the same assumption I made at the beginning of the thread, that the
different facets of the objects would be stored as data, not type.

Cheers

Dinko Tenev

2005-11-24, 7:57 am

That's obviously the part I was missing, thanks.

Cheers
Dinko

Jon Harrop wrote:
> Dinko Tenev wrote:
>
> This (polymorphic variants) is OCaml specific. The "#red" means any
> constructor from the polymorphic variant type called "red"... which I
> forgot to define. Oops.
>
> You can either define it:
>
> # type red = [ `Red ];;
> type red = [ `Red ]
>
> # let color = function
> (_, #red, _) -> "red"
> | _ -> "not red";;
> val color : 'a * [> red ] * 'b -> string = <fun>
>
> or you can specify this constructor directly in the "color" function:
>
> # let color = function
> (_, `Red, _) -> "red"
> | _ -> "not red";;
> val color : 'a * [> `Red ] * 'b -> string = <fun>
>
> Sorry about that.
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> http://www.ffconsultancy.com

Dinko Tenev

2005-11-24, 7:57 am

christophe.poucet@gmail.com wrote:
> Hello,
>
> I think there seems to be a bit of confusion between the different
> posts. As I read through the original post, I had a reaction similar
> to Jon Harrop. In fact, for a closed set of attributes you don't need
> to use polymorphic variants. But then as I read further, it seems that
> the original poster does not want to have data stored in his objects
> that represents whether an object is red or yellow. But actually have
> different types (and why he wants this, I do not know). In this case,
> the suggestiion offered by Jon Harrop does not work as it bases itself
> on the same assumption I made at the beginning of the thread, that the
> different facets of the objects would be stored as data, not type.
>
> Cheers

I see only these two requirements in the original post:

1) "...we need to uniformly work sometimes with all objects, sometimes
with all red objects, etc. Working uniformly means at least being able
to store them in one list."

2) "...it should be the type system what prevents passing a cubic thing
to a function which works with spherical ones, say. In other words,
these kinds of error should be determined statically."

As far as storing different things in the same list, and statically
checking list elements' types against pre-defined bounds, the snippet
seems to be just fine.

Cheers,
Dinko

christophe.poucet@gmail.com

2005-11-25, 7:57 am

Hello Dinko,

Thanks for the clarification, it seems that my understanding of
polymorphic variants was slightly lacking and I had overseen the
example provided with the type error.

Cheers,
Christophe

danilla

2005-11-30, 3:59 am

Thank you very much, everybody

What Dr Jon Harrop proposed seems to be most attractive,
but the reason why I didn't even mention it in my original
post is because I had no idea it could be handled statically.

I'm unfamiliar with OCaml and I wonder if something similar
can be done in Haskell (which is yet another requirement,
I forgot to mention it)

--- output fragment
# let b : (shape * [ `Red ] * owner) list = [myball; friendshouse];;
val b : (shape * [ `Red ] * owner) list =
[(`Spherical, `Red, `Me); (`Cubic, `Red, `MyFriend)]

For example, the following fails (the OCaml top-level highlights
"moon")
because the moon is not red:

# let b : (shape * [ `Red ] * owner) list =
[myball; moon; friendshouse];;
This expression has type shape * [> `Yellow ] * [> `Nobody ]
but is here used with type shape * [ `Red ] * owner
-- end of output

So, I have 2 questions:

1. The fragment above looks to me like an interpreter's output.
If it is so, will this error be reported at compile time in the case
of compiled code?

2. Is there something similar in Haskell?

Seems like in Haskell I can say
a :: [ (Shape,Color,Owner) ]
but I can't say
a :: [ (Shape, Red, Owner) ] since Red is not a type

Jon Harrop

2005-12-02, 9:14 pm

danilla wrote:
> 1. The fragment above looks to me like an interpreter's output.
> If it is so, will this error be reported at compile time in the case
> of compiled code?

I quoted output from OCaml's top-level interpreter, yes. The errors are type
errors so they will be caught at compile time by the static type checker if
you choose to use either of the compilers, yes.

> 2. Is there something similar in Haskell?
>
> Seems like in Haskell I can say
> a :: [ (Shape,Color,Owner) ]
> but I can't say
> a :: [ (Shape, Red, Owner) ] since Red is not a type

Yipes. Err, anyone? :-)

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

Sponsored Links