Edit: The original question was "tying the knot with a comonad", but what really helped here is a two-dimensional knot tying with U2Graph from cirdec. Original question (until Anwser):
I want to tie the knot with data that originates from a comonad
data U a = U [a] a [a]
into a richer data structure
data FullCell = FullCell {
vision :: [[Int]],
move :: Int -> Maybe FullCell -- tie the knot here!
}
with a function
tieKnot :: U Int -> U FullCell
However, my brain encounters an "occurs check" when I try to fill in for undefined:
tieKnot :: U Int -> U FullCell
tieKnot u = u =>> (\z -> FullCell {
vision = limitTo5x5 z,
move = move'
}) where
move' 1 = Just undefined -- tie the knot to neighbor here
move' (-1) = Just undefined -- ...
move' _ = Nothing
limitTo5x5 = undefined -- not of interest, but the cause why a comonad is used
The problem I cannot solve is, I need to refer to something I am just constructing, and it is buried deep in a comonad. And I want to be really sure that circles actually point to the same thunk.
What is the best way to solve it? Is that comonad U a the way to go? A doubly linked list data T a = T (Maybe (T a)) a (Maybe (T a)) seems to run into the same problem, but will be much harder to extend to 2 dimensions.
Background: I try to implement codegolf's rat race in haskell. So with tying-the-know I want to refer to the same thunk owing the time-consuming computation.
The solution comes from Cirdec's Answer. It is just missing a small step that I do not want to squeeze into a comment.
What caused my brain to run into an "occurs check" is: To construct a FullCell and tie the knot on its field move I need the already constructed U2Graph FullCell. Now that I stated it, the requirement is easy to write as:
toU2Graph :: (U2Graph b -> a -> b) -> U2 a -> U2Graph b
where the first argument is a function that constructs my FullCell. Cirdec's function can be adapted easily. The final step is to bring the comonad back in:
toU2GraphW :: (U2Graph b -> U2 a -> b) -> U2 a -> U2Graph b
toU2GraphW f u = toU2Graph f (duplicate u)
It's possible to build a graph from a zipper so that moving around on the graph doesn't require allocating new memory. This can be a performance improvement if you are going to hold on to multiple pointers into the structure.
We'll start with the zipper for lists.
data U a = U [a] a [a]
The corresponding graph holds references to the nodes to the left and right, if they exist.
data UGraph a = UGraph {
_left :: Maybe (UGraph a),
_here :: a,
_right :: Maybe (UGraph a)
}
Any instances of this structure should obey the following laws, which say that going one direction and then back the other brings you back to where you started.
_right >=> _left == \x -> (_right >=> const (return x)) x
_left >=> _right == \x -> (_left >=> const (return x)) x
The UGraph data type doesn't enforce this, so it would be wise to put it in a module and not export the UGraph constructor.
To convert a zipper to a graph we start in the middle and work our way out both sides. We tie recursive knots between the already built portion of the graph and the parts of the graph that haven't already been built.
toUGraph :: U a -> UGraph a
toUGraph (U ls h rs) = g
where
g = UGraph (build ugraph' g ls) h (build UGraph g rs)
ugraph' r h l = UGraph l h r
build _ _ [] = Nothing
build f prev (here:next) = Just g
where
g = f (Just prev) here (build f g next)
Combined with my other answer, you can build a graph of the visible portions of your U Int with
tieKnot :: U Int -> UGraph [[Int]]
tieKnot = toUGraph . extend limitTo5x5
Ultimately you want to build a 2d field. Building a graph like we did for the one dimensional list zipper in two dimensions is much trickier, and in general will require forcing O(n^2) memory to traverse arbitrary paths of length n.
You plan on using the two-dimensional list zipper Dan Piponi described, so we'll reproduce it here.
data U2 a = U2 (U (U a))
We might be tempted to make a graph for U2 that's a straight up analog
data U2Graph a = U2Graph (UGraph (UGraph a))
This has a fairly complicated structure. Instead, we're going to do something much simpler. A node of the graph corresponding to U2 will hold references to adjacent nodes in each of the four cardinal directions, if those nodes exist.
data U2Graph a = U2Graph {
_down2 :: Maybe (U2Graph a),
_left2 :: Maybe (U2Graph a),
_here2 :: a,
_right2 :: Maybe (U2Graph a),
_up2 :: Maybe (U2Graph a)
}
Instances of U2Graph should obey the same bidirectional iterator laws we defined for UGraph. Once again, the structure doesn't enforce these laws itself, so the U2Graph constructor probably shouldn't be exposed.
_right2 >=> _left2 == \x -> (_right2 >=> const (return x)) x
_left2 >=> _right2 == \x -> (_left2 >=> const (return x)) x
_up2 >=> _down2 == \x -> (_up2 >=> const (return x)) x
_down2 >=> _up2 == \x -> (_down2 >=> const (return x)) x
Before we convert a U2 a to a U2Graph a, let's take a look at the structure of a U2 a. I'm going to assign the outer list to be the left-right direction and the inner list to be the up-down direction. A U2 has a spine going all the way across the data, with the focal point anywhere along the spine. Each sublist can be slid perpendicular to the spine so that it is focusing on a specific point on the sublist. A U2 in the middle of use might look like the folloing. The +s are the outer spine, the vertical dashes | are the inner spines, and * is the focal point of the structure.
|
||
||| ||
|||| |||| |
+++*++++++++
|||||| ||
||||
||
Each of the inner spines is continuous - it can't have a gap. That means that if we are considering a location off the spine, it can only have a neighbor to the left or right if the location one closer to the spine also had a neighbor on that side. This gives rise to how we will build a U2Graph. We will build connections to the left and right along the outer spine, with recursive references back towards the focal point just like we did in toUGraph. We will build connections up and down along the inner spines, with recursive references back towards the spine, just like we did in toUGraph. To build the connections to the left and right from a node on an inner spine we'll move one step closer to the outer spine, move sideways at that node, and then move one step farther away from the outer spine on the adjacent inner spine.
toU2Graph :: U2 a -> U2Graph a
toU2Graph (U2 (U ls (U ds h us) rs)) = g
where
g = U2Graph (build u2down g ds) (build u2left g ls) h (build u2right g rs) (build u2up g us)
build f _ [] = Nothing
build f prev (here:next) = Just g
where
g = f (Just prev) here (build f g next)
u2up d h u = U2Graph d (d >>= _left2 >>= _up2 ) h (d >>= _right2 >>= _up2 ) u
u2down u h d = U2Graph d (u >>= _left2 >>= _down2) h (u >>= _right2 >>= _down2) u
u2left r (U ds h us) l = g
where
g = U2Graph (build u2down g ds) l h r (build u2up g us)
u2right l (U ds h us) r = g
where
g = U2Graph (build u2down g ds) l h r (build u2up g us)