Haskell函数：从（a -> [b]）-> [a -> b]

Question

我有一个名为separateFuncs的函数，它如下所示：

seperateFuncs :: [a -> b] -> (a -> [b])
seperateFuncs xs = \x -> map ($ x) xs

我在想是否存在相反的情况，也就是说是否存在这样的函数

joinFuncs :: (a -> [b]) -> [a -> b]

我认为不行（主要是因为列表长度不固定），但也许我会被证明是错的。 问题是是否存在某种数据类型 f，它具有函数 :: (a -> f b) -> f (a -> b)？

- walpen

---

除了平凡解决方案，我猜没有其他的了。 - Don Stewart

有一个针对无限列表和已知长度元组的函数。基本上，输出的第i个元素是输入的第i个投影。 - n. m.

另一个解释可能来自于 Applicative f => Monad f：每个 f (a -> b) 都可以转换为 (a -> f b)，但不一定反过来（此外，你可以通过 (=<<) :: (a -> f b) -> (f a -> f b) 的方式实现 (<*>) :: f (a -> b) -> (f a -> f b)，但并非总是如此）。虽然对此不太确定。 - user824425

Answer 1

你可以将seperateFuncs相对容易地推广到Applicative（或Monad）：

seperateFuncs :: (Applicative f) => f (a -> b) -> (a -> f b)
seperateFuncs f x = f <*> pure x

使用点无风格编写，您有 seperateFuncs = ((. pure) . (<*>))，因此您基本上希望使用以下定义 unap . (. extract) 以点有风格的方式书写。

joinFuncs :: (Unapplicative f) => (a -> f b) -> f (a -> b)
joinFuncs f = unap f (\ g -> f (extract g))

这里我将Unapplictaive定义为：

class Functor f => Unapplicactive f where
    extract  :: f a -> a
    unap     :: (f a -> f b) -> f (a -> b)

要获取由leftaroundabout提供的定义，您可以给出以下实例：

instance Unapplicative [] where
    extract = head
    unap f = [\a -> f [a] !! i | i <- [0..]]

instance Unapplicative ((->) c) where
    extract f = f undefined
    unap f = \x y -> f (const y) x

我认为很难为任何不像(->)的f提供一个“有用”的函数f :: (f a -> f b) -> f (a -> b)。

- user824425

---

顺便说一下，在与Matt Fenwick的答案相同的要点中：你可以将coap视为g(f a)(f b)-> f(g a b)的实例，就像sequenceA一样，你正在“转置”一个函子(f)和一个双函子((->))。 - user824425

Answer 2

首先，你可以尝试使用暴力破解方法来解决这个函数：

joinFuncs f = [\x -> f x !! i | i<-[0..]]

但这显然是有问题的——所得到的列表总是无限的，但只有当length(f x) > i时，用x求第i个元素才会成功。

为了给出一个“真正”的解决方案：

问题是是否存在某种数据类型f，它具有函数:: (a -> f b) -> f (a -> b)？

考虑到(->)c，那么你的签名是(a -> (c->b)) -> (c->(a->b))，或者等效于(a -> c -> b) -> c -> a -> b，而这恰好是flip。

当然，这有点微不足道，因为这种类型对于seperateFuncs来说具有相同的签名...

- leftaroundabout

Answer 3

是否存在某种数据类型 f，它具有函数 :: (a -> f b) -> f (a -> b)？

事实上，在 Traversable 类型类中还有一个更通用的版本，它处理可交换的函子：

class (Functor t, Foldable t) => Traversable t where

  ... 

  sequenceA :: Applicative f => t (f b) -> f (t b)

这与您的函数有什么关系？从您的类型开始，进行一次类型替换后，我们就可以恢复出sequenceA:

1. (a -> f b) -> f (a -> b) ==> let t = (->) a
2. t (f b) -> f (t b)

然而，这种类型需要约束条件，即t必须是可遍历的——对于(->) a没有可遍历的实例，这意味着通常情况下无法使用此操作来处理函数。尽管请注意，“另一个方向”——f (a -> b) -> (a -> f b)适用于所有函数和所有应用程序f。

