Haskell中的Unsequence Monad函数

Question

我在设计Haskell sequence函数的反函数时遇到了一些麻烦,Hoogle告诉我该函数尚不存在.这是它的行为方式:

ghci> sequence [Just 7, Just 8, Just 9]
Just [7,8,9]
ghci> sequence [getLine, getLine, getLine]
hey
there
stack exchange
["hey","there","stack exchange"] :: IO [String]

我的问题是制作这样的函数:

unsequence :: (Monad m) => m [a] -> [m a]

所以它的行为如下:

ghci> unsequence (Just [7, 8, 9])
[Just 7, Just 8, Just 9]
ghci> sequence getLine
hey
['h','e','y'] :: [IO Char] --(This would actually cause an error, but hey-ho.)

我实际上并不知道这是否可能,因为我会在某些时候逃避monad,但我已经开始了,虽然我不知道如何为这个递归函数设置断点:

unsequence m = (m >>= return . head) : unsequence (m >>= return . tail)

我意识到当m这里等于时我需要一个断点return [],但不是所有的monad都有Eq实例,所以我怎么能这样做呢？这甚至可能吗？如果是这样,为什么不呢？请告诉我.

Answer 1

你不能拥有unsequence :: (Monad m) => m [a] -> [m a].问题在于列表:您无法确定列表中的元素是如何获得的,这会使任何合理的定义复杂化unsequence.

有趣的是,如果你是绝对的,100%确定monad中的列表是无限的,你可以这样写:

unsequenceInfinite :: (Monad m) => m [a] -> [m a]
unsequenceInfinite x = fmap head x : unsequenceInfinite (fmap tail x)

它会工作!

还想象一下,我们Pair周围有一个仿函数.我们可以写unsequencePair为

unsequencePair :: (Monad m) => m (Pair a) -> Pair (m a)
unsequencePair x = Pair (fmap firstPairElement x) (fmap secondPairElement x)

一般来说,事实证明,您只能unsequence为具有属性的仿函数定义,您可以始终将两个值"压缩"在一起而不会丢失信息.无限列表(在Haskell中,它们的一种可能类型Cofree Identity)就是一个例子.该Pair函子是另一回事.但不是传统的列表,或者像Maybe或者类似的函子Either.

在distributive包中,有一个名为的类型类Distributive封装了这个属性.你unsequence被称为distribute那里.

Answer 2

确实不可能unsequence单独使用monad 创建函数.原因是:

1. 您可以使用值安全轻松地创建monadic结构return.
2. 但是,从monadic结构中删除值是不安全的.例如,您无法从空列表中删除元素(即该类型的函数[a] -> a不安全).
3. 因此,我们有一个特殊的函数(即>>=),它可以安全地从monadic结构中删除一个值(如果存在),处理它并返回另一个安全的monadic结构.

因此,从值创建monadic结构是安全的.但是从monadic结构中删除值是不安全的.

假设我们有一个extract :: Monad m => m a -> a可以"安全地"从monadic结构中删除一个值的函数.然后我们可以实现unsequence如下:

unsequence :: Monad m => m [a] -> [m a]
unsequence = map return . extract

但是,没有一种安全的方法可以从monadic结构中提取值.因此unsequence [],unsequence Nothing将返回undefined.

但是,您可以unsequence为monadic和comonadic的结构创建一个函数.A Comonad的定义如下:

class Functor w => Comonad w where
    extract   :: w a -> a
    duplicate :: w a -> w (w a)
    extend    :: (w a -> b) -> w a -> w b

    duplicate = extend id
    extend f = fmap f . duplicate

一个共同结构与一元结构相反.特别是:

1. 您可以安全地从comonadic结构中提取值.
2. 但是,您无法从值安全地创建新的comonadic结构,这就是duplicate函数从值安全地创建新的comonadic结构的原因.

请记住,unsequence所需的定义return和extract？您无法从值安全地创建新的comonadic结构(即comonadic结构没有return).因此,该unsequence功能定义如下:

unsequence :: (Comonad m, Monad m) => m [a] -> [m a]
unsequence = map return . extract

有趣的sequence是,它只适用于单一结构.所以通过直觉你可以假设unsequence它只适用于简单的结构.但事实并非如此,因为您需要首先从comonadic结构中提取列表,然后将列表的每个元素放入monadic结构中.

该unsequence函数的通用版本将comonadic列表结构转换为monadic结构列表:

unsequence :: (Comonad w, Monad m) => w [a] -> [m a]
unsequence = map return . extract

另一方面,该sequence函数仅适用于monadic结构,因为您只是通过链接所有monad将monadic结构列表折叠成monadic列表结构:

import Control.Monad (liftM2)

sequence :: Monad m => [m a] -> m [a]
sequence = foldr (liftM2 (:)) (return [])

希望有所帮助.