流（无限列表）monad 模拟了哪些效果？
What effects are modeled by the stream (infinite list) monad?
monad 的各种实例模拟不同类型的效果：例如，Maybe 模拟偏向性，List 非确定性，Reader 只读状态。我想知道流数据类型（或无限列表或联合列表）的monad实例是否有这样一个直观的解释，data Stream a = Cons a (Stream a)（见下文其monad实例定义）。我在 few different occasions 上偶然发现了流 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
P.S.: 我不确定我的语言是否非常准确（尤其是在使用 "effect" 这个词时），请随时纠正我。
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 的直觉。下面，我们展示了 a0, a1, ... 的流 A 和 b0, b1, ... 的 B 及其组合 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
"Isomorphism"是一个普遍的概念；同构的两个事物通常意味着存在满足某些方程的双射，这取决于所考虑的结构或界面。在这种情况下，我们讨论的是单子的结构，如果存在满足以下方程的双射，我们就说两个单子是同构的：
toStream (return a) = return a
toStream (u >>= k) = toStream u >>= (toStream . k)
这个想法是，无论我们应用函数 return 和 (>>=) "before or after" 双射，我们都会得到相同的结果。 （然后可以从这两个方程和上面的其他两个方程中推导出使用 fromStream 的类似方程）。
@Li-yao Xia 的回答几乎涵盖了它，但如果它有助于您的直觉，请将 Stream monad 视为对并行计算的无限序列进行建模。 Stream 值本身是一个（无限）值序列，我可以使用 Functor 实例对序列中的所有值并行应用相同的函数； Applicative 实例将给定函数的 序列 应用于一系列值，逐点将每个函数应用于相应的值； Monad 实例将计算应用于序列中的每个值，结果可能取决于值及其在序列中的位置。
作为一些典型操作的例子，这里有一些示例序列加上一个Show-instance
instance (Show a) => Show (Stream a) where
show = show . take 10 . toList
nat = go 1 where go x = Cons x (go (x+1))
odds = go 1 where go x = Cons x (go (x+2))
给予：
> odds
[1,3,5,7,9,11,13,15,17,19]
> -- apply same function to all values
> let evens = fmap (1+) odds
> evens
[2,4,6,8,10,12,14,16,18,20]
> -- pointwise application of functions to values
> (+) <$> odds <*> evens
[3,7,11,15,19,23,27,31,35,39]
> -- computation that depends on value and structure (position)
> odds >>= \val -> fmap (\pos -> (pos,val)) nat
[(1,1),(2,3),(3,5),(4,7),(5,9),(6,11),(7,13),(8,15),(9,17),(10,19)]
>
此处 Applicative 和 Monadic 计算之间的区别类似于其他单子：应用操作具有静态结构，因为每个结果都取决于 a <*> b仅基于 a 和 b 中相应元素的值，与它们如何适应更大的结构（即它们在序列中的位置）无关；相比之下，单子操作可以具有依赖于基础值的结构，因此在表达式 as >>= f 中，对于 as 中的给定值 a，相应的结果可以依赖于两者关于特定值 a 和结构上它在序列中的位置（因为这将决定序列的哪个元素 f a 将提供结果）。
事实证明，在这种情况下，一元计算明显的额外普遍性并没有转化为任何实际额外的普遍性，正如你可以从最后一个例子中看到的那样以上相当于纯应用操作：
(,) <$> nat <*> odds
更一般地，给定一个单子动作 f :: a -> Stream b，总是可以将其写成：
f a = Cons (f1 a) (Cons (f2 a) ...))
对于适当定义的 f1 :: a -> b、f2 :: a -> b 等，之后我们将能够将单子操作表示为应用程序操作：
as >>= f = (Cons f1 (Cons f2 ...)) <*> as
将此与 List monad 中发生的情况进行对比：给定 f :: a -> List b，if 我们可以写：
f a = [f1 a, f2 a, ..., fn a]
（特别意味着结果中的元素数量将由 f 单独确定，而不管 a 的值如何），那么我们会遇到相同的情况：
as >>= f = as <**> [f1,...,fn]
并且每个单子列表操作都是一个基本的应用操作。
因此，并非所有有限列表的长度都相同这一事实使得 List monad 比其应用程序更强大，但因为所有（无限）序列 都是 相同的长度，Stream monad 不会在应用实例上添加任何内容。
monad 的各种实例模拟不同类型的效果：例如，Maybe 模拟偏向性，List 非确定性，Reader 只读状态。我想知道流数据类型（或无限列表或联合列表）的monad实例是否有这样一个直观的解释，data Stream a = Cons a (Stream a)（见下文其monad实例定义）。我在 few different occasions 上偶然发现了流 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
P.S.: 我不确定我的语言是否非常准确（尤其是在使用 "effect" 这个词时），请随时纠正我。
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 的直觉。下面，我们展示了 a0, a1, ... 的流 A 和 b0, b1, ... 的 B 及其组合 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
"Isomorphism"是一个普遍的概念；同构的两个事物通常意味着存在满足某些方程的双射，这取决于所考虑的结构或界面。在这种情况下，我们讨论的是单子的结构，如果存在满足以下方程的双射，我们就说两个单子是同构的：
toStream (return a) = return a
toStream (u >>= k) = toStream u >>= (toStream . k)
这个想法是，无论我们应用函数 return 和 (>>=) "before or after" 双射，我们都会得到相同的结果。 （然后可以从这两个方程和上面的其他两个方程中推导出使用 fromStream 的类似方程）。
@Li-yao Xia 的回答几乎涵盖了它，但如果它有助于您的直觉，请将 Stream monad 视为对并行计算的无限序列进行建模。 Stream 值本身是一个（无限）值序列，我可以使用 Functor 实例对序列中的所有值并行应用相同的函数； Applicative 实例将给定函数的 序列 应用于一系列值，逐点将每个函数应用于相应的值； Monad 实例将计算应用于序列中的每个值，结果可能取决于值及其在序列中的位置。
作为一些典型操作的例子，这里有一些示例序列加上一个Show-instance
instance (Show a) => Show (Stream a) where
show = show . take 10 . toList
nat = go 1 where go x = Cons x (go (x+1))
odds = go 1 where go x = Cons x (go (x+2))
给予：
> odds
[1,3,5,7,9,11,13,15,17,19]
> -- apply same function to all values
> let evens = fmap (1+) odds
> evens
[2,4,6,8,10,12,14,16,18,20]
> -- pointwise application of functions to values
> (+) <$> odds <*> evens
[3,7,11,15,19,23,27,31,35,39]
> -- computation that depends on value and structure (position)
> odds >>= \val -> fmap (\pos -> (pos,val)) nat
[(1,1),(2,3),(3,5),(4,7),(5,9),(6,11),(7,13),(8,15),(9,17),(10,19)]
>
此处 Applicative 和 Monadic 计算之间的区别类似于其他单子：应用操作具有静态结构，因为每个结果都取决于 a <*> b仅基于 a 和 b 中相应元素的值，与它们如何适应更大的结构（即它们在序列中的位置）无关；相比之下，单子操作可以具有依赖于基础值的结构，因此在表达式 as >>= f 中，对于 as 中的给定值 a，相应的结果可以依赖于两者关于特定值 a 和结构上它在序列中的位置（因为这将决定序列的哪个元素 f a 将提供结果）。
事实证明，在这种情况下，一元计算明显的额外普遍性并没有转化为任何实际额外的普遍性，正如你可以从最后一个例子中看到的那样以上相当于纯应用操作：
(,) <$> nat <*> odds
更一般地，给定一个单子动作 f :: a -> Stream b，总是可以将其写成：
f a = Cons (f1 a) (Cons (f2 a) ...))
对于适当定义的 f1 :: a -> b、f2 :: a -> b 等，之后我们将能够将单子操作表示为应用程序操作：
as >>= f = (Cons f1 (Cons f2 ...)) <*> as
将此与 List monad 中发生的情况进行对比：给定 f :: a -> List b，if 我们可以写：
f a = [f1 a, f2 a, ..., fn a]
（特别意味着结果中的元素数量将由 f 单独确定，而不管 a 的值如何），那么我们会遇到相同的情况：
as >>= f = as <**> [f1,...,fn]
并且每个单子列表操作都是一个基本的应用操作。
因此，并非所有有限列表的长度都相同这一事实使得 List monad 比其应用程序更强大，但因为所有（无限）序列 都是 相同的长度，Stream monad 不会在应用实例上添加任何内容。