帮助撰写"colist monad"(从成语介绍练习)

Question

我正在阅读Conor McBride和Ross Paterson的"功能性珍珠/成语:带效果的应用程序编程:"(新版本,标题中带有"成语").我对练习4有点困难,这将在下面解释.任何提示,将不胜感激(尤其是:我应该开始写作fmap和join或return和>>=？).

问题陈述

你想创建一个instance Monad []地方

return x = repeat x

和ap = zapp.

标准库函数

如同在p.本文的第2部分将apmonadic函数值应用于monadic值.

ap :: Monad m => m (s -> t) -> m s -> m t
ap mf ms = do
    f <- mf
    s <- ms
    return (f s)

我用规范符号扩展了这个,

ap mf ms = mf >>= (\f -> (ms >>= \s -> return (f s)))

特定于列表的函数zapp("zippy应用程序")将一个列表中的函数应用于另一个列表中的对应值,即

zapp (f:fs) (s:ss) = f s : zapp fs ss

我的困难

请注意,在扩展形式中,mf :: m (a -> b)是[(a -> b)]我们案例中的函数列表.所以,在第一次申请中>>=,我们有

(f:fs) >>= mu

哪里mu = (\f -> (ms >>= \s -> return (f s))).现在,我们可以调用fs >>= mu子程序,但是这不知道要删除第一个元素ms.(回想一下,我们希望得到的列表是[f1 s1,f2 s2,...].我试图破解一些东西,但是......如预测的那样,它没有用......任何帮助都会非常感激.

提前致谢!

编辑1

我想我得到了它的工作; 首先我重写ap以fmap和join为用户"comonad"建议.

我信仰的飞跃就是这样fmap = map.如果有人能解释如何到达那里,我会非常感激.在此之后,显然join在用户"comonad"建议的列表列表上工作,并且应该是对角线,\x -> zipWith ((!!) . unL) x [0..].我的完整代码是这样的:

newtype L a = L [a] deriving (Eq, Show, Ord)
unL (L lst) = lst
liftL :: ([a] -> [b]) -> L a -> L b
liftL f = L . f . unL

joinL :: L (L a) -> L a
joinL = liftL $ \x -> zipWith ((!!) . unL) x [0..]

instance Functor L where
    fmap f = liftL (map f)

instance Monad L where
    return x = L $ repeat x
    m >>= g = joinL (fmap g m)

希望这是正确的(似乎是本文第18页的"解决方案")...感谢大家的帮助!

Answer 1

嗯.我不禁想到这次演习有点不公平.

练习4(colist Monad)

虽然repeat并zapp没有对return和ap平常的Monad []情况下,他们没有少的return和ap替代单子的,更适合的coinductive解释[].什么是join :: [[x]] ? [x]这个单子？

评论这个monad ap和我们的相对效率zapp.

首先,我相当确定有问题的monad实例一般无效[].当他们说"共同解释"时,我怀疑这指的是无限的名单.在某些情况下,实例实际上对有限列表有效,但对于一般的任意列表则不然.

所以这是你的第一个,非常一般的暗示 - 为什么monad实例只对某些列表有效,特别是无限列表？

这里是你的第二个提示:fmap和return是在早期论文给出微不足道的其他定义.你已经拥有return; fmap只是略显不明显.

此外,(>>=)在其他功能方面具有易于实现,与任何Monad,这让join作为问题的症结所在.在大多数情况下(>>=)编程更自然,但join在概念上更具基础性,在这种情况下,我认为,分析更直接.所以我建议你继续努力,暂时忘记(>>=).实施后,您可以返回并重新构建(>>=)并检查monad定律,以确保一切正常.

最后,假设你有一个fmap可用的时刻,但没有别的.考虑到与类型值[a -> b]和[a],你可以结合他们得到类型的东西[[b]].join这里的类型是[[a]] -> [a].你怎么写join这样的,你得到的结果zapp与原始值相同？请注意,关于相对效率的问题以及问题是关于实施的线索.

Answer 2

我只是想我应该澄清一下,标题中带有练习和"成语"的版本是一篇较早的论文草稿,最终出现在JFP中.当时,我错误地认为colists(我的意思是可能是无限的,可能是有限的列表)是一个monad,其方式与zapp相对应:有一个似乎合理的候选者(在其他答案中提到)但是Jeremy Gibbons很友好地向我们指出它不符合monad法则.反例涉及具有不同有限长度的列表的"参差不齐"列表.相应地,在JFP文章中,我们得到了纠正.(我们对它感到非常高兴,因为我们喜欢找到那些(<*>)不是Monad的ap的应用函子.)

通过排除粗糙的案例,必然无限的列表(即流)确实形成了一个其行为类似于zapp的monad.有关线索,请注意Stream x与Nat - > x同构.

我为这种困惑道歉.在网络上留下旧的,未完成的草稿(充满错误)有时是危险的(ha ha).