Use of combine supervising harvesters
So, I've been experimenting with fixed points lately and finally struggling through regular fixed points enough to discover some uses; now i am moving accompanying fixed points and i am afraid i am stuck;
Here are some examples of what I've tried and what / didn't work:
{-# language DeriveFunctor #-}
{-# language FlexibleInstances #-}
module WFix where
import Control.Comonad
import Control.Comonad.Cofree
import Control.Monad.Fix
So I started with Loeb's theorem as a list; each item in the list is a function that takes an end result to compute its answer; this allows me to make a "table" where values can depend on other values.
spreadSheetFix :: [Int]
spreadSheetFix = fix $ \result -> [length result, (result !! 0) * 10, (result !! 1) + 1, sum (take 3 result)]
Ok, so I have a basic fix, time to go to comonad types! Here are some simple examples that you can use for examples:
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')
Ok, so the following combinators come from 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
I started by testing wfix:
streamWFix :: Int
streamWFix = wfix st
where
incNext = succ . extract . next
st = (S incNext (S incNext (S (const 0) st)))
> streamWFix
-- 2
This one seems to work, calling the first one w a -> a
on w before reaching resolution const 0
in this case; It makes sense. We can also do this with a ribbon:
selfReferentialWFix :: Int selfReferentialWFix = wfix $ Tape [const 10] ((+5) . extract . moveLeft) [] -- selfReferentialWFix == 15
K, I think I'm getting this one, but the following, I'm stuck, I don't seem to have an intuition for what cfix is supposed to do. Even the simplest thing that I could think of spins forever when I appreciate it; even trying to fetch the first element of the stream using getOne.
getOne :: Stream a -> a
getOne (S a _) = a
simpleCFix :: Stream Int
simpleCFix = cfix go
where
go _ = 0
Similar to kfix; even simple attempts do not seem to stop. My understanding of kfix was that the function in each slot passed a copy of the evaluated comonad centered on that location; what's the case?
I tried using 'getOne' in this:
streamKFix :: Stream Int
streamKFix = kfix st
where
go _ = 0
st = S go st
Here's a final attempt at using a ribbon that also fails to start:
tapeKFix :: Tape Int tapeKFix = kfix $ Tape [] (const 0) []
So, right down to my question, can someone suggest some managed (non-trivial) examples of using cfix and kfix, and explain how they work? I plan on using kfix to eventually make "Conway's I think kfix will be useful in dealing with the neighborhood around this cell?"
Feel free to ask any clarifying questions and help me expand my knowledge and intuition to fix it!
Thank!
source to share
Examples ComonadApply
and Comonad
for are Tape
not lazy enough to use with kfix
.
duplicate
for Tape
requires you to prove that the tape exists before inferring that the result isTape
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
<@>
checks that both arguments are tapes before inferring that the result is 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
The combined method kfix (Tape _ _ _)
does not allowTape
kfix w = fix $ \u -> w <@> duplicate u
kfix (Tape _ _ _) = fix $ \u -> (Tape _ _ _) <@> duplicate u
kfix (Tape _ _ _) = fix $ \u -> (Tape _ _ _) <@> case u of (Tape _ _ _) -> ...
-- ^ |
-- ----------- <<loop>> -------------
You can fix this by doing duplicate
, <@>
or both of the better performing ones using irrefutable patterns . The pattern ~(Tape l a r)
matches even if no constructor Tape
has been created yet. Here's how you would use it to make it duplicate
effective
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
Consistent pattern matches are equivalent to using functions to retrieve values. For duplicate
this is equivalent to writing
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
...
source to share