[Caml-list] polymorphic function not recognised as such

[Caml-list] polymorphic function not recognised as such

[Benjamin Geer]

Can anyone explain to me why the following doesn't compile:

----------

type thing = Int of int | String of string ;;

let int_of_thing t =
   match t with
       Int i -> i
     | String s -> int_of_string s ;;

let string_of_thing t =
   match t with
       Int i -> string_of_int i
     | String s -> s ;;

let compare_things t1 t2 comparison_fun =
   match (t1, t2) with
       (Int i, _) -> comparison_fun i (int_of_thing t2)
     | (String s, _) -> comparison_fun s (string_of_thing t2) ;;

let is_less_than t1 t2 =
   compare_things t1 t2 (<) ;;

let is_greater_than t1 t2 =
   compare_things t1 t2 (>) ;;

----------

The compiler says:

File "test.ml", line 16, characters 38-39:
This expression has type string but is here used with type int

It seems to have decided that in the function compare_things, 
comparison_fun is int -> int -> 'a because that's how it's used in the 
first pattern, not realising that I mean to pass a polymorphic function, 
'a -> 'a -> bool.

Is there a way to make this work?  (Specifying the type of 
comparison_fun as 'a -> 'a -> bool makes no difference.)

Ben

-------------------
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] polymorphic function not recognised as such

[Jean-Baptiste Rouquier]

The following type
    compare_things : thing -> thing -> ('a -> 'a -> bool) -> bool
doesn't mean that comparison_fun has to be polymorphic, but it means
that any function with type ('a -> 'a -> bool), where 'a is any type, is
acceptable. For instance, the type checker would accept a function of
the type (char -> char -> bool).

If you force the type checker to accept your function, for instance this
way (warning, awful code !):

let compare_things t1 t2 (comparison_fun: 'a -> 'a -> bool) =
  match (t1, t2) with
      (Int i, _) -> comparison_fun (Obj.magic i) (Obj.magic
(int_of_thing t2))
    | (String s, _) -> comparison_fun (Obj.magic s) (Obj.magic
(string_of_thing t2)) ;;


then you can get a segfault if you don't give a polymorphic function to
compare_things :

let string_rev s =
  let l = String.length s in
  let result = String.create l in
  for i=0 to l-1 do result.[i] <- s.[l-i-1] done;
  result

let my_comparison s s' =
  (string_rev s) > (string_rev s')

let ok = compare_things (Int 0) (String "42") (<)
let segfaults = compare_things (Int 0) (String "42") my_comparison


work around: pass 2 args to compare_things, namely compare_int and
compare_strings.
Jean-Baptiste.




Benjamin Geer wrote:

> Can anyone explain to me why the following doesn't compile:
>
> ----------
>
> type thing = Int of int | String of string ;;
>
> let int_of_thing t =
>   match t with
>       Int i -> i
>     | String s -> int_of_string s ;;
>
> let string_of_thing t =
>   match t with
>       Int i -> string_of_int i
>     | String s -> s ;;
>
> let compare_things t1 t2 comparison_fun =
>   match (t1, t2) with
>       (Int i, _) -> comparison_fun i (int_of_thing t2)
>     | (String s, _) -> comparison_fun s (string_of_thing t2) ;;
>
> let is_less_than t1 t2 =
>   compare_things t1 t2 (<) ;;
>
> let is_greater_than t1 t2 =
>   compare_things t1 t2 (>) ;;
>
> ----------
>
> The compiler says:
>
> File "test.ml", line 16, characters 38-39:
> This expression has type string but is here used with type int
>
> It seems to have decided that in the function compare_things, 
> comparison_fun is int -> int -> 'a because that's how it's used in the 
> first pattern, not realising that I mean to pass a polymorphic 
> function, 'a -> 'a -> bool.
>
> Is there a way to make this work?  (Specifying the type of 
> comparison_fun as 'a -> 'a -> bool makes no difference.)
>
> Ben
>
> -------------------
> 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




-------------------
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] polymorphic function not recognised as such

[Benjamin Geer]

Jean-Baptiste Rouquier wrote:
>    compare_things : thing -> thing -> ('a -> 'a -> bool) -> bool
> doesn't mean that comparison_fun has to be polymorphic, but it means 
> that any function with type ('a -> 'a -> bool), where 'a is any type, is 
> acceptable. For instance, the type checker would accept a function of 
> the type (char -> char -> bool).

OK, but it seems that the type checker has inferred the type of 
comparison_fun just by looking at its first use in compare_things, and 
has decided that it must be monomorphic; this is an incorrect inference. 
  My naive impression is that if the type checker was willing to accept 
