Type error

Type error

[Denis Bueno]

I'm writing a simple (stupid) de-functorised Set library. Its skeleton is:

,----
| type 'a t
|   (** The type of sets. *)
|
| val empty: 'a t
|   (** The empty set. *)
|
| val mem: 'a -> 'a t -> bool
|   (** [mem x s] tests whether [x] belongs to the set [s]. *)
|
| val add: 'a -> 'a t -> 'a t
|   (** [add x s] returns a set containing all elements of [s],
|       plus [x]. If [x] was already in [s], [s] is returned unchanged. *)
`----

In my implementation, sets are lists.

One of the things I'd like to do is write an of_array to create an
array from a set. However, it is often the case that I have an array
of objects from which I'd like to pull out one field & make a set of
those fields. So, my of_array looks like this:

Interface:
,----
| val of_array: ?getter : ('b -> 'a) -> 'b array -> 'a t
|   (** [of_array xs] returns a set containing the elements in [xs]. *)
`----

Implementation:
,----
| let of_array ?(getter = fun x -> x) xs =
|   Array.fold_right (fun x set -> add (getter x) set) xs empty;;
`----

I get a type error when trying to compile this. I don't know how to
fix it, or even if it's possible without wrecking my nice of_array
signature. The type error:

,----
| The implementation pSet.ml does not match the interface pSet.cmi:
| Values do not match:
|   val of_array : ?getter:('a -> 'a) -> 'a array -> 'a list
| is not included in
|   val of_array : ?getter:('a -> 'b) -> 'a array -> 'b t
`----

I understand why this shouldn't be compilable, but, is it possible to
do something similarly elegant (without creating a separate function)?

-Denis

Re: [Caml-list] Type error

[Jonathan Roewen]

How about not defining a default, and matching on getter as an option?

let of_array ?getter xs = match getter with
| None -> Array.fold_right (fun x set -> add x set) xs empty
| Some f -> Array.fold_right (fun x set -> add (f x) set) xs empty

Jonathan


On 10/15/06, Denis Bueno <dbueno@gmail.com> wrote:
> I'm writing a simple (stupid) de-functorised Set library. Its skeleton is:
>
> ,----
> | type 'a t
> |   (** The type of sets. *)
> |
> | val empty: 'a t
> |   (** The empty set. *)
> |
> | val mem: 'a -> 'a t -> bool
> |   (** [mem x s] tests whether [x] belongs to the set [s]. *)
> |
> | val add: 'a -> 'a t -> 'a t
> |   (** [add x s] returns a set containing all elements of [s],
> |       plus [x]. If [x] was already in [s], [s] is returned unchanged. *)
> `----
>
> In my implementation, sets are lists.
>
> One of the things I'd like to do is write an of_array to create an
> array from a set. However, it is often the case that I have an array
> of objects from which I'd like to pull out one field & make a set of
> those fields. So, my of_array looks like this:
>
> Interface:
> ,----
> | val of_array: ?getter : ('b -> 'a) -> 'b array -> 'a t
> |   (** [of_array xs] returns a set containing the elements in [xs]. *)
> `----
>
> Implementation:
> ,----
> | let of_array ?(getter = fun x -> x) xs =
> |   Array.fold_right (fun x set -> add (getter x) set) xs empty;;
> `----
>
> I get a type error when trying to compile this. I don't know how to
> fix it, or even if it's possible without wrecking my nice of_array
> signature. The type error:
>
> ,----
> | The implementation pSet.ml does not match the interface pSet.cmi:
> | Values do not match:
> |   val of_array : ?getter:('a -> 'a) -> 'a array -> 'a list
> | is not included in
> |   val of_array : ?getter:('a -> 'b) -> 'a array -> 'b t
> `----
>
> I understand why this shouldn't be compilable, but, is it possible to
> do something similarly elegant (without creating a separate function)?
>
> -Denis
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Type error

[skaller]

On Sat, 2006-10-14 at 23:29 -0400, Denis Bueno wrote:
> I'm writing a simple (stupid) de-functorised Set library. Its skeleton is:

> 
> One of the things I'd like to do is write an of_array to create an
> array from a set. However, it is often the case that I have an array
> of objects from which I'd like to pull out one field & make a set of
> those fields. So, my of_array looks like this:


