Re: [Caml-list] stl?

[Nicolas Pouillard <nicolas.pouillard@gmail.com>]

Excerpts from Brian Hurt's message of Wed Mar 04 17:14:50 +0100 2009:
> 
> 
> 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:

[...]

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

[...]

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

Haskell `newtype's is a pretty reasonable answer to this problem.

A `newtype' is a bit like a type with only one constructor of only one argument,
except that there is no runtime cost for it. However by being a *new* type one
can define different instances of type classes for it. Moreover since the
deriving feature is extended on `newtype's, retrieving all the goodness of
the wrapped type is costless (deriving newtype is easy since generally the
code justs virtually unpacks and re-packs using the constructor and call
the same functions on the wrapped value).

Examples:

\begin{code}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Data.List
import Data.Function

newtype MySet a = MkMySet { toList :: [a] } -- here toList is an accessor
                                            -- function (MySet a -> [a])
  deriving (Read,Show,Functor,Monad) -- ...

norm :: Ord a => MySet a -> [a]
norm = nub . sort . toList

instance (Ord a) => Eq (MySet a) where (==) = (==) `on` norm
instance (Ord a) => Ord (MySet a) where compare = compare `on` norm

propMySet = MkMySet [1,2,3,4] == MkMySet [1,1,2,4,3]
\end{code}

Or another one:

\begin{code}
newtype DownInt = DownInt { fromDownInt :: Int }
  deriving (Eq,Read,Show,Enum,Num)

instance Ord DownInt where compare = flip compare `on` fromDownInt
  -- same as compare x y = fromDownInt y `compare` fromDownInt x

propDownInt = DownInt 4 < DownInt 2

-- this example is contrived since sortBy would be simpler here
-- however in larger examples the benifit is clearer, for instance
-- List.sort is not in a functor in OCaml.
sortDownInt :: [Int] -> [Int]
sortDownInt = map fromDownInt . sort . map DownInt

propDownInt' = [4,3,2,1] == sortDownInt [1,2,3,4]

-- since DownInt is in the Num class (an explicit choice
-- from the definition of DownInt), literals can be
-- freely lifted to DownInt.
propDownInt'' = [4,3,2,1] == sort [(1::DownInt),2,3,4]
\end{code}

Note that one can generalize `DownInt' as `Down' and get an easy
way to reverse the order on a type.

Since that, I personally consider type-classes goodness more valuable
than functors usage that doesn't fall in that category.

All the best,

-- 
Nicolas Pouillard