Which Algebraic Pattern fits this type of tree?

Question

I've got a puzzle for you,

I managed to write some code that would do these things using recursion-schemes, but it's incredibly messy and that usually means that I missed a useful abstraction somewhere.

I'm designing a layout system for my text editor Rasa; It uses splits in a very similar manner as Vim. I decided to describe the splits using a Tree; you can imagine it as a binary tree of either vertical or horizontal splits with 'Views' at the leaf nodes. This picture might help.

Here's my initial data structure:

data Direction = Hor | Vert
data Tree a = 
  Branch Direction (Tree a) (Tree a)
  | Leaf a
  deriving (Functor)

Some of the operations I need are:

• split :: (View -> Tree View) -> Tree View -> Tree View Which splits nodes (or not) into two nodes horizontally or vertically (while maintaining their position in the tree)
• close :: (View -> Bool) -> Tree View -> Tree View which 'closes' any views which match the predicate by removing them from the tree and re-organizing adjacent views properly.
• fmap; I'd like the tree to be a functor so I can alter the views.

Some nice to have features: - focusRight :: Tree View -> Tree View, Sets a View to be active if and only if the nearest horizontally joined view to the left WAS active

I'm looking for an abstraction or set of abstractions which would provide this functionality in a clean way. Here's my thought process so far:

At first I thought I had a Monoid, The identity was the empty tree, and mappend would just attach another branch to the tree, but this doesn't work since I have two operations: vertical append and horizontal append and the operations aren't associative when they're mixed together.

Next I thought 'Some of my operations depend on their context' so I probably have a Comonad. The version of the tree I have doesn't work as a co-monad because I don't have a value to extract on a Branch, so I restructured my tree like this:

data Tree a = Node Direction [Tree a] a [Tree a]
    deriving (Functor)

but this still didn't handle the case of 'splitting' a node based on what was inside it, this matched the signature (View -> Tree View) -> Tree View -> Tree View, which unifies with bind from Monad, so maybe I had a monad? I can implement monad for the original Tree definition, but can't figure it out for my Comonad tree version.

Is there a way I can get the best of both worlds here? Am I digging up the wrong tree with Comonad/Monad? Basically I'm looking for an elegant way to model these functions over my data-structure. Thanks!

If you want to see the full code, the functions are here and the current tree is here.

Answer 1

I gave up trying to cram this into a comment. Conor McBride has a whole talk and, with Sam Lindley, a big chunk of a paper, all about using monads to carve up 2D space. Since you asked for an elegant solution I feel compelled to give you a potted summary of their work, although I wouldn't necessarily advise building this into your codebase - I suspect it's probably simpler just to work with a library like boxes and hand-crank the cutting and resizing logic with manual error handling.

---

Your first Tree is a step in the right direction. We can write a Monad instance to graft trees together:

instance Monad Tree where
    return = Leaf
    Leaf x >>= f = f x
    Branch d l r >>= f = Branch d (l >>= f) (r >>= f)

Tree's join takes a tree with trees at its leaves and lets you walk all the way to the bottom without stopping for breath half way down. It may be helpful to think of Tree as a free monad, as @danidiaz has shown in an answer. Or Kmett might say that you have a very simple syntax permitting term substitution whose Var is called Leaf.

