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

Question

monad的各种实例模拟不同类型的效果:例如,Maybe模型偏好,List非确定性,Reader只读状态.我想知道是否对流数据类型(或无限列表或共同列表)的monad实例有这样一个直观的解释data Stream a = Cons a (Stream a)(参见下面的monad实例定义).我在几个 不同的 场合偶然发现了流monad ,我想更好地了解它的用途.

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

PS:我不确定我的语言是否非常精确(尤其是在使用"效果"这个词时),所以请随意纠正我.

Answer 1

该Stream单子是同构的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:

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)

A并且a0, a1, ...是双射,意味着他们满足这些方程式:

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)

我们的想法是,无论我们是否应用这些函数B以及b0, b1, ..."在双射之前或之后" ,我们都会得到相同的结果.(AB = liftA2 (+) A B然后可以从这两个方程和上面的另外两个方程导出使用的类似方程).