[Caml-list] Design advice

[Caml-list] Design advice

[Dan Schmidt]

I've been using ocaml for only a couple of months now, and it's not
yet clear to me how to do some things most idiomatically in it.

One has to do with making the equivalent of an enum in C.  Say I'm
implementing a deck of cards for a card game.  There are four suits,
and none of them have any special properties (this isn't a game like
bridge where different suits are treated differently).  I could do

  type suit = Spades | Hearts | Diamonds | Clubs

but this seems a little heavyweight; it seems weird to perform pattern
matching on values that really have no semantic importance other than
the fact that they are different from each other.  It's not like I'm
going to have any code that does one thing when given the 3 of Spades
and another thing when given the 3 of Hearts.  The other issue is that
it is mildly annoying to, for example, write a compare function to be
used inside a struct that implements the OrderedType signature (e.g.,
if I want to have a Set of cards).

The alternative is to just use an int, but then it is theoretically
possible that I could pass in ints outside the valid range and get
run-time errors.  The idea of guaranteeing that a suit is never
invalid appeals to me.

The same sort of issue comes up with representing the two players of
the game.  I could use an int and just raise exceptions everywhere if
it turns out to be not 0 or 1.  Or I could make a

  type player = Player_one | Player_two

type, but now I have to convert this to an integer whenever I want to
use the player number as an index.  Which sort of approach usually
ends up being less of a hassle in the end?  Or does it depend on the
particular application?  Or is there yet a third solution which is
better than either of these?  I've been vacillating, and right now I
am inclined to go with the variants at the expense of having to
indirect every once in a while.

Finally, is there any type in the library that functions like an
immutable array?  I would like to have an indexable bunch of values
but use it in a purely functional way.  I could always just use
Arrays and copy them before updating, but if there's already an
idiomatic type to use I'd prefer to use that.

Thanks,
Dan

-- 
http://www.dfan.org
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[John Prevost]

>>>>> "ds" == Dan Schmidt <dfan@dfan.org> writes:

    ds> {...} it seems weird to perform
    ds> pattern matching on values that really have no semantic
    ds> importance other than the fact that they are different from
    ds> each other.  It's not like I'm going to have any code that
    ds> does one thing when given the 3 of Spades and another thing
    ds> when given the 3 of Hearts.  The other issue is that it is
    ds> mildly annoying to, for example, write a compare function to
    ds> be used inside a struct that implements the OrderedType
    ds> signature (e.g., if I want to have a Set of cards).

Well, note that in the type you've defined, the only thing in the type
is the different suits.  That is the *only* information there.  I
don't see why it seems unreasonable to pattern match here.

Note that the built-in comparison operations work just fine on types
defined this way.

    ds> {... similar angst about Player_One and Player_Two ...}

In this case, it only makes sense in games with precisely two players.
For example: Go, or Chess.  If you think you might be using an array
that you want to index into, you may very well be thinking of a game
with unbounded numbers of players--or a library for unbounded numbers
of players.  (For example, Bridge has only four players, but a more
general library for hands of cards might support an arbitrary number.)

In the case of a set number of players, you might use a tuple instead
of an array, since you know the precise size, and you know which
player goes with which item.  As an example:

type player = North | South | East | West
type state = { n_hand : hand, s_hand : hand, e_hand : hand, w_hand : hand }

let get_hand p st = match p with
  | North -> st.n_hand
  | South -> st.s_hand
  | East -> st.e_hand
  | West -> st.w_hand

Is this a little heavy?  Well, possibly.  But it's not unreasonable,
and it does at the very least restrict possible "unsafe" operations to
certain sections of code.  You might, for example, do this instead of
the above:

type player = (* same *)
type state = hand array

let player_to_index = function
  | North -> 0
  | South -> 1
  | East -> 2
  | West -> 3

let get_hand p st = st.(player_to_index p)