> I understand why this shouldn't be compilable, but, is it possible to
> do something similarly elegant (without creating a separate function)?

Well yes, you can do something vastly more comprehensive,
and at the same time save yourself months of implementation
work .. by simply using Extlib.

Extlib decouples data structures in a similar way to C++.
C++ uses iterators, Extlib uses streams.

The trick is factorisation: instead of

	to_set: Array --> Set
	to_array: Set --> Array

etc etc etc etc .. combinatorial explosion which invades all
data structures ..

you use:

	to_stream: Set -> stream
	from_stream: stream -> Set

	to_stream: Array  -> stream
	from_Stream: stream -> Array

and now you can define:

	let array_to_set a = Set.from_stream (Array.to_stream a)

So to get only one field of an array .. or anything else,
all you need is to write the extractor:

	proj: 'a -> 'b

and use

	stream_map proj x

like

	Set.from_stream (stream_map proj (Array.to_stream a))

Note that Extlib tries to be lazy so it will not actually build
two streams here (the actual function calls used by Extlib
may have different names).


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Type error

[Jonathan Roewen]

Oops, I should've tested first -- still same problem with the explicit
matching :-) I think you either have to always 'map', or never 'map'.

Jonathan

On 10/15/06, Denis Bueno <dbueno@gmail.com> wrote:
> I'm writing a simple (stupid) de-functorised Set library. Its skeleton is:
>
> ,----
> | type 'a t
> |   (** The type of sets. *)
> |
> | val empty: 'a t
> |   (** The empty set. *)
> |
> | val mem: 'a -> 'a t -> bool
> |   (** [mem x s] tests whether [x] belongs to the set [s]. *)
> |
> | val add: 'a -> 'a t -> 'a t
> |   (** [add x s] returns a set containing all elements of [s],
> |       plus [x]. If [x] was already in [s], [s] is returned unchanged. *)
> `----
>
> In my implementation, sets are lists.
>
> One of the things I'd like to do is write an of_array to create an
> array from a set. However, it is often the case that I have an array
> of objects from which I'd like to pull out one field & make a set of
> those fields. So, my of_array looks like this:
>
> Interface:
> ,----
> | val of_array: ?getter : ('b -> 'a) -> 'b array -> 'a t
> |   (** [of_array xs] returns a set containing the elements in [xs]. *)
> `----
>
> Implementation:
> ,----
> | let of_array ?(getter = fun x -> x) xs =
> |   Array.fold_right (fun x set -> add (getter x) set) xs empty;;
> `----
>
> I get a type error when trying to compile this. I don't know how to
> fix it, or even if it's possible without wrecking my nice of_array
> signature. The type error:
>
> ,----
> | The implementation pSet.ml does not match the interface pSet.cmi:
> | Values do not match:
> |   val of_array : ?getter:('a -> 'a) -> 'a array -> 'a list
> | is not included in
> |   val of_array : ?getter:('a -> 'b) -> 'a array -> 'b t
> `----
>
> I understand why this shouldn't be compilable, but, is it possible to
> do something similarly elegant (without creating a separate function)?
>
> -Denis
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Type error

[Etienne Miret]

