使用 Comonad Fix 组合器

Question

所以我最近一直在尝试不动点，但最终还是遇到了困难通过定期定点足以发现一些用途；现在我要继续 comonadic 固定点，恐怕我被卡住了；

这里有一些我尝试过的和has/hasn没用的例子：

{-# language DeriveFunctor #-}
{-# language FlexibleInstances #-}
module WFix where

import Control.Comonad
import Control.Comonad.Cofree
import Control.Monad.Fix

所以我从勒布定理开始；列表的每个元素都是一个函数它采用最终结果来计算其答案；这让我可以 'spreadsheet' 值可能取决于其他值的计算。

spreadSheetFix :: [Int]
spreadSheetFix = fix $ \result -> [length result, (result !! 0) * 10, (result !! 1) + 1, sum (take 3 result)]

好的，我已经有了基本的修复工作，是时候继续使用 comonad 类型了！这里有一些简单的comonads用于示例：

  data Stream a = S a (Stream a)
    deriving (Eq, Show, Functor)

  next :: Stream a -> Stream a
  next (S _ s) = s

  instance Comonad Stream where
    extract (S a _) = a
    duplicate s@(S _ r) = S s (duplicate r)

  instance ComonadApply Stream where
    (S f fs) <@> (S a as) = S (f a) (fs <@> as)

  data Tape a = Tape [a] a [a]
    deriving (Show, Eq, Functor)

  moveLeft, moveRight :: Tape a -> Tape a
  moveLeft w@(Tape [] _ _) = w
  moveLeft (Tape (l:ls) a rs) = Tape ls l (a:rs)

  moveRight w@(Tape _ _ []) = w
  moveRight (Tape ls a (r:rs)) = Tape (a:ls) r rs

  instance Comonad Tape where
    extract (Tape _ a _) = a
    duplicate w@(Tape l _ r) = Tape lefts w rights
      where
        lefts = zipWith const (tail $ iterate moveLeft w) l
        rights = zipWith const (tail $ iterate moveRight w) r

  instance ComonadApply Tape where
    Tape l f r <@> Tape l' a r' = Tape (zipWith ($) l l') (f a) (zipWith ($) r r')

好的，下面的组合器来自 Control.Comonad;

wfix :: Comonad w => w (w a -> a) -> a
wfix w = extract w (extend wfix w)

cfix :: Comonad w => (w a -> a) -> w a
cfix f = fix (extend f)

kfix :: ComonadApply w => w (w a -> a) -> w a
kfix w = fix $ \u -> w <@> duplicate u

我开始尝试 wfix:

streamWFix :: Int
streamWFix = wfix st
  where
    incNext = succ . extract . next
    st = (S incNext (S incNext (S (const 0) st)))

> streamWFix
-- 2

这似乎是通过在 w 上调用第一个 w a -> a 直到到达在这种情况下，分辨率 const 0；这就说得通了。我们也可以这样做用胶带：

selfReferentialWFix :: Int
selfReferentialWFix = wfix $ Tape [const 10] ((+5) . extract . moveLeft) []
-- selfReferentialWFix == 15

K，我想我明白了，但接下来的我有点卡住了，我似乎对 cfix 应该做什么没有直觉。即使是我能想到的最简单的事情也会永远旋转当我评估它时；甚至试图提取流的第一个元素使用 getOne 失败。

getOne :: Stream a -> a
getOne (S a _) = a

simpleCFix :: Stream Int
simpleCFix = cfix go
  where
    go _ = 0

与kfix类似；即使是简单的尝试似乎也不会终止。我对 kfix 的理解是每个 'slot' 中的函数得到通过了一份专注于该地点的已评估 comonad 的副本；是这样吗？

我试过在这个上使用 'getOne':

streamKFix :: Stream Int
streamKFix = kfix st
  where
    go _ = 0
    st = S go st

这是使用 Tape 的有限尝试，但也失败了运行:

tapeKFix :: Tape Int
tapeKFix = kfix $ Tape [] (const 0) []

所以；关于我的问题，有人可以提供一些运行nable（非平凡）使用 cfix 和 kfix 的例子，并解释它们是如何工作的？我计划使用 kfix 最终做一个“Conway's 生活游戏”风格的实验，我认为 kfix 会有用吗与特定小区周围的社区合作？

欢迎提问任何澄清问题并帮助我扩展我的知识和直觉修复！

谢谢！

Answer 1

Tape 的 ComonadApply 和 Comonad 实例不够懒惰，无法与 kfix 一起使用。

duplicate for Tape 要求您证明磁带存在，然后才能断定结果是 Tape

instance Comonad Tape where
  extract (Tape _ a _) = a
  duplicate w@(Tape l _ r) = Tape lefts w rights
--             ^             ^
-- matches a Tape            |               
-- before determining that the result is a Tape

<@> 在得出结果是 Tape

之前检查两个参数是否都是磁带

instance ComonadApply Tape where
  Tape l f r <@> Tape l' a r' = Tape (zipWith ($) l l') (f a) (zipWith ($) r r')
-- ^             ^              ^
-- matches two Tapes            |
-- before detrmining that the result is a Tape

合并后 kfix (Tape _ _ _) 无法产生 Tape

kfix w            = fix $ \u -> w            <@> duplicate u
kfix (Tape _ _ _) = fix $ \u -> (Tape _ _ _) <@> duplicate u
kfix (Tape _ _ _) = fix $ \u -> (Tape _ _ _) <@> case u of (Tape _ _ _) -> ...
--                         ^                                |
--                         ----------- <<loop>> -------------

您可以通过使用 irrefutable patterns 提高 duplicate、<@> 或两者的效率来解决此问题。即使尚未生成 Tape 构造函数，模式 ~(Tape l a r) 也会匹配。下面介绍如何使用它来提高 duplicate 的工作效率

instance Comonad Tape where
  extract (Tape _ a _) = a
  duplicate w@(~(Tape l _ r)) = Tape lefts w rights
    where
      lefts = zipWith const (tail $ iterate moveLeft w) l
      rights = zipWith const (tail $ iterate moveRight w) r

无可辩驳的模式匹配相当于使用函数提取值。对于 duplicate 相当于写作

left  (Tape l _ _) = l
right (Tape _ _ r) = r

instance Comonad Tape where
  extract (Tape _ a _) = a
  duplicate w = Tape lefts w rights
    where
      l = left w
      r = right w
      ...

使用 Comonad Fix 组合器

Using Comonad Fix Combinators

haskell

comonad

fixpoint-combinators