"ocaml_beginners"::[] How to access types within a module for matching

Jon Harrop wrote:
> On Thursday 17 May 2007 08:56:11 Hugo Ferreira wrote:
>> I wanted to avoid the copy & paste reuse technique (see my response to
>> Jon on this). Anyway my question is this: say I want to develop a
>> generic data structure of my own like Map so that:
>> 1. It still enforces an interface for the key (or any other number of
>> elements it requires)
>> 2. It be extensible i.e: make its guts available for those that need it
>> (not that I am not talking about reimplementation or tweaking, juts
>;> extending)
>
> You need to quantify exactly what you mean by "guts". Then parameterise the
> rest of the internals over the "guts" and pass the "guts" into the functor as
> a module argument.
>

Haaa.. that should have been obvious. Guts here is simply the type:

type 'a t =
Empty
| Node of 'a t * key * 'a * 'a t * int

Thanks.

Messages in this topic (0) Reply (via web post) | Start a new topic

.

Jon Harrop wrote:
> On Thursday 17 May 2007 08:36:17 Hugo Ferreira wrote:
>> You are correct of course. My initial problem is how can I extend the
>> Map to include iterators.
>
> Have you considered simply adding more powerful fold functions? Can you not
> write what you need in terms of fold?
>

Not quite. I need to backtrack. [1] seems to be a good solution.

Hugo F.

[1] http://www.lri.fr/~filliatr/ftp/publis/enum2.ps.gz

>> Richard said "make a copy of the source" but
>>; this seems unwise. What happens if a bug in the original code is
>> detected and corrected, what happens if the implementation is changed
>> without altering the types? Changes would go unnoticed and I would not
>> be the wiser.
>
> That is a problem with inextensible abstraction.
>
>>; Jon, I will be direct and hope not be rude in answering this: if I had
>> the resources I would rather use it on your book and not the library.
>> After all I want to implement specific stuff that are not generally
>> available elsewhere. (That being said, I hope your work on F# will
>;> provide you a better customer base )
>
> No worries. Our F# work has pulled in as much profit over the past month as
> OCaml for Scientists but I think F# will really take off when Foundations of
> F# is published by APress in the coming weeks.
>

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Thursday 17 May 2007 08:13:50 Hugo Ferreira wrote:
> What I meant is, what mechanisms does F# use that have the same
>; capabilities as functors?

None. F# doesn't provide a higher-order module system and there is no way to
avoid these sources of run-time error.

> If it does not have any equivalent (or better)
> construct (superficial Google search did not show anything), does that
>; mean we can live without functors?

You can live without functors: just wrap all the members in an object or
record.

> If so how is code reuse attained
> while enforcing a contract (interface) as Ocaml's Map does
>; (compatibility library does not seem to have a Map)?

F# errs on the side of making everything publically accessible. This means you
can extend things as much as possible (given that it is still a static
language) but the APIs are huge.

> The motivation for my questions are to know how one may design, develop
> and make available generic data structures that can be easily used and
> extended by someone else.

Just write functions and make them higher-order when you want pluggability. So
your insert function might be parameterized over the rebalance function to
support AVL, RB trees etc.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Thursday 17 May 2007 09:37:10 Hugo Ferreira wrote:
> Haaa.. that should have been obvious. Guts here is simply the type:
>
> type 'a t =
> Empty
>
> | Node of 'a t * key * 'a * 'a t * int

Ok. So you factor that type and some functions needed to handle it (e.g.
create a node from two children and metadata) and put them in a separate
module. Define a signature for that module. Then parameterise the Map
implementation over that module by functorizing it (it will be a curried
higher-order module).

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Thursday 17 May 2007 09:38:56 Hugo Ferreira wrote:
> Jon Harrop wrote:
> > On Thursday 17 May 2007 08:36:17 Hugo Ferreira wrote:
> >> You are correct of course. My initial problem is how can I extend the
> >> Map to include iterators.
> >
>; > Have you considered simply adding more powerful fold functions? Can you
> > not write what you need in terms of fold?
>
> Not quite. I need to backtrack. [1] seems to be a good solution.