- Matt Fenwick

Answer 4

最近我不得不思考一些与你的问题非常相似的问题。以下是我发现的概括。

首先，像Tinctorius指出的那样，这很容易做到：

f2m :: Functor f => f (a -> b) -> a -> f b
f2m f a = fmap ($a) f

但是一般情况下这是不可能做到的：

m2a :: Monad m => (a -> m b) -> m (a -> b)

有一种深刻的理解方式是，有人在 #haskell irc 频道中很好地向我解释了，如果存在一个 m2a 函数，则 Applicative 和 Monad 没有区别。为什么呢？嗯，我不完全明白，但大概是这样的：Monad m => a -> m b 是具有一个参数的常见 monadic 操作类型，而 Applicative f => f (a -> b) 则是所谓的 “可应用 applicatives”的另一种常见类型（由于不知道正式名称，称之为“可适用applicatives”）。Monad 可以做到 Applicative 做不到的事情，这与 m2a 无法存在有关。

现在，应用到你的问题上：

joinFuncs :: (a -> [b]) -> [a -> b]

我怀疑同样的“Monad /= Applicative”论点（再次强调，我不完全理解）应该适用于这里。我们知道Monad []实例可以做Applicative []实例无法做到的事情。如果您可以写一个指定类型的joinFuncs，那么[a -> b]的结果在某种意义上必须与a -> [b]的参数“失去信息”，因为否则Applicative []将与Monad []相同。（通过“失去”信息，我的意思是任何具有joinFuncs类型的函数都不能具有反函数，因此它保证消除一些函数对f, g :: a -> [b]之间的区别。极端情况是joinFuncs = undefined。）

我发现我需要类似m2a的函数。所以我发现的特殊情况是可以这样做：

import Data.Map (Map)
import qualified Data.Map as Map

-- | Enumerate a monadic action within the domain enumerated by the 
-- argument list.
boundedM2a :: Monad m => (a -> m b) -> [a] -> m [(a,b)]
boundedM2a f = mapM f'
    where f' a = do b <- f a
                    return (a, b)

-- | The variant that makes a 'Map' is rather useful.
boundedM2a' :: (Monad m, Ord a) => (a -> m b) -> [a] -> m (Map a b)
boundedM2a' f = liftM Map.fromList . boundedM2a f

请注意，除了我们需要枚举 a 的要求之外，有趣的观察结果是，为了做到这一点，我们必须在某种意义上“实现”结果；将其从函数/操作转化为列表、映射或表格。

- Luis Casillas

---

Applicatives commute, Monads might not. - Matt Fenwick

如果一个应用函子F有自然变换(a -> F b) -> F(a -> b)，那么F就自动地成为一个单子，并且具有(a -> F b) -> F a -> F b。这是因为应用函子有 F(a -> b) -> F a -> F b。因此，自然变换(a -> F b) -> F(a -> b)不能是所有应用函子的普遍属性--否则所有应用函子都将成为单子。 - winitzki

Answer 5

问题“我能否拥有类型签名为joinFuncs :: (a -> [b]) -> [a -> b]的函数”是不完整的，如果没有说明您希望这个函数满足什么规律。如果没有规律，您可以通过定义joinFuncs _ = []（始终返回一个空列表）来解决此问题。这个微不足道的函数满足所需的类型签名，但很可能是无用的。

要求joinFuncs有用的一种方法是强制执行非退化法则separateFuncs . joinFuncs == id。然后可以证明，对于这种类型签名，实现joinFuncs是不可能的。

这种类型签名的更一般情况是(a -> f b) -> f (a -> b)，其中f是某个函子。我称这样的函子为“刚性”。有关详细信息，请参见此问题Is this property of a functor stronger than a monad?。

所有刚性函子 R 都满足这样的特性，即类型 R () 只有一个不同的值，即等同于 ()。这使我们能够立即看到 List 函子不是刚性的，因为 List () 不等同于 ()。

最简单的非平凡刚性函子示例是 type R a = (a -> p) -> a，其中 p 是一种固定类型。以这种方式定义的函子 R 实际上是一种刚性单子（rigid monad）。

- winitzki