[Haskell-cafe] adding the elements of two lists

[Doug McIlroy]

> Date: Tue, 27 Mar 2012 11:03:54 +1300
> From: "Richard O'Keefe" <ok at cs.otago.ac.nz>
> Subject: Re: [Haskell-cafe] adding the elements of two lists
> To: <jerzy.karczmarczuk at unicaen.fr>
> Cc: haskell-cafe at haskell.org
> 
> And *that* is why I stopped trying to define instance Num t => Num [t].
> If "I KNEW that the length of the lists is ... fixed ..." then the type
> wasn't *really* [t], but some abstract type that happened to be implemented
> as [t], and that abstract type deserved a newtype name of its own.
> 
> Naming the type
>  - makes the author's intent clearer to readers
>  - lets the compiler check it's used consistently
>  - lets you have instances that don't match instances for
>    other abstract types that happen to have the same implementation
>  - provides a natural place to document the purpose of the type
>  - gives you a way to enforce the intended restrictions
> all for zero run-time overhead.

Quite taken by this manifesto for high style and morality,
I resolved to do right by some old code, of which I had
been quite proud: www.cs.dartmouth.edu/~doug/powser.html.
Sadly, the exercise took some bloom off the rose. What
the code gained in honesty and safety, it lost in beauty
and readability.

Here's the contrast, seen in overloading arithmetic to
handle addition and multiplication of power series.

--------- without newtype

toSeries f = f : repeat 0   -- coerce scalar to series

instance Num a => Num [a] where
   (f:fs) + (g:gs) = f+g : fs+gs
   (f:fs') * gs@(g:gs') = f*g : fs'*gs + (toSeries f)*gs'

--------- with newtype

newtype Num a => PS a = PS [a] deriving (Show, Eq)

fromPS (PS fs) = fs         -- extract list
toPS f = PS (f : repeat 0)  -- coerce scalar to series

instance Num a => Num (PS a) where
   (PS (f:fs)) + (PS (g:gs)) = PS (f+g : fs+gs)
   (PS (f:fs)) * gPS@(PS (g:gs)) =
      PS $ f*g : fromPS ((PS fs)*gPS + (toPS f)*(PS gs))

The code suffers a pox of PS. When one goes on to
introduce efficiencies and generalize to handle
finite series (polynomials), it only gets worse.

One unpleasant technical problem: the deriving
clause is almost useless--one can't print or
detect equality of infinite objects.  For output  
one must apply something like (take 10 . fromPS).

Yet this modest package would likely pose
problems if it were combined with others in a
grander suite for automated mathematics.  What to
do? I think I might write the package without
newtype, and then wrap it in PS for export in hopes
of exploiting the advantages of both styles.