Stdlib

Stdlib

[Jonathan Bryant]

Quick (and rather random question) about the standard library.  I
noticed that, like the STL, many of the modules are very similar and
implement many of the same functions (iter, map, etc.).  Unlike the STL
or the Java Standard API, these modules are each completely
independent.  Why hasn't there been a push to do something like
functorize these modules?  For example: List, Array, Hashtbl, Set, and
Map are all collections.  Couldn't you factor out something to make it
easier to extend the library, sort of like the Java API?  Parametric
Polymorphism handles the generics of the elements of the set, so
couldn't the algorithms be factored out leaving three distinct parts
(Elements, Collections of Elements, Operations on Collections), sort of
like in the STL?

I know Java and C++ are bad words here, but you have to admit that at
least that part of Sun's library is rather well designed as is, for the
most part, the STL.  Give the devil his due, I guess... :)

--Jonathan Bryant
  jtbryant@valdosta.edu
  Student Intern
  Unix System Operations
  VSU Information Technology

"Das Leben ohne Music ist einfach ein Irrtum, eine Strapaze, ein" Exil."
("Life without music is simply an error, a pain, an exile.")
--Frederich Nietzsche

"The three cardinal values of a programmer are laziness, impatience, and
hubris."
--Perl Man Page

Re: [Caml-list] Stdlib

[skaller]

On Mon, 2005-10-31 at 09:41 -0500, Jonathan Bryant wrote:
> Quick (and rather random question) about the standard library.  I
> noticed that, like the STL, many of the modules are very similar and
> implement many of the same functions (iter, map, etc.).  Unlike the STL
> or the Java Standard API, these modules are each completely
> independent.  Why hasn't there been a push to do something like
> functorize these modules? 

Because the technology to do that is WAY in advance of the
current Ocaml.

What you are asking for is *polyadic* functions, aka
functorial polymorphism. For example, a fold function
that works on all data structures, that is, polymorphic
not just on the data type (such as int), 
but also the data functor (such as list).

Such a function would never work with abstracted modules,
it would require data types to be defined entirely algebraically.

All of this can be done (I worked on a system that did it),
however it is definitely non-trivial. It is well in advance
of anything Haskell can do also.

In fact, C++ DOES provide such functions: the STL is built
on this concept. .. however the mechanism is not 'type safe': 
it works only by hackery based on overloading
and dependent name lookup.

This problem is partly solved in Extlib, which provides an
equivalent concept to STL iterators. However the Extlib
solution, whilst not so general as STL, is fully safe
(since it is written in Ocaml .. :)


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

Re: [Caml-list] Stdlib

[Jonathan Roewen]

> Because the technology to do that is WAY in advance of the
> current Ocaml.
>
> What you are asking for is *polyadic* functions, aka
> functorial polymorphism. For example, a fold function
> that works on all data structures, that is, polymorphic
> not just on the data type (such as int),
> but also the data functor (such as list).
>
> Such a function would never work with abstracted modules,
> it would require data types to be defined entirely algebraically.
>
> All of this can be done (I worked on a system that did it),
> however it is definitely non-trivial. It is well in advance
> of anything Haskell can do also.

Really? What about type classes? Haskell has fmap! That's an example
of what you mean, correct?

Jonathan

Re: [Caml-list] Stdlib

[skaller]

On Tue, 2005-11-01 at 13:11 +1300, Jonathan Roewen wrote:

> > All of this can be done (I worked on a system that did it),
> > however it is definitely non-trivial. It is well in advance
> > of anything Haskell can do also.
> 
> Really? 

Really. It is in some sense the Holy Grail of programming
language design. Ocaml doesn't even support higher order
polymorphism -- you cannot pass a polymorphic function to
a function -- when you try it gets monomorphised (yes,
it can be done by wrapping the function in a record or
using classes).

> What about type classes? Haskell has fmap! That's an example
> of what you mean, correct?

Yes, it is an example of what one would like to do,
however it is not the same. You have to provide certain
primitives, and then others are derived from them.

The problem is .. this is nominal typing. In fact, Ocaml
can do this same thing with functors, but the result
is merely a sum of all the named cases -- it isn't
abstract.

