list - 流(无限列表)monad 模拟了哪些效果？

Question

monad 的各种实例模拟不同类型的效果:例如，Maybe模型偏爱，List不确定性，Reader只读状态。我想知道流数据类型(或无限列表或共同列表)的monad实例是否有这样直观的解释，data Stream a = Cons a (Stream a) (见下面它的 monad 实例定义)。我在 few 上偶然发现了流单子(monad)。 different occasions我想更好地了解它的用途。

data Stream a = Cons a (Stream a)

instance Functor Stream where
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

instance Applicative Stream where
    pure a                      = Cons a (pure a)
    (Cons f fs) <*> (Cons a as) = Cons (f a) (fs <*> as)

instance Monad Stream where
    xs >>= f = diag (fmap f xs)

diag :: Stream (Stream a) -> Stream a
diag (Cons xs xss) = Cons (hd xs) (diag (fmap tl xss))
    where
        hd (Cons a _ ) = a
        tl (Cons _ as) = as

P.S.:我不确定我的语言是否非常精确(尤其是在使用“效果”这个词时)，所以请随时纠正我。

Answer 1

Stream monad 与 Reader Natural 同构( Natural :自然数)，这意味着 Stream 之间存在双射和 Reader Natural这保留了它们的一元结构。

直观地

两个Stream a和 Reader Natural a ( Natural -> a ) 可以看作是表示 a 的无限集合由整数索引。

fStream = Cons a0 (Cons a1 (Cons a2 ...))

fReader = \i -> case i of
  0 -> a0
  1 -> a1
  2 -> a2
  ...

他们的Applicative和 Monad实例都按索引组成元素。 Applicative 更容易显示直觉。 .下面，我们展示一个流 A的 a0, a1, ... , 和 B的 b0, b1, ... , 及其组成AB = liftA2 (+) A B ，以及功能的等效表示。

fStreamA  = Cons  a0     (Cons  a1     ...)
fStreamB  = Cons     b0  (Cons     b1  ...)
fStreamAB = Cons (a0+b0) (Cons (a1+b1) ...)
fStreamAB = liftA2 (+) fStreamA fStreamB

-- lambda case "\case" is sugar for "\x -> case x of"
fReaderA = \case 0 -> a0    ; 1 -> a1    ; ...
fReaderB = \case 0 ->    b0 ; 1 -> b1    ; ...
fReaderC = \case 0 -> a0+b0 ; 1 -> a1+b1 ; ...
fReaderC = liftA2 (+) fReaderA fReaderB = \i -> fReaderA i + fReaderB i

正式地

双射:

import Numeric.Natural  -- in the base library

-- It could also be Integer, there is a bijection Integer <-> Natural
type ReaderN a = Natural -> a

tailReader :: ReaderN a -> ReaderN a
tailReader r = \i -> r (i+1)

toStream :: ReaderN a -> Stream a
toStream r = Cons (r 0) (toStream (tailReader r))

fromStream :: Stream a -> ReaderN a
fromStream (Cons a s) = \i -> case i of
  0 -> a
  i -> fromStream s (i-1)

toStream和 fromStream是双射，这意味着它们满足以下方程:

toStream (fromStream s) = s :: Stream a
fromStream (toStream r) = r :: ReaderN a

“同构”是一个普遍的概念；两件事同构通常意味着存在满足某些方程的双射，这取决于所考虑的结构或界面。在这种情况下，我们讨论的是 monad 的结构，如果存在满足这些方程的双射，我们说两个 monad 是同构的:

toStream (return a) = return a
toStream (u >>= k) = toStream u >>= (toStream . k)

这个想法是，无论我们应用函数return，我们都会得到相同的结果。和 (>>=) “之前或之后”的双射。 (使用 fromStream 的类似方程可以从这两个方程和上面的其他两个方程导出)。