[Caml-list] Functor implementation

[Caml-list] Functor implementation

[Chris Clearwater]

Hi all, I was curious as to how ocaml implements functors and finding no help
with google, I thought I could ask on the list. After giving it a little
thought I was thinking they might be implemented as follows:

type 'a tree = Empty | Node of ('a tree) * 'a * ('a tree)
type comparison = GT | EQ | LT

let node l v r = Node(l, v, r)
let single v = Node(Empty, v, Empty)

let rec insert c t a =
    match t with
        Empty -> single a
      | Node(l, v, r) -> match (c a v) with
            LT -> node (insert c l a) v r
          | EQ -> t
          | GT -> node l v (insert c r a)

let rec member c t a =
    match t with
        Empty -> false
      | Node(l, v, r) -> match (c a v) with
            LT -> member c l a
          | EQ -> true
          | GT -> member c r a

(* Functor implementation follows *)

type 'a setmodule = {
    empty: 'a tree;
    insert: 'a tree -> 'a -> 'a tree;
    member: 'a tree -> 'a -> bool;
}

let make c = {
    empty = Empty;
    insert = insert c;
    member = member c;
}

(* Use a functor *)
let compare x y = let cmp = x - y in if cmp > 0 then GT else if cmp < 0 then LT else EQ
let mymodule = make compare
let s = mymodule.insert mymodule.empty 5

EOF

How far off is Ocaml's way and is the performance comparable? And on a
sidenote, wouldn't it be beneficial for there to be a built in comparison
type and a function to convert from integers greater than less than or
equal to, to the comparrison type? I imagine this would clarify code
that uses comparisons greatly.

Thanks in advance for your answers!

-------------------
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] Functor implementation

[Xavier Leroy]

> Hi all, I was curious as to how ocaml implements functors and
> finding no help with google, I thought I could ask on the
> list.

Basically, a structure is compiled like a record, and a functor like a
function.

> After giving it a little thought I was thinking they might be
> implemented as follows:
> [...]
> How far off is Ocaml's way and is the performance comparable?

It's pretty close, and the performance is comparable.
Here is pseudocode that is closest to the actual compiled code:

 type 'a orderedtype = {
     compare: 'a -> 'a -> comparison
 }

 type 'a setmodule = {
     empty: 'a tree;
     insert: 'a tree -> 'a -> 'a tree;
     member: 'a tree -> 'a -> bool;
 }

 let make compare =

   let node l v r = Node(l, v, r) in
   let single v = Node(Empty, v, Empty) in

   let rec insert t a =
       match t with
           Empty -> single a
         | Node(l, v, r) -> match (compare.compare a v) with
               LT -> node (insert l a) v r
             | EQ -> t
             | GT -> node l v (insert r a) in

  (* other struct members similar *)

  {
     empty = Empty;
     insert = insert;
     member = member
  }

  let mymodule =
    make { compare = fun x y -> ... }


Now, let me warn you about the following code:

> let compare x y =
    let cmp = x - y in if cmp > 0 then GT else if cmp < 0 then LT else EQ

which doesn't work if x and y are sufficiently far apart
(e.g. x = max_int and y = min_int).

- 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

Re: [Caml-list] Functor implementation

[Chris Clearwater]

On Wed, Jul 23, 2003 at 03:01:32PM +0200, Xavier Leroy wrote:
> Now, let me warn you about the following code:
> 
> > let compare x y =
>     let cmp = x - y in if cmp > 0 then GT else if cmp < 0 then LT else EQ
> 
> which doesn't work if x and y are sufficiently far apart
> (e.g. x = max_int and y = min_int).
> 
> - Xavier Leroy

Ahh, thanks, functors now fit nicely in my head. And yeah that cmp
function was kind of braindead. I dont know why I didnt simply write it
as : let cmp x y = if x > y then GT else if x < y then LT else EQ. But
it would still be nice if the built in comparison function returned a
sum type. And there was provided a helper function:
let comparison_of_int x = if x > 0 then GT else if x < 0 then LT else EQ.
Maybe "ordering" is a more appropriate name. Also, true and false appear
to be a sum type: type bool = True | False, except you can't have lower
case constructor names. Does this signal the fact that there is some
kind of limitation with having primitive sum types?

-------------------
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] Functor implementation

[brogoff]

On Wed, 23 Jul 2003, Chris Clearwater wrote:
> Ahh, thanks, functors now fit nicely in my head. And yeah that cmp
> function was kind of braindead. I dont know why I didnt simply write it
> as : let cmp x y = if x > y then GT else if x < y then LT else EQ. But
> it would still be nice if the built in comparison function returned a
> sum type. 

I agree. I think I made a petty complaint about this some time ago. And 
I'd make another (even more petty) complaint about your choice of constructor 
names now, as I'd prefer Equal, LessThan, GreaterThan or Eq, Lt, Gt, so that 
all caps names could be reserved by convention for module types and "view" 
constructor names. By view constructors, I'm referring to the technique 
described by Wang and Murphy for simulating views in ML; that technique is 
even better in OCaml with private types, though I suspect that we'd pay more 
for the indirections than would MLton users. 

> Maybe "ordering" is a more appropriate name. Also, true and false appear
> to be a sum type: type bool = True | False, except you can't have lower
> case constructor names. Does this signal the fact that there is some
> kind of limitation with having primitive sum types?

Nope, probably hysterical raisins again. Note that Revised fixes this. 

-- Brian


-------------------
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