Haskell makes it easier to name the types (monadic notation)
but it isn't any more expressive than Ocaml's functors.
In fact, it is probably the other way around, its just that
instantiating all those dang functors by hand is a pain.
C++ is a breeze by comparison, since templates are instantiated
automatically.

The point is that the much vaunted 'intensional polymorphism'
in Ocaml only applies to type variables -- there are no
functor variables.

BTW: any real type theorist disgusted with my explanation is
welcome to explain it properly -- in particular why it
is THE central problem of programming theory.

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

Re: [Caml-list] Stdlib

[Brian Hurt]

On Mon, 31 Oct 2005, Jonathan Bryant wrote:

> Quick (and rather random question) about the standard library.  I
> noticed that, like the STL, many of the modules are very similar and
> implement many of the same functions (iter, map, etc.).  Unlike the STL
> or the Java Standard API, these modules are each completely
> independent.  Why hasn't there been a push to do something like
> functorize these modules?  For example: List, Array, Hashtbl, Set, and
> Map are all collections.  Couldn't you factor out something to make it
> easier to extend the library, sort of like the Java API?  Parametric
> Polymorphism handles the generics of the elements of the set, so
> couldn't the algorithms be factored out leaving three distinct parts
> (Elements, Collections of Elements, Operations on Collections), sort of
> like in the STL?

The question here is: why?  What good would factoring out the common base 
actually do?

In Java and C++, with their style of inheritance, if you don't explicitly 
factor out the common base, then you can't inherit from/manipulate the 
common base functionality.  But Ocaml does structural comparisons for 
matching, not inheritance trees.  So if you wanted to write a bit of code 
that could be used with lists, arrays, maps, etc., you could just write:

module type Collection = sig
     type 'a t
     val map : ('a -> 'b) -> 'a t -> 'b t
end;;

module MyCode(Col: Collection) = struct
     ...
end;;

OK, you have to hack a little bit because list.mli and array.mli don't 
explicitly define the 'a t type.  But they could.  And going:

module MyListCode =
     MyCode(struct type 'a t = 'a list let map = List.map end)
;;

isn't that big a deal.  But the important point is that this still works, 
even if the common functionality you want to depend upon isn't explicitly 
factored out.  A similiar stunt can be done with objects.

The other reason to do this is to factor out the common code.  But there 
isn't that much code to share among the various maps, iters, and folds. 
Well, a little bit of shared code between Map and Set (and see the Pagoda 
Core Foundation code for an example of how they could share code), but 
that's about it.

I suppose you could convert every ordered collection into either an 
iterator of some sort or a lazy list, and then map/fold/iter on that and 
while this sort of functionality is usefull in general (and I'd like to 
see it added to the standard library), there are generally usefull 
optimizations that can be applied.  For example, if I'm mapping a Map to 
another Map, I know the new tree will have the same shape as the old 
tree.  And so on.  This sort of optimization would be lost going through 
iterator or lazy list.

Brian

Stdlib

[Jonathan Bryant]

Wow, guys.  Thanks for the responses.  That really cleared up my
question :).  I (unfortunately) have to learn some of the STL for
another project and the thought occurred to me.

On another note, I would love to do this other project in OCaml, but it
is OpenGL intensive (read: based) and LablGL drives me nuts.  The named
argument thing drives me up the wall because it's more information that
I don't want to have to learn and internalize.  If the author of that
package reads this list, then I apologize.  You've done a fantastic job
of mapping the API, but I really do not like the OCaml syntax for both
Labeled and Optional arguments in general.  Does anyone know of an
OpenGL package that is /complete/ and /not/ labeled?  There is, of
course, the option of writing a module/set of modules that use the
existing C stubs an are not labled, but that would be a last-ditch
effort.

Thanks!

--Jonathan Bryant
  jtbryant@valdosta.edu
  Student Intern
  Unix System Operations
  VSU Information Technology

"Das Leben ohne Music ist einfach ein Irrtum, eine Strapaze, ein" Exil."
("Life without music is simply an error, a pain, an exile.")
--Frederich Nietzsche

"The three cardinal values of a programmer are laziness, impatience, and
hubris."
--Perl Man Page