Why I never finish my Haskell programs (part 3 of ∞)
(Previously:
[1]
[2])
I'm doing more work on matrix functions. A matrix represents a
relation, and I am representing a matrix as a [[Integer]] . Then
matrix addition is simply liftA2 (liftA2 (+)) . Except no, that's
not right, and this is not a complaint, it's certainly my mistake.
The overloading for liftA2 for lists does not do what I want, which
is to apply the operation to each pair of correponding elements. I want
liftA2 (+) [1,2,3] [10,20,30] to be [11,22,33] but it is not.
Instead liftA2 lifts an operation to apply to each possible pair of
elements, producing [11,21,31,12,22,32,13,23,33] .
And the twicelifted version is
similarly not what I want:
$$
\require{enclose}
\begin{pmatrix}1&2\\3&4\end{pmatrix}\enclose{circle}{\oplus}
\begin{pmatrix}10&20\\30&40\end{pmatrix}=
\begin{pmatrix}
11 & 21 & 12 & 22 \\
31 & 41 & 32 & 42 \\
13 & 23 & 14 & 24 \\
33 & 43 & 34 & 44
\end{pmatrix}
$$
No problem, this is what ZipList is for. ZipLists are just regular
lists that have a label on them that advises liftA2 to lift an
operation to the elementbyelement version I want instead of the
eachonebyeveryotherone version that is the default. For instance
liftA2 (+) (ZipList [1,2,3]) (ZipList [10,20,30])
gives ZipList [11,22,33] , as desired. The getZipList function
turns a ZipList back into a regular list.
But my matrices are nested lists, so I need to apply the ZipList
marker twice, once to the outer list, and once to each of the inner
lists, because I want the elementbyelement behavior at both
levels. That's easy enough:
matrix :: [[a]] > ZipList (ZipList a)
matrix m = ZipList (fmap ZipList m)
(The fmap here is actually being specialized to map , but that's
okay.)
Now
(liftA2 . liftA2) (+) (matrix [[1,2],[3,4]]) (matrix [[10,20],[30, 40]])
does indeed produce the result I want, except that the type markers
are still in there: instead of
[[11,22],[33,44]]
I get
ZipList [ ZipList [11, 22], ZipList [33, 44] ]
No problem, I'll just use getZipList to turn them back again:
unmatrix :: ZipList (ZipList a) > [[a]]
unmatrix m = getZipList (fmap getZipList m)
And now matrix addition is finished:
matrixplus :: [[a]] > [[a]] > [[a]]
matrixplus m n = unmatrix $ (liftA2 . liftA2) (+) (matrix m) (matrix n)
This works perfectly.
But the matrix and unmatrix pair bugs me a little. This business
of changing labels at both levels has happened twice already and
I am likely to need it again. So I will turn the two functions
into a single higherorder function by abstracting over ZipList .
This turns this
matrix m = ZipList (fmap ZipList m)
into this:
twice zl m = zl (fmap zl m)
with the idea that I will now have matrix = twice ZipList and
unmatrix = twice getZipList .
The first sign that something is going wrong is that twice does not
have the type I wanted. It is:
twice :: Functor f => (f a > a) > f (f a) > a
where I was hoping for something more like this:
twice :: (Functor f, Functor g) => (f a > g a) > f (f a) > g (g a)
which is not reasonable to expect: how can Haskell be expected to
figure out I wanted two diferent functors in there when there is only one
fmap ? And indeed twice does not work; my desired matrix = twice
ZipList does not even typecheck:
<interactive>:19:7: error:
• Occurs check: cannot construct the infinite type: a ~ ZipList a
Expected type: [ZipList a] > ZipList a
Actual type: [a] > ZipList a
• In the first argument of ‘twice’, namely ‘ZipList’
In the expression: twice ZipList
In an equation for ‘matrix’: matrix = twice ZipList
• Relevant bindings include
matrix :: [[ZipList a]] > ZipList a (bound at <interactive>:20:5)
Telling GHC explicitly what type I want for twice doesn't work
either, so I decide it's time to go to lunch. w I take paper with me,
and while I am eating my roast pork hoagie with sharp provolone and
spinach (a popular local delicacy) I work out the results of the type
unification algorithm on paper for both cases to see what goes wrong.
I get the same answers that Haskell got, but I can't see where the
difference was coming from.
So now, instead of defining matrix operations, I am looking into the
type unification algorithm and trying to figure out why twice
doesn't work.
And that is yet another reason why I never finish my Haskell programs.
(“What do you mean, λabstraction didn't work?”)
[Other articles in category /prog/haskell]
permanent link
