Какой алгебраический шаблон соответствует этому типу дерева?

Я бросил попытки втиснуть это в комментарий. Конор Макбрайд имеет целый разговор и, с Сэмом Линдли, большой кусок бумага, все об использовании монад для разделения 2D-пространства. Поскольку вы попросили элегантное решение, я чувствую себя обязанным дать вам краткое изложение их работы, хотя я бы не обязательно советовал встраивать это в вашу кодовую базу - я подозреваю, что, вероятно, проще просто работать с библиотекой, такой как boxes и настройте логику обрезки и изменения размера с помощью ручной обработки ошибок.

Ваш первый Tree — это шаг в правильном направлении. Мы можем написать экземпляр Monad для прививки деревьев вместе:

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 берет дерево с деревьями на его листьях и позволяет пройти весь путь до самого дна, не останавливаясь на полпути вниз. Может быть полезно думать о Tree как о бесплатная монада, как показал @danidiaz в ответе. Или Кметт может сказать, что у вас очень простой синтаксис, позволяющий подставлять термины, Var которых называется Leaf.

В любом случае, суть в том, что вы можете использовать >>= для выращивания деревьев, постепенно обрезая их листья. Здесь у меня есть одномерный пользовательский интерфейс (давайте пока забудем о Direction) с одним окном, содержащим String, и, многократно разрезая его пополам, я получаю восемь окон меньшего размера.

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|

(В реальной жизни вы, вероятно, вырезаете только одно окно за раз, проверяя его идентификатор внутри вашей функции привязки и возвращая его без изменений, если это не то, что вы ищете.)

Проблема в том, что Tree не понимает того факта, что физическое пространство является ограниченным и ценным ресурсом. fmap позволяет заменить a на b, но полученная структура не поместится на экране, если b будут занимать больше места, чем a!

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

Это становится более серьезным в двух измерениях, потому что коробки могут толкать друг друга и рваться. Если размер среднего окна случайно изменяется, я получаю либо коробку деформированной формы, либо дыру в середине (в зависимости от того, где она находилась в дереве).

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

Расширение окна — вполне разумная вещь, но в реальном мире пространство, в которое оно расширяется, должно откуда-то браться. Вы не можете увеличить одно окно, не сжав другое, и наоборот. Это не та операция, которую можно выполнить с помощью >>=, выполняющего локальные замены в отдельных листовых узлах; вам нужно посмотреть на братьев и сестер окна, чтобы узнать, кто занимает пространство, прилегающее к нему.

Таким образом, вам не должно быть разрешено использовать >>= для изменения размера контента. Идея Линдли и Макбрайда состоит в том, чтобы научить специалистов по проверке шрифтов соединять коробки вместе. Используя натуральные числа на уровне типов и сложение,

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

они работают с контентом, проиндексированным по его ширине и высоте. (В статье используются двумерные матрицы, представленные в виде векторов векторов, но для эффективности вы можете использовать массив с фантомным типом, измеряющим его размер.)

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

Для размещения двух блоков рядом с помощью Hor требуется, чтобы они имели одинаковую высоту, а для размещения их друг над другом с помощью Ver требуется, чтобы они имели одинаковую ширину.

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)

Теперь мы готовы построить монаду для склеивания этих деревьев. Семантика return не изменилась — он сам помещает 2D-объект в Box.

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

Теперь давайте подумаем о >>=. Как правило, коробка состоит из нескольких частей Content разного размера, составленных таким образом, чтобы получилась большая коробка. Ниже у меня есть три фрагмента контента размером 2x1, 2x2 и 1x3, составляющие блок 3x3. Это поле будет выглядеть примерно так: Hor (Ver (Content 2x1) (Content 2x2)) Content 1x3.

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

Хотя вы, абонент >>=, знаете внешние размеры своей коробки, вы не знаете размеров отдельных частей содержимого, из которых она состоит. Как вы можете ожидать сохранения размера содержимого, когда вы вырезаете его с помощью >>=? Вам придется написать функцию, которая сохраняет размер без априорного знания о том, каков был размер.

Итак, >>= берет Box известного размера wh, разбирает его на части, чтобы найти содержимое, обрабатывает его с помощью функции, которая сохраняет (неизвестный) размер содержимого, которое вы ему даете*, и собирает его обратно, чтобы создать новую коробку с тот же размер wh. Обратите внимание на тип ранга 2, отражающий тот факт, что вызывающая сторона >>= не имеет контроля над размерами содержимого, с которым будет вызываться продолжение.

(>>=) :: 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)

Если вы используете синоним типа ~> для функций, сохраняющих индекс, и переворачиваете аргументы, вы получаете что-то похожее на =<< для обычных Monad, но со стрелкой другого типа. Композиция Клейсли тоже выглядит весьма симпатично.

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)

Так что это монады над индексированными наборами. (Подробнее читайте в Kleisli Arrows of Outrageous Fortune< /a>.) В бумаге они создают еще куча инфраструктуры для поддержки обрезки и перестановки блоков, что, вероятно, будет полезно для создания пользовательского интерфейса. Для повышения эффективности вы также можете решить отслеживать текущее окно с помощью застежка-молния, что является забавным упражнением. Между прочим, я думаю, что Hasochism — отличное введение в причудливые типы в целом, а не только как решение этой конкретной проблемы.

^{*Если предположить, что индекс a действительно является точным показателем его физического размера}

Я бы представил ваш тип как монаду и использовал бы >>= для обработки split.

{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free

data Direction = Hor | Vert

data TreeF a = TreeF Direction a a deriving Functor

type Tree a = Free TreeF a

Что касается close, я бы, вероятно, использовал cata или para из recursion-schemes, поскольку close, по-видимому, работает снизу вверх и требует максимум знаний о родительских узлах и родственных узлах. Вы также можете обратиться к Control.Lens.Plated .

Кстати, у Free уже есть Recursive экземпляр. FreeF TreeF a будет соответствующей алгеброй. Но вы упомянули, что это не очень хорошо сработало.

Работа напрямую с конструкторами Free и FreeT может оказаться затруднительной. Возможно, здесь могли бы помочь некоторые синонимы шаблонов.