Re: [Caml-list] stl?

[Brian Hurt <bhurt@spnz.org>]

On Wed, 4 Mar 2009, Peng Zang wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Wednesday 04 March 2009 01:11:18 am Brian Hurt wrote:
>> This is another large factor.  The three reasons functors aren't used very
>> much are because:
>> 1) They're a big, scary name,
>> 2) They're slightly less efficient,
>> 3) There are no good tutorials about how to use them, and
>> 4) A fanatical devotion to the pope.
>>
>> I'll come in again...
>
> Ha!  =]
>
> But I'll add one more reason.  With functors you have extra overhead like
> having to be explicit with what function you're using.  In your example when
> you want to use Newton's method you always must write "RatioNewton.newtons"
> or "FloatNewtons.newtons".  The alternative is to functorize the call site,
> but (1) that has its own cost: lots of boilerplate functorizing code crowding
> the real code and (2) you just defer the explicit naming cost as when that
> function is called you'll still have to call either Float version or Ratio
> version.

Yeah.  I think of this as one of the advantages of Functors.

Here are two real problems I've hit with type classes, in only a few weeks 
banging around in Haskell.

For example, you can't have more than one instance of a type class for any 
given type.  So let's say you want to have a type class for things that 
can be converted to and from s-expressions, like:
 	data Sexp =
 		Atom String
 		| List [ Sexp ]

 	class Sexpable a where
 		toSexp :: a -> Sexp
 		fromSexp :: Sexp -> Maybe a

So then you start throwing out the standard instances, among others, you 
do one for string:
 	instance Sexpable String where
 		toSexp s = Atom s
 		fromSexp (Atom s) = Just s
 		fromSexp _ = Nothing

and, a little while later, one for generic lists:
 	instance Sexpable a => Sexpable [ a ] where
 		toSexp xs = List $ map toSexp xs
 		fromSexp (List xs) = mapM fromSexp xs
 		fromSexp _ = Nothing

Opps!  Now you have conflicting instances for type String- one the 
explicit implementation, and one via the generic list.  There are kludges 
to get around this, but they cause their own problems (Brian's first law 
of programming: kludges multiply).  A common one is to add the function 
toSexpList and fromSexpList to the fundamental type class, and drop the 
generic list implementation.  Except now you can't simply toSexp a value 
of type Map Int ([Int], Foo) despite the fact that Maps, Ints, Foos, and 
tuples all have toSexp defined over them- that list in there says that you 
have to pick things apart by hand, so you can call toSexpList instead of 
toSexp at the right point.

Here's another example, slightly translated.  Newton's method is actually 
a very widely applicable algorithm.  There is a variant of it, called 
Newton-Kantorovich, which solves systems of non-linear equations. 
Basically, the function f has type vector -> vector, with it's inputs the 
current values of all the variables used by all the equations (as a 
vector), and it's output the computed values of all the equations (as a 
vector).  The derivative of this function, f', has the type vector -> 
matrix, the input being the current values of all the variables, and the 
output being the matrix of partial derivatives.  Basically, the element at 
row i, column j of the matrix is the old fasioned, single-variable 
derivitive of equation i, assuming that all variables except variable j 
are constants (with their current value).  Then, instead of just doing x' 
= x - (f x)/(f' x), we first solve for (f' x)*y = f x for y, which is just 
your standard linear algebra solve Ax = b for x problem.  You can then 
calculate x' = x - y using standard vector subtraction.

But when you try to implement this, you realize that you have not one, but 
three (arguably four), different types all co-variant.  You have the type 
of x, which is a vector (and arguable the different type of f x, which can 
be a different size of vector- is the vector length an aspect of it's type 
or not?), the type of the differential (matrix, in this case), and the 
type of the norm of x, which is generally a real of some sort.  In my 
original example, I assumed that all three of these were the same type- 
but I may not want to.  And actually, you start wanting to split some of 
the various types off earlier- for example, if your function uses 
complexes or quaterions, the type of the values and the types of the 
derivitives may be the same, but you may want a different type (a real 
number type) for the norm.

Now, I comment you *can* do this in Haskell- using GHC specific 
extensions.  But you don't need fancy extensions (which cause problems in 
the type checker, if I understand things correctly) to do this, quite 
easily, with functors.

>
> I think objects are much closer to type classes and a much nicer solution.
> You can write:

If only Ocaml implemented objects!

Oh, wait.  Never mind.

Brian