Generalise methods on Zipper with different types for current element and left/right lists
题
I'm toying around with zippers, where the current element can have a different type than the left and right lists:
data Z a b = Z ([a], b, [a])
One can navigate the zipper with moveLeft
and moveRight
:
moveLeft :: (b -> a -> a) -> (a -> b -> b) -> Z a b -> Z a b
moveLeft listF currentF (Z (x:xs, c, ys)) = Z (xs, g x c, ((f c x):ys))
moveRight :: (b -> a -> a) -> (a -> b -> b) -> Z a b -> Z a b
moveRight listF currentF (Z (xs, c, y:ys)) = Z (((f c y):xs), g y c, ys)
Here, listF
transforms a list element and the current one into a list element to the left or right. currentF
transforms the current element and a list element into the current element.
If both the current and the list type are equal, moving is simple:
moveLeftSameType :: Z a a -> Z a a
moveLeftSameType = moveLeft const const
and everything works as expected, nice!
What I'd like to do now is to generalize the above idea, such that by only implementing the listF
and currentF
functions for a given Z a b
(say a :: Char
, b :: Int
), moveLeft
and moveRight
do the right thing automagically. What would be the correct way to do this?
Remark
I have tried to implement a class like this:
class CPos a where
listF :: c -> d -> d
currentF :: d -> c -> c
moveLeft :: a -> a
moveRight :: a -> a
where moveLeft/Right
are implemented in terms of listF
and currentF
, but this fails with
The class method `listF' mentions none of the type variables of the class CPos a
Remark 2
Something I don't like about the above idea in general is the fact that be allowing arbitrary functions listF
and currentF
it's impossible to guarantee
moveLeft . moveRight = id
(if the zipper is within the list, on the borders this doesn't hold anyways). Any hints to enforce this?
解决方案
Here is a solution to that.
class CPos a b where
listF :: b -> a -> a
currentF :: a -> b -> b
moveLeft :: Z a b -> Z a b
moveLeft (Z (x:xs, c, ys)) = Z (xs, currentF x c, ((listF c x):ys))
moveRight :: Z a b -> Z a b
moveRight (Z (xs, c, y:ys)) = Z (((listF c y):xs), currentF y c, ys)
I don't think you can enforce moveLeft . moveRight = id
. I mean it is undecidable to guarantee two functions are equal. The best you can do is to write quickcheck
testcases to guarantee the same.