Sunday, December 17, 2006

Questions on Haskell Style (and Polynomials redux)

Someone posted, on the Haskell "Blow your Mind" page, a much more concise implementation of Polynomials as Numbers than I managed to come up with. There are a couple things I learned by comparing it with my version:

  • Use of zipWith (+) instead of map (\v -> (fst v + snd v)) zip; obviously I need to get to know the libraries better
  • zipWith' is introduced to zipWith two lists together, padding the shortest one with zeroes. Jeremy Gibbons suggested the same thing, calling it longzipwith, and this is parallel to what I did without the "with" in my zipLong function.
  • They had the same questions I did about what to do with the required signum and abs functions. Mikael suggested in a comment that I should use the NumericPrelude library instead of the standard one, for a more sensible generic definition of a number.
  • Jeremy and Blow-your-mind both used one less line in their zip function definition than I did: they manage to define it without explicitly handling the case where both lists are null.
And here are some questions I have -- please comment if you have any ideas!
  • The Blow-your-mind version uses [a] instead of Poly [a] as its polynomial type. My feeling is that an explicit constructor and data type like Poly is better, because a polynomial is not the most obvious way to interpret a list of numbers. However, my functions ended up being a lot wordier, pulling that constructor on and off the list all the time. What's the better style choice here?
  • The multiplication function has me scratching my head. It seems terser, but less communicative to me. If you're got more experience with functional programming than I do: is the Blow-your-mind version much more clear or efficient, and is it worth it? Is mine only clearer to me because I'm not used to FP style yet? Or maybe tight APL-like gnomishness is part of the point of the Blow-your-mind page. (Here they are again if you don't want to follow all the links).
My version:
> scalarPolyMult :: (Floating a) => a -> Poly a -> Poly a
> scalarPolyMult c (Poly rs) = Poly $ map (*c) rs

> multByUnknown (Poly rs) = Poly (0:rs)

> multPoly :: (Floating a) => (Poly a) -> (Poly a) -> (Poly a)
> multPoly (Poly []) cs = Poly []
> multPoly (Poly (b:bs)) cs =
> addPoly
> (scalarPolyMult b cs)
> (multPoly (Poly bs) (multByUnknown cs))
Blow-your-mind version:
  xs * ys = foldl1 (+) (padZeros partialProducts)
partialProducts = map (\x -> [x*y | y <- ys]) xs
padZeros = map (\(z,zs) -> replicate z 0 ++ zs) . (zip [0..])


Doug McIlroy said...

For a classic and beautiful way to handle polynomials (and power series) see my comment on the blow-your-mind version:

Chris Bogart said...

That last link should be
and it's truly beautiful.