Monads:确定是否可以进行任意转换
Monads: Determining if an arbitrary transformation is possible
这里有 quite a few 个关于涉及 Monad 的类型转换是否可能的问题。
例如,可以创建类型为 f :: Monad m => [m a] -> m [a]
的函数,但不可能创建类型为 g :: Monad m => m [a] -> [m a]
的函数作为前者的反函数。 (即:f . g = id
)
我想了解可以使用哪些规则来确定是否可以构造该类型的函数,以及如果这些类型不遵守这些规则,为什么不能构造它们。
如果你看一下"Monad laws",monad只限制你定义一个组合函数而不是反向函数。
在第一个示例中,您可以组合列表元素。
在第二个Monad m => m [a] -> [m a]
中,您不能将一个动作拆分为多个动作(动作组合不可逆)。
示例:
假设您必须读取 2 个值。
s1 <- action
s2 <- action
这样做,动作结果s2取决于s1的副作用。
您可以将这 2 个操作绑定到 1 个操作中以按相同的顺序执行,但是您不能将它们拆分并从 s2 执行操作,而 s1 不会产生第二个操作所需的副作用。
不是真正的答案,对于我的链接来说过于非正式,但尽管如此,我还是有一些有趣的观察结果不适合发表评论。首先,让我们考虑一下您提到的这个功能:
f :: Monad m => [m a] -> m [a]
这个签名实际上比它需要的更强大。目前对此的概括是来自 Data.Traversable
:
的 sequenceA
函数
sequenceA :: (Traversable t, Applicative f) -> t (f a) -> f (t a)
...不需要 Monad
的全部功能,并且可以与任何 Traversable
一起使用,而不仅仅是列表。
其次:我认为 Traversable
只需要 Applicative
这一事实对这个问题非常重要,因为应用计算具有 "list-like" 结构。对于某些 f
,每个应用计算都可以重写为 f <$> a1 <*> ... <*> an
的形式。或者,非正式地,每个应用计算都可以看作是一个动作列表 a1, ... an
(在结果类型上是异质的,在函子类型上是同质的),加上一个 n 位函数来组合它们的结果。
如果我们通过这个镜头看 sequenceA
,它所做的只是选择一个 f
构建出适当嵌套数量的列表构造函数:
sequenceA [a1, ..., an] == f <$> a1 <*> ... <*> an
where f v1 ... vn = v1 : ... : vn : []
现在,我还没有机会尝试证明这一点,但我的推测如下:
- 至少从数学上讲,
sequenceA
有一个 left inverse in free applicative functors。如果你有一个 Functor f => [FreeA f a]
并且你 sequenceA
它,你得到的是一个类似列表的结构,其中包含这些计算和一个组合函数,该函数将计算结果制成一个列表。但是我怀疑不可能在 Haskell (unSequenceFreeA :: (Traversable t, Functor f) => FreeA f (t a) -> Maybe (t (Free f a))
) 中编写这样的函数,因为您无法在 FreeA
中的组合函数的结构上进行模式匹配来告诉它它的形式是 f v1 ... vn = v1 : ... : vn : []
.
然而,sequenceA
在自由应用程序中没有右逆,因为从 a1, ... an
操作的结果中生成列表的组合函数可能会做任何事情;例如,return 任意长度的常量列表(与自由应用值执行的计算无关)。
- 一旦你转向非自由应用函子,
sequenceA
将不再有左逆,因为非自由应用函子的方程转化为你无法再区分哪一个的情况两个 t (f a)
"action lists" 是给定 f (t a)
"list-producing action." 的来源
我一直认为 monad 的方式是 Monad m => m a
类型的值是一些 m
类型的程序,它执行并产生 a
。 monad laws 通过将这些程序的组合视为 "do thing one then do thing two" 来强化这一概念,并产生某种结果组合。
正确的单位 获取一个程序并 returning 它的值应该
与 运行 原始程序相同。
m >>= return = m
左单元 如果你创建一个简单的程序,只是 return 一个值,
然后将该值传递给创建新程序的函数,然后
生成的程序应该就像您在
值。
return x >>= f = f x
关联性 如果你执行一个程序m
,将它的结果输入一个函数f
产生另一个程序,然后将该结果输入到第三个函数 g
中,该函数也生成一个程序,然后这与创建一个新函数相同,该函数 return 是一个基于将 f
的结果输入 [=15] 的程序=],并将m
的结果输入其中。
(m >>= f) >>= g = m >>= (\x -> f x >>= g)
使用这种关于 "program that creates a value" 的直觉可以得出一些关于它对您在示例中提供的函数意味着什么的结论。
Monad m => [m a] -> m [a]
偏离这个函数应该做什么的直观定义是困难的:按顺序执行每个程序并收集结果。这会产生另一个产生结果列表的程序。
Monad m => m [a] -> [m a]
这并没有一个明确直观的定义,因为它是一个生成列表的程序。您无法在无法访问结果值的情况下创建列表,在本例中这意味着执行程序。某些 monad,有一个清晰的方法从程序中提取一个值,并提供 m a -> a
的一些变体,比如 State
monad,可以像这样有一些功能的合理实现。它必须是特定于应用程序的。其他单子,比如 IO
,你无法逃脱。
Monad m => (a -> m b) -> m (a -> b)
这也没有一个明确直观的定义。这里你有一个函数 f
生成一个类型 m b
的程序,但你试图 return 一个类型 m (a -> b)
的函数。在a
的基础上,f
创建了具有不同执行语义的完全不同的程序。即使您可以在程序结果值中提供 a -> b
的适当映射,您也不能将这些变体包含在类型为 m (a -> b)
的单个程序中。
这种直觉并没有真正完全包含 monad 背后的思想。例如,列表的 monadic 上下文并不真正像一个程序。
一些容易记住的东西是:"you can't escape from a Monad"(这是一种设计)。将 m [a]
转换为 [m a]
是一种逃避形式,所以你不能。
另一方面,您可以轻松地从某物创建 Monad(使用 return
),因此 遍历 ([m a] -> m [a]
) 通常是可能的。
这里有 quite a few 个关于涉及 Monad 的类型转换是否可能的问题。
例如,可以创建类型为 f :: Monad m => [m a] -> m [a]
的函数,但不可能创建类型为 g :: Monad m => m [a] -> [m a]
的函数作为前者的反函数。 (即:f . g = id
)
我想了解可以使用哪些规则来确定是否可以构造该类型的函数,以及如果这些类型不遵守这些规则,为什么不能构造它们。
如果你看一下"Monad laws",monad只限制你定义一个组合函数而不是反向函数。
在第一个示例中,您可以组合列表元素。
在第二个Monad m => m [a] -> [m a]
中,您不能将一个动作拆分为多个动作(动作组合不可逆)。
示例:
假设您必须读取 2 个值。
s1 <- action
s2 <- action
这样做,动作结果s2取决于s1的副作用。 您可以将这 2 个操作绑定到 1 个操作中以按相同的顺序执行,但是您不能将它们拆分并从 s2 执行操作,而 s1 不会产生第二个操作所需的副作用。
不是真正的答案,对于我的链接来说过于非正式,但尽管如此,我还是有一些有趣的观察结果不适合发表评论。首先,让我们考虑一下您提到的这个功能:
f :: Monad m => [m a] -> m [a]
这个签名实际上比它需要的更强大。目前对此的概括是来自 Data.Traversable
:
sequenceA
函数
sequenceA :: (Traversable t, Applicative f) -> t (f a) -> f (t a)
...不需要 Monad
的全部功能,并且可以与任何 Traversable
一起使用,而不仅仅是列表。
其次:我认为 Traversable
只需要 Applicative
这一事实对这个问题非常重要,因为应用计算具有 "list-like" 结构。对于某些 f
,每个应用计算都可以重写为 f <$> a1 <*> ... <*> an
的形式。或者,非正式地,每个应用计算都可以看作是一个动作列表 a1, ... an
(在结果类型上是异质的,在函子类型上是同质的),加上一个 n 位函数来组合它们的结果。
如果我们通过这个镜头看 sequenceA
,它所做的只是选择一个 f
构建出适当嵌套数量的列表构造函数:
sequenceA [a1, ..., an] == f <$> a1 <*> ... <*> an
where f v1 ... vn = v1 : ... : vn : []
现在,我还没有机会尝试证明这一点,但我的推测如下:
- 至少从数学上讲,
sequenceA
有一个 left inverse in free applicative functors。如果你有一个Functor f => [FreeA f a]
并且你sequenceA
它,你得到的是一个类似列表的结构,其中包含这些计算和一个组合函数,该函数将计算结果制成一个列表。但是我怀疑不可能在 Haskell (unSequenceFreeA :: (Traversable t, Functor f) => FreeA f (t a) -> Maybe (t (Free f a))
) 中编写这样的函数,因为您无法在FreeA
中的组合函数的结构上进行模式匹配来告诉它它的形式是f v1 ... vn = v1 : ... : vn : []
.
然而, sequenceA
在自由应用程序中没有右逆,因为从a1, ... an
操作的结果中生成列表的组合函数可能会做任何事情;例如,return 任意长度的常量列表(与自由应用值执行的计算无关)。- 一旦你转向非自由应用函子,
sequenceA
将不再有左逆,因为非自由应用函子的方程转化为你无法再区分哪一个的情况两个t (f a)
"action lists" 是给定f (t a)
"list-producing action." 的来源
我一直认为 monad 的方式是 Monad m => m a
类型的值是一些 m
类型的程序,它执行并产生 a
。 monad laws 通过将这些程序的组合视为 "do thing one then do thing two" 来强化这一概念,并产生某种结果组合。
正确的单位 获取一个程序并 returning 它的值应该 与 运行 原始程序相同。
m >>= return = m
左单元 如果你创建一个简单的程序,只是 return 一个值, 然后将该值传递给创建新程序的函数,然后 生成的程序应该就像您在 值。
return x >>= f = f x
关联性 如果你执行一个程序
m
,将它的结果输入一个函数f
产生另一个程序,然后将该结果输入到第三个函数g
中,该函数也生成一个程序,然后这与创建一个新函数相同,该函数 return 是一个基于将f
的结果输入 [=15] 的程序=],并将m
的结果输入其中。(m >>= f) >>= g = m >>= (\x -> f x >>= g)
使用这种关于 "program that creates a value" 的直觉可以得出一些关于它对您在示例中提供的函数意味着什么的结论。
Monad m => [m a] -> m [a]
偏离这个函数应该做什么的直观定义是困难的:按顺序执行每个程序并收集结果。这会产生另一个产生结果列表的程序。Monad m => m [a] -> [m a]
这并没有一个明确直观的定义,因为它是一个生成列表的程序。您无法在无法访问结果值的情况下创建列表,在本例中这意味着执行程序。某些 monad,有一个清晰的方法从程序中提取一个值,并提供m a -> a
的一些变体,比如State
monad,可以像这样有一些功能的合理实现。它必须是特定于应用程序的。其他单子,比如IO
,你无法逃脱。Monad m => (a -> m b) -> m (a -> b)
这也没有一个明确直观的定义。这里你有一个函数f
生成一个类型m b
的程序,但你试图 return 一个类型m (a -> b)
的函数。在a
的基础上,f
创建了具有不同执行语义的完全不同的程序。即使您可以在程序结果值中提供a -> b
的适当映射,您也不能将这些变体包含在类型为m (a -> b)
的单个程序中。
这种直觉并没有真正完全包含 monad 背后的思想。例如,列表的 monadic 上下文并不真正像一个程序。
一些容易记住的东西是:"you can't escape from a Monad"(这是一种设计)。将 m [a]
转换为 [m a]
是一种逃避形式,所以你不能。
另一方面,您可以轻松地从某物创建 Monad(使用 return
),因此 遍历 ([m a] -> m [a]
) 通常是可能的。