Anyway, the point is you can use >>= to grow trees by progressively chopping up their leaves. Here I have a one-dimensional UI (let's forget about Direction for the moment) with a single window containing a String, and by repeatedly cutting it in half I end up with eight smaller windows.

halve :: [a] -> Tree [a]
halve xs = let (l, r) = splitAt (length xs `div` 2) xs
         in Node (Leaf l) (Leaf r)

ghci> let myT = Leaf "completeshambles"
-- |completeshambles|
ghci> myT >>= halve
Node (Leaf "complete") (Leaf "shambles")
-- |complete|shambles|
ghci> myT >>= halve >>= halve
Node (Node (Leaf "comp") (Leaf "lete")) (Node (Leaf "sham") (Leaf "bles"))
-- |comp|lete|sham|bles|
ghci> myT >>= halve >>= halve >>= halve
Node (Node (Node (Leaf "co") (Leaf "mp")) (Node (Leaf "le") (Leaf "te"))) (Node (Node (Leaf "sh") (Leaf "am")) (Node (Leaf "bl") (Leaf "es")))
-- |co|mp|le|te|sh|am|bl|es|

(In real life you'd probably only be cutting up one window at a time, by checking its ID inside your binding function and returning it unchanged if it's not the one you're looking for.)

The problem is, Tree has no understanding of the fact that physical space is a limited and precious resource. fmap lets you replace as with bs, but the resulting structure won't fit on the screen if the bs take up more space than the as did!

ghci> fmap ("in" ++) myT
Leaf "incompleteshambles"

This gets more serious in two dimensions, because boxes can push each other around and tear. If the middle window gets accidentally resized, I either get a misshapen box or a hole in the middle (depending on whereabouts in the tree it was).

+-+-+-+         +-+-+-+            +-+-+  +-+
| | | |         | | | |            | | |  | |
+-+-+-+         +-+-+-++-+   or,   +-+-+--+-+
| | | |  ---->  | |    | | perhaps | |    | |
+-+-+-+         +-+-+-++-+         +-+-+--+-+
| | | |         | | | |            | | |  | |
+-+-+-+         +-+-+-+            +-+-+  +-+

Expanding a window is a perfectly reasonable thing to want to do, but in the real world the space it expands into has to come from somewhere. You can't grow one window without shrinking another, and vice versa. This is not the sort of operation which can be done with >>=, which performs local substitutions at individual leaf nodes; you need to look at a window's siblings to know who's taking up the space adjacent to it.

---

So you shouldn't be allowed to use >>= to resize content like that. Lindley and McBride's idea is to teach the type checker how to snap boxes together. Using type-level natural numbers and addition,

data Nat = Z | S Nat
type family n :+ m where
    Z :+ m = m
    S n :+ m = S (n :+ m)

they work with content indexed by its width and height. (In the paper they use 2D matrices represented as vectors of vectors, but for efficiency you may want to use an array with a phantom type measuring its size.)

a, Box a :: (Nat, Nat) -> *
-- so Box :: ((Nat, Nat) -> *) -> (Nat, Nat) -> *

Placing two boxes side by side using Hor requires that they have the same height, and placing them above each other with Ver requires that they have the same width.

data Box a wh where
    Content :: a '(w, h) -> Box a '(w, h)
    Hor :: Box a '(w1, h) -> Box a '(w2, h) -> Box a '(w1 :+ w2, h)
    Ver :: Box a '(w, h1) -> Box a '(w, h2) -> Box a '(w, h1 :+ h2)

Now we're ready to build a monad to graft together these trees. The semantics of return haven't changed - it puts a 2D object in a Box on its own.

return :: a wh -> Box a wh
return = Content

Now let's think about >>=. In general a box is made up of a number of pieces of Content of varying size, composed somehow to produce a larger box. Below I have three pieces of content sized 2x1, 2x2 and 1x3 making up a 3x3 box. This box will look something like Hor (Ver (Content 2x1) (Content 2x2)) Content 1x3.

 2x1
+--+-+
|  | |
+--+ |1x3
|  | |
|  | |
+--+-+
 2x2

While you, the caller of >>=, know the outer measurements of your box, you don't know the dimensions of the individual pieces of content that make it up. How can you be expected to preserve the size of the content when you cut it up with >>=? You'll have to write a function which preserves the size without a priori knowledge of what the size was.

So >>= takes a Box of a known size wh, takes it apart to find the content, processes it with a function which preserves the (unknown) size of the content you give it*, and puts it back together to produce a new box with the same size wh. Note the rank-2 type, reflecting the fact that the caller of >>= has no control over the dimensions of content the continuation will be called with.

(>>=) :: Box a wh -> (forall wh2. a wh2 -> Box b wh2) -> Box b wh
Content x >>= f = f x
Hor l r >>= f = Hor (l >>= f) (r >>= f)
Ver t b >>= f = Ver (t >>= f) (b >>= f)

If you use a type synonym ~> for index-preserving functions and flip the arguments, you get something which looks just like =<< for regular Monads, but with a different kind of arrow. Kleisli composition also comes out looking quite pretty.

type a ~> b = forall x. a x -> b x

return :: a ~> Box a
(=<<) :: (a ~> Box b) -> (Box a ~> Box b)
(>=>) :: (a ~> Box b) -> (b ~> Box c) -> (a ~> Box c)

So that's monads over indexed sets. (More in Kleisli Arrows of Outrageous Fortune.) In the paper they build a bunch more infrastructure to support cropping and rearranging boxes, which would probably be useful to you building a UI. For efficiency you might also decide to track the currently focused window using a zipper, which is a fun exercise. Incidentally I think Hasochism is a great introduction to fancy types in general, not just as a solution to this particular problem.

^{*Assuming that a's index is indeed an accurate measure of its physical size}