On oct 15 2006 at 05:29, Denis Bueno wrote:
> ,----
> | val of_array: ?getter : ('b -> 'a) -> 'b array -> 'a t
> |   (** [of_array xs] returns a set containing the elements in  
> [xs]. *)
> `----
>
> I get a type error when trying to compile this. I don't know how to
> fix it, or even if it's possible without wrecking my nice of_array
> signature.

Your very nice of_array signature... I'm afraid you're signature is  
awful. Basically you're trying to get a 'a -> 'b type, which is  
impossible without using Obj.magic, and awful anyway. See, if you do

# let my_array = [| (1,'a') ; (2,'b') |];;
val my_array : (int * char) array = [|(1, 'a'); (2, 'b')|]
# let set = of_array ~getter:snd my_array;;
val set : char list = ['a'; 'b']

This is okay, but if you decide not to give the optional argument:

# let set2 = of_array my_array

Then what type should be inferred for set2? of course the real type  
is (int * char) t, but with the signature you gave for of_array you  
cannot infer it, since they're is no way to know that the default  
value for the optional argument has the type 'a -> 'a.

By implementing of_array with Obj.magic, you get:

# let set2 = of_array my_array;;
val set2 : 'a list = [<poly>; <poly>]

and then you can do funny (and ugly) things:

# add 4 set2;;
- : int list = [4; 354636; 354630]
# add 'c' set2;;
- : char list = ['c'; '\
36'; '\
30']
# add (3,'c') set2;;
- : (int * char) list = [(1, 'a'); (2, 'b'); (3, 'c')]

I implemented of_array this way:
# let of_array ?(getter = fun x -> Obj.magic x) xs =
   Array.fold_right (fun x set -> add (getter x) set) xs empty;;
   val of_array : ?getter:('a -> 'b) -> 'a array -> 'b list = <fun>

Regards,

Etienne

Re: [Caml-list] Type error

[Jacques Garrigue]

From: "Denis Bueno" <dbueno@gmail.com>

> Interface:
> ,----
> | val of_array: ?getter : ('b -> 'a) -> 'b array -> 'a t
> |   (** [of_array xs] returns a set containing the elements in [xs]. *)
> `----

As somebody already pointed out, this interface is problematic.
It asks for a function ('b -> 'a),  but says that it can do without
one, for any 'a and 'b. However, the only function of type ('b -> 'a)
when 'a and 'b are different (which is allowed by the interface) is
Obj.magic, which is clearly not what you intend.

Actually, what you would want is some kind of dependent typing:

* if getter is provided, then 'a and 'b may be different

* if getter is omitted, then 'a and 'b must be equal, i.e. the type is
   ?getter:('a -> 'a) -> 'a array -> 'a t

This is clearly much stronger than the polymorphism of ocaml, which
requires the same type to be valid in both cases, i.e. 'a = 'b even if
getter is provided.

Some extensions to the type system, like GADT or dependent polymorpic
variant matching, might allow something close to what you ask for, but
you would still have to pass a special constructor for getter rather
than omit it, so there would be no improvement.

The only simple solution I see is to define two functions, one with an
extra argument and one without.

Jacques Garrigue

type error

[Jacques Le Normand]

[-- Attachment #1: Type: text/plain, Size: 320 bytes --]

hello caml-list
thanks for all the help so far; it's been very educational
there's a type error I can't get my head around:


class a =
object
end

and b =
object
  inherit a
  method d (e : b) = (e :> a)
end


gives the error:

The abbreviation b expands to type < d : b -> a > but is used with type <  >

why is this?

[-- Attachment #2: Type: text/html, Size: 438 bytes --]

Re: type error

[Remi Vanicat]

Martin Jambon <martin.jambon@ens-lyon.org> writes:

> A more idiomatic way is to declare the following type:
>
> type foo = < bar: int >

An even more idiomatic way to do it is by using type class:

class type foo = object method bar : int end;;

and then you can use #foo that will be the type you wanted, Martin's
example become:

# class type foo = object method bar : int end;;
class type foo = object method bar : int end
# let print_bar (x : #foo) = print_int x # bar;;
val print_bar : #foo -> unit = <fun>
# let x =
    (object
     method bar = 123
       method hello () = print_endline "hello"
       end);;
val x : < bar : int; hello : unit -> unit > = <obj>
# print_bar x;;
123- : unit = ()



-- 
Rémi Vanicat

type error

[Jacques Le Normand]

[-- Attachment #1: Type: text/plain, Size: 232 bytes --]

Hello caml-list,
I don't quite understand what the error is here:

 type foo = <bar:int;..>

error:

A type variable is unbound in this type declaration.
In definition < bar : int; .. > the variable 'a is unbound


cheers
--Jacques

[-- Attachment #2: Type: text/html, Size: 298 bytes --]

Type error

[Jon Harrop]

I've got a type error:

This type of expression, <height:int; width:int; _..> -> unit, contains type 
variables that cannot be generalized

which appears with the form:

let f =
  let t = ref None in
  fun data -> ...

but not in the unnested form:

let t = ref None

let f =
  fun data -> ...

Is that supposed to happen? I thought those two forms were exactly equivalent 
(except for polluting the outer namespace in the latter case).

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists