Comonadical найти все способы сосредоточиться на сетке
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
import Control.Comonad
import Data.Functor.Reverse
import Data.List (unfoldr)
Сначала немного контекста (ха-ха). У меня есть молния над непустыми списками.
data LZipper a = LZipper (Reverse [] a) a [a]
deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)
mkZipper :: a -> [a] -> LZipper a
mkZipper = LZipper (Reverse [])
Вы можете сделать шаг в любом направлении вдоль молнии, но вы можете упасть с конца.
fwd, bwd :: LZipper a -> Maybe (LZipper a)
fwd (LZipper _ _ []) = Nothing
fwd (LZipper (Reverse xs) e (y:ys)) = Just $ LZipper (Reverse (e:xs)) y ys
bwd (LZipper (Reverse []) _ _) = Nothing
bwd (LZipper (Reverse (x:xs)) e ys) = Just $ LZipper (Reverse xs) x (e:ys)
Дублирование застежки-молнии покажет вам все способы, которыми вы можете на нее смотреть, с акцентом на то, как вы смотрите на нее в настоящее время.
instance Comonad LZipper where
extract (LZipper _ x _) = x
duplicate z = LZipper (Reverse $ unfoldr (step bwd) z) z (unfoldr (step fwd) z)
where step move = fmap (\y -> (y, y)) . move
Например:
ghci> duplicate (mkZipper 'a' "bc")
LZipper (Reverse [])
(LZipper (Reverse "") 'a' "bc")
[LZipper (Reverse "a") 'b' "c",LZipper (Reverse "ba") 'c' ""]
-- Abc -> *Abc* aBc abC
ghci> fmap duplicate (fwd $ mkZipper 'a' "bc")
Just (LZipper (Reverse [LZipper (Reverse "") 'a' "bc"])
(LZipper (Reverse "a") 'b' "c")
[LZipper (Reverse "ba") 'c' ""])
-- aBc -> Abc *aBc* abC
(Я использую заглавные буквы и звездочки, чтобы указать фокус молнии.)
Я пытаюсь работать с двумерными сетками с фокусом, представленным как застежка-молния. Каждая внутренняя молния представляет собой ряд сетки. Моя конечная цель - найти пути через сетку, прыгая от соседа к соседу.
Перемещение по сетке поддерживает инвариант, что все строки ориентированы на один и тот же индекс. Это позволяет легко сосредоточиться на любом из ваших соседей.
type Grid a = LZipper (LZipper a)
up, down, left, right :: Grid a -> Maybe (Grid a)
up = bwd
down = fwd
left = traverse bwd
right = traverse fwd
extractGrid :: Grid a -> a
extractGrid = extract . extract
mkGrid :: (a, [a]) -> [(a, [a])] -> Grid a
mkGrid (x, xs) xss = mkZipper (mkZipper x xs) $ map (uncurry mkZipper) xss
Примеры:
ghci> let myGrid = mkGrid ('a', "bc") [('d', "ef"), ('g', "hi")]
ghci> myGrid
LZipper (Reverse [])
(LZipper (Reverse "") 'a' "bc")
[LZipper (Reverse "") 'd' "ef",LZipper (Reverse "") 'g' "hi"]
-- +-------+
-- | A b c |
-- | d e f |
-- | g h i |
-- +-------+
ghci> return myGrid >>= right >>= down
Just (LZipper (Reverse [LZipper (Reverse "a") 'b' "c"])
(LZipper (Reverse "d") 'e' "f")
[LZipper (Reverse "g") 'h' "i"])
-- +-------+
-- | a b c |
-- | d E f |
-- | g h i |
-- +-------+
То, что я хочу, это эквивалент LZipper"s duplicate для сеток: функция, которая берет сетку и создает сетку всех способов, которыми вы можете смотреть на сетку, с акцентом на текущий взгляд на нее.
duplicateGrid :: Grid a -> Grid (Grid a)
Что я ожидаю:
duplicateGrid myGrid
+-------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | a B c | | a b C | |
| * d e f * | d e f | | d e f | |
| * g h i * | g h i | | g h i | |
| ********* +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | a b c | | a b c | | a b c | |
| | D e f | | d E f | | d e F | |
| | g h i | | g h i | | g h i | |
| +-------+ +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | a b c | | a b c | | a b c | |
| | d e f | | d e f | | d e f | |
| | G h i | | g H i | | g h I | |
| +-------+ +-------+ +-------+ |
+-------------------------------+
Я старался duplicateGrid = duplicate . duplicate, Это имеет правильный тип, но (при условии, что я интерпретировал show выводится правильно, что я, вероятно, не сделал), это дает только сетки, сосредоточенные где-то на первом столбце:
(duplicate . duplicate) myGrid
+-------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | a b c | | a b c | |
| * d e f * | D e f | | d e f | |
| * g h i * | g h i | | G h i | |
| ********* +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | A b c | | a b c | | a b c | |
| | d e f | | D e f | | d e f | |
| | g h i | | g h i | | G h i | |
| +-------+ +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | A b c | | a b c | | a b c | |
| | d e f | | D e f | | d e f | |
| | g h i | | g h i | | G h i | |
| +-------+ +-------+ +-------+ |
+-------------------------------+
Я тоже пробовал duplicateGrid = duplicate . fmap duplicate, Предполагая еще раз, что я способен интерпретировать show вывод, это дало мне что-то, что содержало неправильные сетки и смещало фокусы строк, так что движение вниз также двигало бы вас вперед:
(duplicate . fmap duplicate) myGrid
+-------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | D e f | | G h i | |
| * a B c * | d E f | | g H i | |
| * a b C * | d e F | | g h I | |
| ********* +-------+ +-------+ |
| +-------+ ********* +-------+ |
| | A b c | * D e f * | G h i | |
| | a B c | * d E f * | g H i | |
| | a b C | * d e F * | g h I | |
| +-------+ ********* +-------+ |
| +-------+ +-------+ ********* |
| | A b c | | D e f | * G h i * |
| | a B c | | d E f | * g H i * |
| | a b C | | d e F | * g h I * |
| +-------+ +-------+ ********* |
+-------------------------------+
Такое чувство, что это был бы легкий вопрос для тех, кто в курсе, но это заставляет мою голову вращаться. Я полагаю, я мог бы запустить функцию, которая вызывает up, down, left а также right, но я чувствую, что комонадный механизм должен быть в состоянии сделать это для меня. Какова правильная реализация duplicateGrid?
3 ответа
Это небольшая проблема здесь, которую мы пытаемся составить Grid с самим собой, потому что эта установка дает нам слишком много неправильных способов реализации duplicate с правильным типом. Полезно рассмотреть общий случай, когда составленные комонады не обязательно совпадают.
Предположим, у нас есть f а также g comonads. Тип duplicate будет выглядеть так:
duplicate :: f (g a) -> f (g (f (g a)))
Мы можем получить следующее исключительно с помощью Comonad экземпляры:
duplicate . fmap duplicate :: f (g a) -> f (f (g (g a)))
Из этого становится очевидно, что мы должны поменяться f а также g в середине.
Есть класс типа с именем Distributive у нас есть метод, который мы хотим.
class Functor g => Distributive g where
distribute :: Functor f => f (g a) -> g (f a)
В частности, нам необходимо реализовать Distributive g, а потом duplicate Для составленной комонады можно реализовать:
duplicate = fmap distribute . duplicate . fmap duplicate
Тем не менее, документация в Distributive говорит, что значения g должны иметь одинаковую форму, чтобы мы могли собрать произвольное количество копий без потери информации.
Чтобы проиллюстрировать это, если Vec n a является n вектор, то distribute :: [Vec n a] -> Vec n [a] это просто матричное перемещение. Необходимо заранее определить размер внутреннего вектора, поскольку для транспонирования на "рваной" матрице должны быть отброшены некоторые элементы, а это не закономерно. Бесконечные потоки и молнии также хорошо распределяются, так как они тоже имеют только один возможный размер.
Zipper не законно Distributive так как Zipper содержит значения с контекстами разного размера. Тем не менее, мы можем реализовать неправильное распределение, которое предполагает одинаковые размеры контекста.
Ниже буду реализовывать duplicate за Grid с точки зрения неправильного распределения для основных списков.
В качестве альтернативы, можно просто закатать рукава и реализовать функцию транспонирования на Zipper (Zipper a) непосредственно. Я действительно сделал это, но это доставило мне головную боль, и я далеко не уверен, что это правильно. Лучше сделать типы как можно более общими, чтобы сузить пространство возможных реализаций, чтобы было меньше места для ошибок.
Я собираюсь опустить Reverse чтобы уменьшить синтаксический шум; Я надеюсь, что вы меня извините.
{-# language DeriveFunctor #-}
import Control.Comonad
import Data.List
import Control.Monad
data Zipper a = Zipper [a] a [a] deriving (Eq, Show, Functor)
lefts, rights :: Zipper a -> [a]
lefts (Zipper ls _ _) = ls
rights (Zipper _ _ rs) = rs
bwd :: Zipper a -> Maybe (Zipper a)
bwd (Zipper [] _ _) = Nothing
bwd (Zipper (l:ls) a rs) = Just $ Zipper ls l (a:rs)
fwd :: Zipper a -> Maybe (Zipper a)
fwd (Zipper _ _ []) = Nothing
fwd (Zipper ls a (r:rs)) = Just $ Zipper (a:ls) r rs
instance Comonad Zipper where
extract (Zipper _ a _) = a
duplicate z =
Zipper (unfoldr (fmap (join (,)) . bwd) z) z (unfoldr (fmap (join (,)) . fwd) z)
Мы можем распространять списки, если заранее знаем их длину. Поскольку списки Хаскелла могут быть бесконечными, мы должны измерять длину с возможно бесконечными ленивыми натуральными числами. Альтернативным решением для измерения длины было бы использование "направляющего" списка, по которому мы можем сжать другие списки. Однако в функциях распределения я бы предпочел не предполагать, что такой фиктивный список всегда доступен.
data Nat = Z | S Nat
length' :: [a] -> Nat
length' = foldr (const S) Z
distList :: Functor f => Nat -> f [a] -> [f a]
distList Z fas = []
distList (S n) fas = (head <$> fas) : distList n (tail <$> fas)
Конечно, это не работает с исключениями времени выполнения, если наше предположение о длине неверно.
Мы можем распространять Zipper s путем распределения их фокусов и контекстов, при условии, что мы знаем длину контекстов:
distZipper :: Functor f => Nat -> Nat -> f (Zipper a) -> Zipper (f a)
distZipper l r fz = Zipper
(distList l (lefts <$> fz)) (extract <$> fz) (distList r (rights <$> fz))
Наконец, мы можем продублировать Grid S, как мы видели раньше, но сначала мы должны определить форму внутреннего Zipper s. Поскольку мы предполагаем, что все внутреннее Zipper имеют одинаковую форму, мы только смотрим на Zipper в центре внимания:
duplicateGrid :: Grid a -> Grid (Grid a)
duplicateGrid grid@(Zipper _ (Zipper ls _ rs) _) =
fmap (distZipper (length' ls) (length' rs)) $ duplicate $ fmap duplicate grid
Тестирование этого (как вы, должно быть, уже испытали) довольно ужасно, и я еще не удосужился проверить даже случай два на два вручную.
Тем не менее, я довольно уверен в приведенной выше реализации, поскольку определения сильно ограничены типами.
Основная проблема, с которой вы сталкиваетесь, заключается в том, что молнии изначально не поддерживают двухмерные структуры. Ответ там велик (другой ответ в основном точно ваше определение Grid), и я бы посоветовал вам прочитать его, но суть в том, что застежки-молнии идентифицируют элементы с путями, чтобы туда попасть, и в двумерном пространстве такая идентификация проблематична, потому что есть много путей, чтобы добраться до точки.
Следовательно, вы заметите, что в то время как ваш up а также down функции для Grid S был полностью определен в терминах молнии, вам нужно было использовать Traversable механизм для определения left а также right, Это также означает, что left а также right не обладают такими же характеристиками производительности, как up а также down так как вы "идете против зерна", так сказать.
Так как ваш Comonad экземпляр был определен только с использованием ваших функций молнии, он может только duplicate в направлении, которое определяется вашей молнией, а именно fwd а также bwd (и, соответственно, up а также down).
Изменить: После некоторой дополнительной мысли, я думаю, что ваш подход будет принципиально проблематичным. Я сохранил свой оригинальный текст ниже, но есть более явная проблема.
Если вы пытаетесь обойти молнии, как если бы они были похожи на любую другую 2-ю структуру, вы будете продолжать получать Nothing с вашим duplicate, Давайте отметим, что произойдет, если вы на самом деле попытаетесь использовать свой up, down, left, right функции на якобы без проблем duplicate (mkZipper 'a' "bc"),
*Main> let allRows = duplicate $ mkZipper 'a' "bc"
*Main> down allRows -- This is fine since we're following the zipper normally
Just (LZipper (Backwards [LZipper (Backwards "") 'a' "bc"]) (LZipper (Backwards "a") 'b' "c") [LZipper (Backwards "ba") 'c' ""])
*Main> right allRows
Nothing -- That's bad...
*Main> down allRows >>= right
Nothing -- Still nothing
перемещение right а также left требует (как вы должным образом заметили, упомянув об инварианте), что каждый из ваших вложенных молний является однородным по структуре, в противном случае traverse провалится преждевременно. Это означает, что если вы действительно хотите использовать left а также right, единственный способ, которым это будет хорошо играть с duplicate если вы используете самый равномерный duplicate возможный.
duplicate z @ (LZipper left focus right) =
LZipper (fmap (const z) left) z (fmap (const z) right)
Альтернативой является использование только тех функций, которые поставляются с застежкой-молнией. Это означает только использование fwd а также bwd, а потом extract сосредоточиться и продолжать использовать fwd а также bwd получить то же самое, что и left а также right, Конечно, это означает отказ от возможности сказать "прямо тогда вниз" и "вниз тогда вправо", но, как мы уже видели, молнии плохо играют с несколькими путями.
Теперь давайте проверим вашу интуицию на предмет того, как лучше всего интерпретировать происходящее duplicate . duplicate $ myGrid, Хороший квадрат на самом деле не лучший способ думать о том, что происходит (и вы поймете, почему, если вы ограничитесь extract а также fwd а также bwd).
*Main> let allRows = duplicate . duplicate $ myGrid
*Main> fwd $ extract allRows -- Makes sense
Just ...
-- This *should* be the bottom-left of the grid
*Main> let bottomLeft = extract <$> fwd allRows >>= fwd
*Main> bottomLeft >>= fwd
Nothing -- Nope!
*Main> bottomLeft >>= bwd
Just ... -- Wait a minute...
У нас на самом деле есть рваная структура.
+---------------------------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | a b c | | a b c | |
| * d e f * | D e f | | d e f | |
| * g h i * | g h i | | G h i | |
| ********* +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | A b c | | a b c | | a b c | |
| | d e f | | D e f | | d e f | |
| | g h i | | g h i | | G h i | |
| +-------+ +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | A b c | | a b c | | a b c | |
| | d e f | | D e f | | d e f | |
| | g h i | | g h i | | G h i | |
| +-------+ +-------+ +-------+ |
+---------------------------------------------------+
Квадраты внутри этой рваной структуры на самом деле тоже не квадраты, они также будут рваные. Эквивалентно вы могли бы думать о fwd как идет по диагонали. Или просто бросьте молнии для двухмерных конструкций.
По моему опыту, молнии действительно лучше всего работают в паре с древовидными вещами. Я бы не удивился, если бы эксперт по Haskell смог придумать способ использования застежек-молний и всех преимуществ обновления / доступа, которые идут с ними для таких вещей, как циклические графы или даже просто старые DAG, но я не могу думать ни о каком с вершины моей скудной головы:).
Мораль этой истории заключается в том, что молнии являются головной болью для двумерных структур. (Бесполезно подумал: может быть, линзы могут быть интересными?)
Для любопытных мой подход ниже также работает, только если вы помните о неровности структуры, с которой мы имеем дело; то есть fwd Двойное и последующее извлечение даст вам эквивалент того, что ОП хочет в правом нижнем углу своей сетки, а не в левом нижнем углу.
Оригинал:
Так что вам нужен какой-то способ переключения между вашими чисто на основе молнии duplicate и ваш Traversable дубликат. Самый простой способ - взять duplicate функция, которую вы уже написали, и просто добавьте traverse в середине.
duplicateT :: Traversable t => t (LZipper a) -> LZipper (t (LZipper a))
duplicateT z = LZipper (Backwards $ unfoldr (step bwd) z) z (unfoldr (step fwd) z)
-- Everything's the exact same except for that extra traverse
where step move = fmap (\y -> (y, y)) . (traverse move)
Теперь, когда у нас есть более общее duplicateT мы можем избавиться от неприятного дублирования кода, переопределив duplicate в вашем Comonad например, быть:
-- requires import Data.Functor.Identity
duplicate = fmap runIdentity (duplicate' (Identity z))
Тогда следующее дает вам то, что вы хотите
duplicateGrid = duplicate . duplicateT
Или, если вы хотите изменить порядок столбцов и строк, вы можете сделать наоборот.
Примечание: было бы еще лучше, если бы Haskell позволял вам изначально определять ограничения типов для классов типов, чтобы вы могли иметь различные экземпляры Comonad (все опосредовано newtype s возможно) для вашего LZipper которые меняют направление вашего duplicate, Проблема в том, что вы хотели бы что-то вроде instance Comonad LZipper (LZipper a) where ... или эквивалент newtype который вы просто не можете написать на Хаскеле. Можно предположить, что вы можете сделать что-то подобное с семействами типов, но я подозреваю, что это, вероятно, излишне для этого конкретного экземпляра.
Изменить: На самом деле вам даже не нужно duplicateT если вы дадите соответствующий Applicative экземпляр для LZipper,
instance Applicative LZipper where
pure x = LZipper (Backwards (repeat x)) x (repeat x)
(LZipper leftF f rightF) <*> (LZipper left x right) = LZipper newLeft (f x) newRight
where
newLeft = (Backwards (zipWith ($) (forwards leftF) (forwards left)))
newRight = (zipWith ($) rightF right)
Теперь просто возьмите оригинал duplicate у вас было раньше и использовать traverse,
duplicateGrid = duplicate . (traverse duplicate)
Так что есть тесно связанные друг с другом, которые могут помочь вам. У нас есть:
newtype MC m a = MC { unMC :: m -> a }
instance Monoid m => Comonad (MC m) where
extract (MC f) = f mempty
duplicate (MC f) = MC (\x -> MC (\y -> f (x <> y)))
instance Functor (MC m) where
fmap f (MC g) = MC (f . g)
Таким образом, двунаправленный бесконечный массив будет MC (Sum Integer) a и двунаправленная бесконечная сетка будет MC (Sum Integer, Sum Integer) a, И, конечно же, MC m (MC n a) изоморфен MC (m,n) a через карри.
В любом случае, желаемая функция дублирования сетки будет аналогична (без учета оболочек нового типа и карри):
duplicateGrid g x y dx dy = g (x + dx) (y + dy)
duplicate для 1D массива выглядит так:
duplicate f x y = f (x+y)
Так duplicate . duplicate является:
(duplicate . duplicate) f x y z
= duplicate (duplicate f) x y z
= duplicate f (x+y) z
= f (x + y + z)
Не то, что нужно. Что значит fmap duplicate выглядит как:
fmap duplicate f x y z = f x (y + z)
Это понятно делать duplicate снова даст нам то же самое, что и duplicate . duplicate (что и должно быть, так как это комонадный закон). Тем не менее, это немного более перспективно. Если бы мы сделали два fmapс...
fmap (fmap duplicate) f x y z w
= fmap duplicate (f x) y z w
= f x y (z + w)
Теперь, если мы сделали duplicate мы бы получили
(duplicate . fmap (fmap duplicate)) f x y z w = f (x+y) (z+w)
Но это все еще не так. Изменение имен переменных, его f (x+y) (dx + dy), Итак, нам нужно что-то поменять местами две внутренние переменные... Название теории категорий для того, что мы хотим, является законом распределения. Хаскель зовут Traversable, Что значит sequenceA выглядеть для функций (функции образуют Applicative функтор и на самом деле Monad, Reader монада) как выглядит? Тип говорит все.
sequenceA :: (a -> b -> c) -> (b -> a -> c)
sequenceA f x y = f y x
Итак, наконец:
fmap sequenceA g x y z = g x z y
(duplicate . fmap (fmap duplicate) . fmap sequenceA) g x y dx dy
= (duplicate . fmap (fmap duplicate)) g x dx y dy
= g (x + dx) (y + dy)
Я на самом деле не пробовал аналогичный код, поэтому я не знаю, работает ли он, но математика говорит, что должен.