And don't export player_to_index or the structure of the state type.
Now the "unsafe" region of your code is just in the library that
contains the above.  Anything that uses it manipulates things purely
in terms of the bounded type, and you only have to verify that
indexing works right in the above library.

When in doubt, export the safest interface possible and then ensure
that your module's internals are correct.  That way you have at least
ensured that users of your module cannot feed you bad arguments.

    ds> Finally, is there any type in the library that functions like
    ds> an immutable array?  I would like to have an indexable bunch
    ds> of values but use it in a purely functional way.  I could
    ds> always just use Arrays and copy them before updating, but if
    ds> there's already an idiomatic type to use I'd prefer to use
    ds> that.

There is none in the base O'Caml.  But this might be more efficient
than copying all the time:

http://www.ai.univie.ac.at/~markus/home/ocaml_sources.html

Take a look in 4.1.6 (Okasaki's Purely Functional Datastructures in
OCaml), chp9.ml, and look at the random access lists.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Chris Hecker]

I usually use variants, but it's not like I've been programming caml for 
much longer than you have.

>type, but now I have to convert this to an integer whenever I want to
>use the player number as an index.

Note that there is a correspondence between variant constructors with no 
arguments and integers 
(http://caml.inria.fr/ocaml/htmlman/manual032.html#htoc212), so:

type suit = Spades | Hearts | Diamonds | Clubs

let suit_to_int (s : suit) =
         assert (Obj.is_int (Obj.repr s));
         ((Obj.magic s) : int)

The assert will catch it if you add variables to one of the constructors 
and then call this.  This uses magic, which is bad, but it alleviates you 
having to type the variant constructors again and possibly make an error in 
the assocation with the int, which is good.  Pick your poison.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[William Lovas]

On Sat, Sep 28, 2002 at 03:55:43AM -0700, Chris Hecker wrote:
> >type, but now I have to convert this to an integer whenever I want to
> >use the player number as an index.
> 
> type suit = Spades | Hearts | Diamonds | Clubs
> 
> let suit_to_int (s : suit) =
>         assert (Obj.is_int (Obj.repr s));
>         ((Obj.magic s) : int)
> 
> The assert will catch it if you add variables to one of the constructors 
> and then call this.  This uses magic, which is bad, but it alleviates you 
> having to type the variant constructors again and possibly make an error in 
> the assocation with the int, which is good.  Pick your poison.

Wouldn't it be safer to just do something like:

    let suit_to_int = function
      | Spades   -> 0
      | Hearts   -> 1
      | Diamonds -> 2
      | Clubs    -> 3

?  You only have to type it once, and if you change the constructors
around, it won't even compile.  Plus it gives you control over which
int a suit corresponds to -- i doubt you can get any sort of guarantee
if you use Obj.magic.

William
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[John Gerard Malecki]

This thread reminds me to ask if are there any guarantees for ordering
of variant types?  Although the implementation indicates that with

  type card = Number of int | Jack | Queen | King | Ace

Jack < Queen and Queen < King it also says that Ace < Number 0.  I can
see what is going on with the implementation.  I'm curious if there
are any ordering guarantees that I can take advantage of?  Since the
documentation is silent on this point I doubt it.

Oh, It does seems as if tuples, arrays and lists are always compared
"from left to right".  This can be handy when sorting multi-
dimensional data.  This seems like a "more natural" ordering than for
variants but, once again, can this ordering be guaranteed for all
ocaml programs?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Chris Hecker]

>    let suit_to_int = function
>       | Spades   -> 0
>       | Hearts   -> 1
>       | Diamonds -> 2
>       | Clubs    -> 3
>?  You only have to type it once, and if you change the constructors
>around, it won't even compile.

As I mentioned in my mail,

    let suit_to_int = function
       | Spades   -> 0
       | Hearts   -> 1
       | Diamonds -> 1
       | Clubs    -> 3

