haskell - 帮助编写 "the colist Monad"(习语介绍论文中的练习)

Question

我正在阅读 Conor McBride 和 Ross Paterson 的“Functional Pearl/Idioms: applicative programming with effects:”(新版本，标题中带有“idioms”)。我在练习 4 中遇到了一点困难，下面将对此进行解释。任何提示将不胜感激(特别是:我应该开始写 fmap 和 join 还是 return 和 >>= ？)。

问题陈述

您想创建一个 instance Monad []在哪里

return x = repeat x

和 ap = zapp .

标准库函数

如上页。论文2， ap将一元函数值应用于一元值。

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

嗯。我不禁认为这个练习有点不公平。

Exercise 4 (the colist Monad)

Although repeat and zapp are not the return and ap of the usual Monad [] instance, they are none the less the return and ap of an alternative monad, more suited to the coinductive interpretation of []. What is the join :: [[x]] → [x] of this monad?

Comment on the relative efficiency of this monad’s ap and our zapp.

首先，我相当确定有问题的 monad 实例是 。对 [] 无效一般 .当他们说“共归纳解释”时，我怀疑这是指无限列表。在某些情况下，该实例实际上对有限列表有效，但通常不适用于任意列表。

所以这是你的第一个非常笼统的提示——为什么 monad 实例只对某些列表有效，尤其是无限列表？

这是您的第二个提示: fmap和 return考虑到本文前面的其他定义，这是微不足道的。您已经有 return ; fmap只是稍微不那么明显。

此外， (>>=)与任何 Monad 一样，在其他功能方面具有简单的实现，留下 join作为问题的症结所在。在大多数情况下 (>>=)使用 join 进行编程更自然在概念上更基本，在这种情况下，我认为更容易分析。所以我建议继续努力，忘记 (>>=)目前。一旦你有了一个实现，你可以回去重构 (>>=)并检查单子(monad)定律以确保一切正常。

最后，假设您有 fmap可用，但没有别的。给定类型为 [a -> b] 的值和 [a] , 你可以将它们组合起来得到 [[b]] 类型的东西. join的类型这里是 [[a]] -> [a] .你怎么写 join这样您就可以得到与使用 zapp 相同的结果在原始值上？请注意，关于相对效率的问题和问题一样，是关于实现的线索。