Yes. A non-invasive but slower solution is to remember past nodes on a list as
you fold. You should be able to write an unfold that uses this approach.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

Messages in this topic (0) Reply (via web post) | Start a new topic

.

Jon,

Thanks for the input to this and the previous two messages.

HF.

Jon Harrop wrote:
> On Thursday 17 May 2007 09:38:56 Hugo Ferreira wrote:
>> Jon Harrop wrote:
>>> On Thursday 17 May 2007 08:36:17 Hugo Ferreira wrote:
>>>> You are correct of course. My initial problem is how can I extend the
>>>>; Map to include iterators.
>>> Have you considered simply adding more powerful fold functions? Can you
>>> not write what you need in terms of fold?
>> Not quite. I need to backtrack. [1] seems to be a good solution.
>
> Yes. A non-invasive but slower solution is to remember past nodes on a list as
> you fold. You should be able to write an unfold that uses this approach.
>

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Thu, 17 May 2007, Hugo Ferreira wrote:

> You are correct of course. My initial problem is how can I extend the
> Map to include iterators. Richard said "make a copy of the source" but
> this seems unwise. What happens if a bug in the original code is
> detected and corrected, what happens if the implementation is changed
> without altering the types? Changes would go unnoticed and I would not
> be the wiser.

Well, you could always just check the changelogs when a new release is
issued. And, wouldn't this only matter if the changes actually leaked
through the abstraction, so that your version of Map+ no longer behaves
the same as the stdlib Map?

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy."

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Thu, 17 May 2007, Hugo Ferreira wrote:

> I wanted to avoid the copy & paste reuse technique (see my response to
> Jon on this). Anyway my question is this: say I want to develop a
> generic data structure of my own like Map so that:
> 1. It still enforces an interface for the key (or any other number of
> elements it requires)
> 2. It be extensible i.e: make its guts available for those that need it
> (not that I am not talking about reimplementation or tweaking, juts
>; extending)
>
> How can one design/implement such a beast functionally (no OO design)?
> This is one of the reasons that prompted my questions on F#.

It seems to me that you could do this through a simple use of signatures.
Offer up a module with an unrestricted signature, one with an abstract
signature, and perhaps with something inbetween. For example:

module type Dictable =
sig
type t

val compare : t -> t -> int
end
;;

module type RawDictType =
functor (Key : Dictable) ->
sig
type key = Key.t
type 'a t = (key * 'a) list

val empty : 'a t
val add : 'a t -> key -> 'a -> 'a t
val mem : 'a t -> key -> bool
val find : 'a t -> key -> 'a
end
;;

module type AbsDictType =
functor (Key : Dictable) ->
sig
type key = Key.t
type 'a t

val empty : 'a t
val add : 'a t -> key -> 'a -> 'a t
val mem : 'a t -> key -> bool
val find : 'a t -> key -> 'a
end
;;

module type ReallyAbsDictType =
(* As we will see below, this is pretty useless without an injector
into Dictable.t for our keys *)
functor (Key : Dictable) ->
sig
type key
type 'a t

val empty : 'a t
val add : 'a t -> key -> 'a -> 'a t
val mem : 'a t -> key -> bool
val find : 'a t -> key -> 'a
end
;;

module Dict =
functor (Key : Dictable) ->
struct
type key = Key.t
type 'a t = (key * 'a) list

let empty = []
let add d key v = (key,v)::d
let mem d key = List.mem_assoc key d
let find d key = List.assoc key d
end
;;

module StringDict = Dict(String);;

module RawStringDict = (Dict : RawDictType)(String);;

module AbsStringDict = (Dict : AbsDictType)(String);;

module ReallyAbsStringDict = (Dict : ReallyAbsDictType)(String);;