is a bug that the compiler can't find.  That's why I said it was a 
tradeoff.  Also, having to type the constructors twice in the mli and the 
ml is already a huge pain the ass for maintenance and refactoring in my 
opinion, and having to do it a third time is completely lame.  But yes, 
magic is magic, so that's why I didn't say it was absolutely the right 
thing.  In reality, a ton of C code depends on this and it is documented to 
work like this in the manual, so it's probably safe, but I don't like 
fencing in the compiler folks any more than necessary.  Hence, "choose your 
poison".

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Chris Hecker]

>   type card = Number of int | Jack | Queen | King | Ace

On a related note, for Xavier et al., why wasn't Number's field 0 assigned 
to the same counter as the int of the non-argument constructors?  In other 
words, why isn't there a single incrementing int id from left to right, 
regardless of arguments?  That would have made algorithmic manipulations on 
variants easier, because then you just have:

let card_to_int (c : card) : int =
         let r = Obj.repr c in
         if Obj.is_int r then Obj.magic c else Obj.obj (Obj.field r 0);;

I don't think it's possible to write card_to_int the way the compiler 
currently works.  If there was a card_cardinality (!) function then you 
could do that + field 0 and the argument constructors would start at the 
end (still not as nice as if they were in the source code order, but better 
than nothing).  Maybe you can write that with camlp4 (of course, with 
camlp4 you can probably just write the longhand match-with form, but if 
you're doing this a lot I'd assume match-with would be slower than just 
fetching the field).

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Lauri Alanko]

This doesn't help you much, but you may be interested to know that in
Haskell this wouldn't be much of a problem. You would do simply:

data Suit = Spades | Hearts | Diamonds | Clubs
	deriving (Eq, Ord, Enum, Ix)

Here "Eq" and "Ord" mean that the compiler generates equality comparison
and ordering functions for the datatype. This is basically what ocaml's
(=) and compare -functions do.

"Enum" means that the compiler generates a bidirectional mapping between
your data type and a subset of natural numbers. This is useful if you
eg. need to communicate Suit values via an external interface (files,
sockets, whatnot).

Finally, "Ix" means that the compiler generates some functionality that
is required for a data type to be usable as an array index. And this is
probably the feature that you seem to need. In Haskell, you could have
an array whose _index_ type is Suit. With such an array, there's no fear
of overflowing, because there simply _aren't_ any index values of the
proper type that weren't included in the domain of the array.

Of course you can get the same safety in ocaml, too, but it just
requires some more work on your part.

This isn't an unconditional plug for Haskell, mind you. Both Haskell and
ocaml are fine languages, and each has great features that the other
lacks.


Lauri Alanko
la@iki.fi
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Kontra, Gergely]

>  type card = Number of int | Jack | Queen | King | Ace

Another interesting question is how to fence the Number of int
construct?

Gergo

+-[Kontra, Gergely @ Budapest University of Technology and Economics]-+
|         Email: kgergely@mcl.hu,  kgergely@turul.eet.bme.hu          |
|  URL:   turul.eet.bme.hu/~kgergely    Mobile: (+36 20) 356 9656     |
+-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Alessandro Baretta]

Lauri Alanko wrote:
> This doesn't help you much, but you may be interested to know that in
> Haskell this wouldn't be much of a problem. You would do simply:
> 
> data Suit = Spades | Hearts | Diamonds | Clubs
> 	deriving (Eq, Ord, Enum, Ix)
> 
> ...
> Finally, "Ix" means that the compiler generates some functionality that
> is required for a data type to be usable as an array index. And this is
> probably the feature that you seem to need. In Haskell, you could have
> an array whose _index_ type is Suit. With such an array, there's no fear
> of overflowing, because there simply _aren't_ any index values of the
> proper type that weren't included in the domain of the array.
> 
> Of course you can get the same safety in ocaml, too, but it just
> requires some more work on your part.
> 
> This isn't an unconditional plug for Haskell, mind you. Both Haskell and
> ocaml are fine languages, and each has great features that the other
> lacks.
> 
> 
> Lauri Alanko
> la@iki.fi