both uses of comparison_fun as valid (or perhaps if it also looked at 
the places where compare_things is called), it would conclude that 
comparison_fun does indeed have to be polymorphic.  In that case, I 
would get a compile error if I tried to pass a non-polymorphic function 
to compare_things.  Would this be this asking too much?  (I suspect the 
answer is yes; I'm just curious...)

Ben

> [...]
> Benjamin Geer wrote:
> 
>> Can anyone explain to me why the following doesn't compile:
>>
>> ----------
>>
>> type thing = Int of int | String of string ;;
>>
>> let int_of_thing t =
>>   match t with
>>       Int i -> i
>>     | String s -> int_of_string s ;;
>>
>> let string_of_thing t =
>>   match t with
>>       Int i -> string_of_int i
>>     | String s -> s ;;
>>
>> let compare_things t1 t2 comparison_fun =
>>   match (t1, t2) with
>>       (Int i, _) -> comparison_fun i (int_of_thing t2)
>>     | (String s, _) -> comparison_fun s (string_of_thing t2) ;;
>>
>> let is_less_than t1 t2 =
>>   compare_things t1 t2 (<) ;;
>>
>> let is_greater_than t1 t2 =
>>   compare_things t1 t2 (>) ;;
>>
>> ----------
>>
>> The compiler says:
>>
>> File "test.ml", line 16, characters 38-39:
>> This expression has type string but is here used with type int
>>
>> It seems to have decided that in the function compare_things, 
>> comparison_fun is int -> int -> 'a because that's how it's used in the 
>> first pattern, not realising that I mean to pass a polymorphic 
>> function, 'a -> 'a -> bool.
>>
>> Is there a way to make this work?  (Specifying the type of 
>> comparison_fun as 'a -> 'a -> bool makes no difference.)
>>
>> Ben

-------------------
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] polymorphic function not recognised as such

[Olivier Andrieu]

 Benjamin Geer [Sunday 14 December 2003] :
 >
 > Jean-Baptiste Rouquier wrote:
 > >    compare_things : thing -> thing -> ('a -> 'a -> bool) -> bool
 > > doesn't mean that comparison_fun has to be polymorphic, but it means 
 > > that any function with type ('a -> 'a -> bool), where 'a is any type, is 
 > > acceptable. For instance, the type checker would accept a function of 
 > > the type (char -> char -> bool).
 > 
 > OK, but it seems that the type checker has inferred the type of
 > comparison_fun just by looking at its first use in compare_things,
 > and has decided that it must be monomorphic; this is an incorrect
 > inference.
 >   My naive impression is that if the type checker was willing to
 > accept both uses of comparison_fun as valid (or perhaps if it also
 > looked at the places where compare_things is called), it would
 > conclude that comparison_fun does indeed have to be polymorphic.
 > In that case, I would get a compile error if I tried to pass a
 > non-polymorphic function to compare_things.  Would this be this
 > asking too much?  (I suspect the answer is yes; I'm just
 > curious...)

You could use a record holding a field with a fully polymorphic type : 

type t = { c : 'a. 'a -> 'a -> bool }

let compare_things t1 t2 comparison_fun =
   match (t1, t2) with
       (Int i, _) -> comparison_fun.c i (int_of_thing t2)
     | (String s, _) -> comparison_fun.c s (string_of_thing t2) ;;

-- 
   Olivier

-------------------
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] polymorphic function not recognised as such

[Michal Moskal]

On Sun, Dec 14, 2003 at 09:38:24PM +0000, Benjamin Geer wrote:
> Jean-Baptiste Rouquier wrote:
> >   compare_things : thing -> thing -> ('a -> 'a -> bool) -> bool
> >doesn't mean that comparison_fun has to be polymorphic, but it means 
> >that any function with type ('a -> 'a -> bool), where 'a is any type, is 
> >acceptable. For instance, the type checker would accept a function of 
> >the type (char -> char -> bool).
> 
> OK, but it seems that the type checker has inferred the type of 
> comparison_fun just by looking at its first use in compare_things, and 
> has decided that it must be monomorphic; this is an incorrect inference. 
>  My naive impression is that if the type checker was willing to accept 
> both uses of comparison_fun as valid (or perhaps if it also looked at 
> the places where compare_things is called), it would conclude that 
> comparison_fun does indeed have to be polymorphic.  In that case, I 
> would get a compile error if I tried to pass a non-polymorphic function 
> to compare_things.  Would this be this asking too much?  (I suspect the 
> answer is yes; I'm just curious...)

Polymorphism in ML is flat, that is all type variables are quantified
before the function, not in the arguments. The type ('a -> foo) -> bar
means forall 'a. ('a -> foo) -> bar, and not (forall 'a. 'a -> foo) -> bar.

This is one of the costs of type inference.

In OCaml you can simulate deep polymorphism with polymorphic records
(but you have to write explicit type then).

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: When in doubt, use brute force. -- Ken Thompson : {E-,w}-- {b++,e}>+++ h

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