let d = StringDict.empty
and rd = RawStringDict.empty
and ad = AbsStringDict.empty
and rad = ReallyAbsStringDict.empty
;;

let d = StringDict.add d "hello" 100;;
let rd = RawStringDict.add rd "hello" 100;;
let ad = AbsStringDict.add ad "hello" 100;;
let rad = ReallyAbsStringDict.add rad "hello" 100;;

let t = StringDict.mem d "hello";;
let t = RawStringDict.mem rd "hello";;
let t = AbsStringDict.mem ad "hello";;
let t = ReallyAbsStringDict.mem rad "hello";;

let a = StringDict.find d "hello";;
let a = RawStringDict.find rd "hello";;
let a = AbsStringDict.find ad "hello";;
let a = ReallyAbsStringDict.find rad "hello";;

module Dict =
functor (Key : Dictable) ->
struct
type key = Key.t
type 'a t = Empty | Node of 'a t * (key * 'a) * 'a t

let empty = Empty
let add d key v =
let rec addh = function
| Empty -> Node(Empty,(key,v),Empty)
| Node (left,(k,_ as kv),right) ->
if Key.compare key k < 0 then Node ((addh left),kv,right)
else if Key.compare key k > 0 then Node (left,kv,(addh right))
else Node (left,(key,v),right)
in addh d
let mem d key =
let rec memh = function
| Empty -> false
| Node (left,(k,_),right) ->
if Key.compare key k < 0 then memh left
else if Key.compare key k > 0 then memh right
else true
in memh d
let find d key =
let rec findh = function
| Empty -> raise Not_found
| Node (left,(k,v),right) ->
if Key.compare key k < 0 then findh left
else if Key.compare key k > 0 then findh right
else v
in findh d
end
;;

module type RawDictType =
functor (Key : Dictable) ->
sig
type key = Key.t
type 'a t = Empty | Node of 'a t * (key * 'a) * 'a t

val empty : 'a t
val add : 'a t -> key -> 'a -> 'a t
val mem : 'a t -> key -> bool
val find : 'a t -> key -> 'a
end
;;

module StringDict = Dict(String);;

module RawStringDict = (Dict : RawDictType)(String);;

module AbsStringDict = (Dict : AbsDictType)(String);;

module ReallyAbsStringDict = (Dict : ReallyAbsDictType)(String);;

let d = StringDict.empty
and rd = RawStringDict.empty
and ad = AbsStringDict.empty
and rad = ReallyAbsStringDict.empty
;;

let d = StringDict.add d "hello" 100;;
let rd = RawStringDict.add rd "hello" 100;;
let ad = AbsStringDict.add ad "hello" 100;;
let rad = ReallyAbsStringDict.add rad "hello" 100;;

let t = StringDict.mem d "hello";;
let t = RawStringDict.mem rd "hello";;
let t = AbsStringDict.mem ad "hello";;
let t = ReallyAbsStringDict.mem rad "hello";;

let a = StringDict.find d "hello";;
let a = RawStringDict.find rd "hello";;
let a = AbsStringDict.find ad "hello";;
let a = ReallyAbsStringDict.find rad "hello";;

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy.&quot;

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder

Messages in this topic (0) Reply (via web post) | Start a new topic

.

William D. Neumann wrote:
&gt; On Thu, 17 May 2007, Hugo Ferreira wrote:
&gt;
>>; You are correct of course. My initial problem is how can I extend the
>> Map to include iterators. Richard said "make a copy of the source&quot; but
>> this seems unwise. What happens if a bug in the original code is
>&gt; detected and corrected, what happens if the implementation is changed
>> without altering the types? Changes would go unnoticed and I would not
>> be the wiser.
&gt;
> Well, you could always just check the changelogs when a new release is
> issued. And, wouldn't this only matter if the changes actually leaked
> through the abstraction, so that your version of Map+ no longer behaves
> the same as the stdlib Map?
>;

Well I really not concerned with adherence to stdlib's Map but would
like to ensure that I use the latest sources. With the input I got from
you people this doesn't seem possible unless stdlib itself is changed.
Which leaves me wondering if this issue (extending modules I mean) is
also considered in other Ocaml libraries out their.

> William D. Neumann
>
> ---
>
> "There's just so many extra children, we could just feed the
> children to these tigers. We don't need them, we're not doing
> anything with them.
&gt;
> Tigers are noble and sleek; children are loud and messy.&quot;
>
> -- Neko Case
>;
> Life is unfair. Kill yourself or get over it.
> -- Black Box Recorder
>
>
> Archives up to November 11, 2006 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.
> Yahoo! Groups Links
&gt;
>
>
>

Messages in this topic (0) Reply (via web post) | Start a new topic

.

William,

William D. Neumann wrote:
&gt; On Thu, 17 May 2007, Hugo Ferreira wrote:
&gt;
>>; I wanted to avoid the copy & paste reuse technique (see my response to
>&gt; Jon on this). Anyway my question is this: say I want to develop a
>&gt; generic data structure of my own like Map so that:
&gt;> 1. It still enforces an interface for the key (or any other number of
>&gt; elements it requires)
>> 2. It be extensible i.e: make its guts available for those that need it
>&gt; (not that I am not talking about reimplementation or tweaking, juts
>;> extending)
>>
>> How can one design/implement such a beast functionally (no OO design)?
>> This is one of the reasons that prompted my questions on F#.
>
> It seems to me that you could do this through a simple use of signatures.
> Offer up a module with an unrestricted signature, one with an abstract
> signature, and perhaps with something inbetween. For example:
>

This is one very complete example. I think this would go well in
http://www.ocaml-tutorial.org/. However after Jon's input I think what I
need is a functor with more that one "parameter" (injector?): one for
the key and another for the base (raw) type and associated
functionality. I can then "extend" the base (raw) type because now I
have access to its elements.

Thanks for the example.
Hugo F.

&gt; module type Dictable =
> sig
> type t
>
> val compare : t -> t -> int
> end
> ;;
>
> module type RawDictType =
> functor (Key : Dictable) ->
&gt; sig
> type key = Key.t
&gt; type 'a t = (key * 'a) list
>;
> val empty : 'a t
> val add : 'a t -> key -> 'a -> 'a t
> val mem : 'a t -> key -> bool
>; val find : 'a t -> key -> 'a
> end
> ;;
>
> module type AbsDictType =
> functor (Key : Dictable) ->
&gt; sig
> type key = Key.t
&gt; type 'a t
>
> val empty : 'a t
> val add : 'a t -> key -> 'a -> 'a t
> val mem : 'a t -> key -> bool
>; val find : 'a t -> key -> 'a
> end
> ;;
>
> module type ReallyAbsDictType =
> (* As we will see below, this is pretty useless without an injector
> into Dictable.t for our keys *)
> functor (Key : Dictable) ->
&gt; sig
> type key
> type 'a t
>
> val empty : 'a t
> val add : 'a t -> key -> 'a -> 'a t
> val mem : 'a t -> key -> bool
>; val find : 'a t -> key -> 'a
> end
> ;;
>
> module Dict =
> functor (Key : Dictable) ->
&gt; struct
&gt; type key = Key.t
&gt; type 'a t = (key * 'a) list
>;
> let empty = []
> let add d key v = (key,v)::d
> let mem d key = List.mem_assoc key d
> let find d key = List.assoc key d
> end
> ;;
>
> module StringDict = Dict(String);;
>;
> module RawStringDict = (Dict : RawDictType)(String);;
>
> module AbsStringDict = (Dict : AbsDictType)(String);;
>
> module ReallyAbsStringDict = (Dict : ReallyAbsDictType)(String);;
>
> let d = StringDict.empty
&gt; and rd = RawStringDict.empty
> and ad = AbsStringDict.empty
> and rad = ReallyAbsStringDict.empty
>; ;;
>
> let d = StringDict.add d "hello" 100;;
&gt; let rd = RawStringDict.add rd "hello" 100;;
&gt; let ad = AbsStringDict.add ad "hello" 100;;
&gt; let rad = ReallyAbsStringDict.add rad "hello" 100;;
&gt;
> let t = StringDict.mem d "hello";;
> let t = RawStringDict.mem rd "hello";;
> let t = AbsStringDict.mem ad "hello";;
> let t = ReallyAbsStringDict.mem rad "hello";;
>
> let a = StringDict.find d "hello";;
> let a = RawStringDict.find rd "hello";;
> let a = AbsStringDict.find ad "hello";;
> let a = ReallyAbsStringDict.find rad "hello";;
>
>
> module Dict =
> functor (Key : Dictable) ->
&gt; struct
&gt; type key = Key.t
&gt; type 'a t = Empty | Node of 'a t * (key * 'a) * 'a t
>
> let empty = Empty
&gt; let add d key v =
> let rec addh = function
> | Empty -> Node(Empty,(key,v),Empty)
>; | Node (left,(k,_ as kv),right) ->
&gt; if Key.compare key k < 0 then Node ((addh left),kv,right)
>; else if Key.compare key k > 0 then Node (left,kv,(addh right))
> else Node (left,(key,v),right)
> in addh d
> let mem d key =
> let rec memh = function
> | Empty -> false
&gt; | Node (left,(k,_),right) ->
&gt; if Key.compare key k < 0 then memh left
>; else if Key.compare key k > 0 then memh right
&gt; else true
>; in memh d
> let find d key =
> let rec findh = function
> | Empty -> raise Not_found
> | Node (left,(k,v),right) ->
&gt; if Key.compare key k < 0 then findh left
>; else if Key.compare key k > 0 then findh right
&gt; else v
> in findh d
> end
> ;;
>
> module type RawDictType =
> functor (Key : Dictable) ->
&gt; sig
> type key = Key.t
&gt; type 'a t = Empty | Node of 'a t * (key * 'a) * 'a t
>
> val empty : 'a t
> val add : 'a t -> key -> 'a -> 'a t
> val mem : 'a t -> key -> bool
>; val find : 'a t -> key -> 'a
> end
> ;;
>
>
> module StringDict = Dict(String);;
>;
> module RawStringDict = (Dict : RawDictType)(String);;
>
> module AbsStringDict = (Dict : AbsDictType)(String);;
>
> module ReallyAbsStringDict = (Dict : ReallyAbsDictType)(String);;
>
> let d = StringDict.empty
&gt; and rd = RawStringDict.empty
> and ad = AbsStringDict.empty
> and rad = ReallyAbsStringDict.empty
>; ;;
>
> let d = StringDict.add d "hello" 100;;
&gt; let rd = RawStringDict.add rd "hello" 100;;
&gt; let ad = AbsStringDict.add ad "hello" 100;;
&gt; let rad = ReallyAbsStringDict.add rad "hello" 100;;
&gt;
> let t = StringDict.mem d "hello";;
> let t = RawStringDict.mem rd "hello";;
> let t = AbsStringDict.mem ad "hello";;
> let t = ReallyAbsStringDict.mem rad "hello";;
>
> let a = StringDict.find d "hello";;
> let a = RawStringDict.find rd "hello";;
> let a = AbsStringDict.find ad "hello";;
> let a = ReallyAbsStringDict.find rad "hello";;
>
> William D. Neumann
>
>
> ---
>
> "There's just so many extra children, we could just feed the
> children to these tigers. We don't need them, we're not doing
> anything with them.
&gt;
> Tigers are noble and sleek; children are loud and messy.&quot;
>
> -- Neko Case
>;
> Life is unfair. Kill yourself or get over it.
> -- Black Box Recorder
>
>
> Archives up to November 11, 2006 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.
> Yahoo! Groups Links
&gt;
>
>
>

Messages in this topic (0) Reply (via web post) | Start a new topic

.