Re: [Haskell-cafe] adding the elements of two lists

From: "Richard O'Keefe" Date: Thu, 29 Mar 2012 16:34:46 +1300

On 29/03/2012, at 3:08 PM, Doug McIlroy wrote:

...

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

Try it again.

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

u f (PS x) = PS $ map f x b f (PS x) (PS y) = PS $ zipWith f x y to_ps x = PS (x : repeat 0)

ps_product (f:fs) (g:gs) = whatever

instance Num a => Num (PS a) where (+) = b (+) (-) = b (-) (*) = b ps_product negate = u negate abs = u abs signum = u signum fromInteger = to_ps . fromInteger

I've avoided defining ps_product because I'm not sure what it is supposed to do: the definition doesn't look commutative.

You have given the Hadamard product--a construction with somewhat esoteric properties. The product I have in mind is the ordinary mathematical product that one meets in freshman calculus. The distributive law yields this symmetric formulation (f:fs) * (g:gs) = f*g : (toSeries f)*gs + fs*(toSeries g) + (0 : fs*gs) The version I gave is an optimization (which I learned from Jerzy). For more explanation see www.cs.dartmouth.edu/~doug/powser.html. I like the lifting functions b and u, but they don't get one very far. The product is where the PS pox begins to bite badly. I would welcome a perspicuous formulation of that using newtype. Incidentally, a more efficient way to write the symmetric product is (f:fs) * (g:gs) = f*g : zipWith (f*) gs + zipWith fs (*g) + (0 : fs*gs) toSeries and zipWith appear in the formulas because Haskell overloading won't let one use the multiplication symbol for both series*series and scalar*series. One might also invent a distinct operator for the purpose. Coercion with toSeries strikes me as the least jarring of these approaches. zipWith suffers from mixing levels of abstraction--it signifies not the idea of multiplication, but the algorithm. A new operator would suffer both from unfamiliarity and lack of commutativity.

...

The code suffers a pox of PS.

But it doesn't *need* to.