type tagged_type = Tag1 of foo | Tag2 of bar | ...

class ['a] tagged_array size =
object
   val map = Hashtbl.create size
   method set index value = Hashtbl.remove map index;
     Hashtbl.add map index value
   method get index = Hashtbl.find map index
   (* any other methods you might need *)
end

It's not really an array, but it's almost as fast and works 
very much like one. I think this approach might solve most 
of Dan's problems.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Design advice

[Xavier Leroy]

Dan Schmidt wrote:

> One has to do with making the equivalent of an enum in C.  Say I'm
> implementing a deck of cards for a card game.  There are four suits,
> and none of them have any special properties (this isn't a game like
> bridge where different suits are treated differently).  I could do
>   type suit = Spades | Hearts | Diamonds | Clubs
> but this seems a little heavyweight; it seems weird to perform pattern
> matching on values that really have no semantic importance other than
> the fact that they are different from each other.  It's not like I'm
> going to have any code that does one thing when given the 3 of Spades
> and another thing when given the 3 of Hearts.  The other issue is that
> it is mildly annoying to, for example, write a compare function to be
> used inside a struct that implements the OrderedType signature (e.g.,
> if I want to have a Set of cards).

As others mentioned, the generic comparison functions (=, <, compare,
etc) work just fine on datatypes, and provide you with a suitable
ordering function for sets or maps.

> Finally, is there any type in the library that functions like an
> immutable array?  I would like to have an indexable bunch of values
> but use it in a purely functional way.

You can use maps (module Map from the standard library), using
integers as keys.  

> I could always just use
> Arrays and copy them before updating, but if there's already an
> idiomatic type to use I'd prefer to use that.

Actually, there is a better way: "version arrays".  The idea is to go
ahead and update in place an array, but record the overwritten array
element in a separate data structure.  Thus, you can access the
latest version of the array in constant time, and earlier versions a
bit more slowly.  I can't point you to an actual implementation, but
no doubt others on this list can.

John Malecki wrote:

> This thread reminds me to ask if are there any guarantees for ordering
> of variant types?  Although the implementation indicates that with
>   type card = Number of int | Jack | Queen | King | Ace
> Jack < Queen and Queen < King it also says that Ace < Number 0.  I can 
> see what is going on with the implementation.  I'm curious if there
> are any ordering guarantees that I can take advantage of?  Since the
> documentation is silent on this point I doubt it.
> Oh, It does seems as if tuples, arrays and lists are always compared
> "from left to right".  This can be handy when sorting multi-
> dimensional data.  This seems like a "more natural" ordering than for
> variants but, once again, can this ordering be guaranteed for all
> ocaml programs?

The current implementation works exactly as you described.  I'm
reluctant to specify the ordering of variant and product types in more
details, as it depends very much on the data representations chosen by
the compiler, which might change one day (?).  It is however very likely
that enumerated datatypes (all constructors are constant) will always
be ordered left-to-right, and that tuples and arrays will always be
ordered lexicographically left-to-right.

Chris Hecker wrote:

>   type card = Number of int | Jack | Queen | King | Ace
> On a related note, for Xavier et al., why wasn't Number's field 0 assigned
> to the same counter as the int of the non-argument constructors?  In other
> words, why isn't there a single incrementing int id from left to right,
> regardless of arguments?

Caml Light worked as you suggest (only one "counter" for constant and
non-constant constructors).  The main reason for having two different
"counters" in OCaml is that integer tags for non-constant constructors
must be less than 246 (i.e. fit in 8 bits, with a few reserved
values).  Hence, in Caml Light, no datatype could have more than 246
constructors, while in OCaml a datatype can have arbitrarily many
constant constructors, it's only the non-constant constructors that
are limited in number.

- Xavier Leroy


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners