Mark Jason Dominus: Why I never finish my Haskell programs (part 1 of ∞)
source link: https://www.tuicool.com/articles/hit/6zm6raU
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Mon, 03 Sep 2018
Why I never finish my Haskell programs (part 1 of ∞)
Whenever I try to program in Haskell, the same thing always goes wrong. Here is an example.
I am writing a module to operate on polynomials. The polynomial !!x^3 - 3x + 1!! is represented as
Poly [1, -3, 0, 1]
I want to add two polynomials. To do this I just add the corresponding coefficients, so it's just
(Poly a) + (Poly b) = Poly $ zipWith (+) a b
Except no, that's wrong, because it stops too soon. When the lists
are different lengths, zipWith
discards the extra, so for example it
says that !!(x^2 + x + 1) + (2x + 2) = 3x + 3!!, because it has
discarded the extra !!x^2!! term. But I want it to keep the extra, as
if the short list was extended with enough zeroes. This would be a
correct implementation:
(Poly a) + (Poly b) = Poly $ addup a b where addup [] b = b addup a [] = a addup (a:as) (b:bs) = (a+b):(addup as bs)
and I can write this off the top of my head.
But do I? No, this is where things go off the rails. “I ought to be
able to generalize this,” I say. “I can define a function like zipWith
that is defined over any Monoid
, it will combine the
elements pairwise with mplus
, and when one of the lists
runs out, it will pretend that that one has some mempty
s stuck on the
end.” Here I am thinking of something like ffff :: Monoid a => [a] ->
[a] -> [a]
, and then the (+)
above would just be
(Poly a) + (Poly b) = Poly (ffff a b)
as long as there is a suitable Monoid
instance for the a
s and b
s.
I could write ffff
in two minutes, but instead I spend fifteen
minutes looking around in Hoogle to see if there is already an ffff
,
and I find mzip
, and waste time being confused by mzip
, until I
notice that I was only confused because mzip
is for Monad
, not
for Monoid
, and is not what I wanted at all.
So do I write ffff
and get on with my life? No, I'm still not done.
It gets worse. “I ought to be able to generalize this,” I say. “It
makes sense not just for lists, but for any Traversable
… Hmm, or
does it?” Then I start thinking about trees and how it should decide
when to recurse and when to give up and use mempty
, and then I start
thinking about the Maybe
version of it.
Then I open a new file and start writing
mzip :: (Traversable f, Monoid a) => f a -> f a -> f a mzip as bs = …
And I go father and farther down the rabbit hole and I never come back
to what I was actually working on. Maybe the next step in this
descent into madness is that I start thinking about how to perform
unification of arbitrary algebraic data structures, I abandon mzip
and open a new file for defining class Unifiable
…
Actually when I try to program in Haskell there a lot of things that go wrong and this is only one of them, but it seems like this one might be more amenable to a quick fix than some of the other things.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK