Каковы некоторые мотивирующие примеры для Cofree CoMonad в Haskell?

Я играю с Cofree и не могу его перехватить.

Например, я хочу играть с Cofree [] Num в ghci и не могу получить интересные примеры.

Например, если я создаю тип Cofree:

let a = 1 :< [2, 3]

Я ожидал бы extract a == 1, но вместо этого получаю эту ошибку:

No instance for (Num (Cofree [] a0)) arising from a use of ‘it’
    In the first argument of ‘print’, namely ‘it’
    In a stmt of an interactive GHCi command: print it

И тип:

extract a :: (Num a, Num (Cofree [] a)) => a

Могу ли я получить несколько простых примеров, даже тривиальных, о том, как использовать Cofree с, скажем, функторами: [] или Maybe или Either, который демонстрирует

extract
extend
unwrap
duplicate?

Cross Добавлено: https://www.reddit.com/r/haskell/comments/4wlw70/what_are_some_motivating_examples_for_cofree/

EDIT: руководствуясь комментарием Дэвида Янга, вот несколько лучших примеров, показывающих, где мои первые попытки были ошибочными, однако мне все же нравятся некоторые примеры, которые могут помочь интуиции Cofree:

> let a = 1 :< []
> extract a
    1
> let b = 1 :< [(2 :< []), (3 :< [])]
> extract b
    1
> unwrap b
    [2 :< [],3 :< []]
> map extract $ unwrap b
    [2,3]

Ответ 1

Давайте просто перечислим определение типа данных Cofree.

data Cofree f a = a :< f (Cofree f a)

Это, по крайней мере, достаточно, чтобы диагностировать проблему с примером. Когда вы написали

1 :< [2, 3]

вы сделали небольшую ошибку, которая сообщила об этом более тонко, чем полезно. Здесь f = [] и a есть что-то числовое, потому что 1 :: a. Соответственно вам нужно

[2, 3] :: [Cofree [] a]

и, следовательно,

2 :: Cofree [] a

который мог бы быть ОК, если бы Cofree [] a были также и экземпляром Num. Таким образом, ваше определение получает ограничение, которое вряд ли будет удовлетворено, и действительно, когда вы используете свое значение, попытка удовлетворить ограничение не выполняется.

Повторите попытку с помощью

1 :< [2 :< [], 3 :< []]

и вам лучше повезло.

Теперь посмотрим, что у нас есть. Начните с упрощения. Что Cofree f ()? Что, в частности, есть Cofree [] ()? Последнее изоморфно фиксированной точке []: древовидные структуры, где каждый node представляет собой список поддерев, также известный как "немаркированные розовые деревья". Например.

() :< [  () :< [  () :< []
               ,  () :< []
               ]
      ,  () :< []
      ]

Аналогично, Cofree Maybe () является более или менее фиксированной точкой Maybe: копией натуральных чисел, потому что Maybe дает нам либо нулевое, либо одно положение, в которое нужно подключить поддерево.

zero :: Cofree Maybe ()
zero = () :< Nothing
succ :: Cofree Maybe () -> Cofree Maybe ()
succ n = () :< Just n

Важным тривиальным случаем является Cofree (Const y) (), который является копией y. Функтор Const y не дает положений для поддеревьев.

pack :: y -> Cofree (Const y) ()
pack y = () :< Const y

Далее, давайте заняться другим параметром. Он сообщает вам, какой ярлык вы прикрепляете к каждому node. Переименование параметров более внушительно

data Cofree nodeOf label = label :< nodeOf (Cofree nodeOf label)

Когда мы обозначаем пример (Const y), мы получаем пары

pair :: x -> y -> Cofree (Const y) x
pair x y = x :< Const y

Когда мы прикрепляем метки к узлам наших чисел, мы получаем непустые списки

one :: x -> Cofree Maybe x
one = x :< Nothing
cons :: x -> Cofree Maybe x -> Cofree Maybe x
cons x xs = x :< Just xs

И для списков мы получим маркированные розовые деревья.

0 :< [  1 :< [  3 :< []
             ,  4 :< []
             ]
     ,  2 :< []
     ]

Эти структуры всегда "непустые", потому что есть хотя бы верхний node, даже если он не имеет дочерних элементов, и что node всегда будет иметь метку. Операция extract дает вам метку верхнего node.

extract :: Cofree f a -> a
extract (a :< _) = a

То есть, extract отбрасывает контекст верхней метки.

Теперь операция duplicate украшает каждую метку собственным контекстом.

duplicate :: Cofree f a -> Cofree f (Cofree f a)
duplicate a :< fca = (a :< fca) :< fmap duplicate fca  -- f fmap

Мы можем получить экземпляр Functor для Cofree f, посетив все дерево

fmap :: (a -> b) -> Cofree f a -> Cofree f b
fmap g (a :< fca) = g a :< fmap (fmap g) fca
    --                     ^^^^  ^^^^
    --                 f fmap  ||||
    --                           (Cofree f) fmap, used recursively

Нетрудно видеть, что

fmap extract . duplicate = id

потому что duplicate украшает каждый node своим контекстом, затем fmap extract отбрасывает украшение.

Обратите внимание, что fmap позволяет смотреть только на метки ввода для вычисления меток вывода. Предположим, мы хотели вычислить выходные метки в зависимости от каждой входной метки в ее контексте? Например, учитывая немаркированное дерево, мы можем пометить каждый node размером всего его поддерева. Благодаря экземпляру Foldable для Cofree f, мы должны иметь возможность подсчитывать узлы с.

length :: Foldable f => Cofree f a -> Int

Итак, это означает

fmap length . duplicate :: Cofree f a -> Cofree f Int

Основная идея comonads заключается в том, что они захватывают "вещи с каким-то контекстом", и они позволяют повсюду применять контекстно-зависимые карты.

extend :: Comonad c => (c a -> b) -> c a -> c b
extend f = fmap f       -- context-dependent map everywhere
           .            -- after
           duplicate    -- decorating everything with its context

Определение extend более непосредственно спасает вас от дублирования (хотя это только для совместного использования).

extend :: (Cofree f a -> b) -> Cofree f a -> Cofree f b
extend g [email protected](_ :< fca) = g ca :< fmap (extend g) fca

И вы можете получить duplicate назад, взяв

duplicate = extend id -- the output label is the input label in its context

Кроме того, если вы выбрали extract как вещь, которую нужно сделать для каждого ярлыка в контексте, вы просто помещаете каждую метку туда, откуда она появилась:

extend extract = id

Эти "операции над метками-в-контексте" называются "стрелками со-Клейсли",

g :: c a -> b

и работа extend заключается в том, чтобы интерпретировать стрелку co-Kleisli как функцию для целых структур. Операция extract является тождественной co-Kleisli стрелкой, и она интерпретируется как extend как функция тождества. Конечно, есть композиция со-Клейсли

(=<=) :: Comonad c => (c s -> t) -> (c r -> s) -> (c r -> t)
(g =<= h) = g . extend h

и законы комонады гарантируют, что =<= ассоциативен и поглощает extract, что дает нам категорию co-Kleisli. Более того,

extend (g =<= h)  =  extend g . extend h

так что extend является функтором (в категориальном смысле) от категории co-Kleisli до множеств-функций. Эти законы нетрудно проверить на Cofree, поскольку они следуют из законов Functor для формы node.

Теперь один полезный способ увидеть структуру в cofree comonad - это своего рода "игровой сервер". Структура

a :< fca

представляет состояние игры. Движение в игре состоит либо из "остановки", и в этом случае вы получаете a или "continue", выбирая поддерево <<264 > . Например, рассмотрим

Cofree ((->) move) prize

Клиент для этого сервера должен либо остановиться, либо продолжить, указав move: это список move s. Игра разыгрывается следующим образом:

play :: [move] -> Cofree ((->) move) prize -> prize
play []       (prize :< _) = prize
play (m : ms) (_     :< f) = play ms (f m)

Возможно, move является Char, а prize является результатом разбора последовательности символов.

Если вы будете достаточно пристально смотреть, вы увидите, что [move] - это версия Free ((,) move) (). Свободные монады представляют собой стратегии клиентов. Функтор ((,) move) представляет собой командный интерфейс с только командой "Отправить a move". Функтором ((->) move) является соответствующая структура "отвечает на отправку a move".

Некоторые функторы можно рассматривать как захват командного интерфейса; свободная монада для такого функтора представляет собой программы, которые создают команды; функтор будет иметь "двойную", которая представляет собой реакцию команд; cofree comonad of dual - это общее понятие среды, в которой могут выполняться программы, которые создают команды, с меткой, говорящей, что делать, если программа останавливается и возвращает значение, а субструктуры говорят о том, как продолжать выполнение программы, если он выдает команду.

Например,

data Comms x = Send Char x | Receive (Char -> x)

описывает возможность отправки или приема символов. Его двойственный

data Responder x = Resp {ifSend :: Char -> x, ifReceive :: (Char, x)}

Как упражнение, посмотрите, можете ли вы реализовать взаимодействие

chatter :: Free Comms x -> Cofree Responder y -> (x, y)