7

我有这样的seperateFuncs功能

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

我想知道是否存在相反的情况，即是否有功能

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

我认为不是（主要是因为列表不是固定长度的），但也许我会被证明是错误的。那么问题是有一些数据类型f具有函数 :: (a -> fb) -> f (a -> b) 吗？

4

5 回答 5

7

您可以非常干净地概括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 a -> f b) -> f (a -> b)为任何f不像(->).

于 2012-12-07T17:45:10.313 回答
4

首先，你可以暴力破解这个功能：

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

但这显然很麻烦 - 结果列表始终是无限的，但仅使用 succeds if评估第ith 个元素。xlength(f x) > i

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

那么问题是有一些f具有功能的数据类型:: (a -> f b) -> f (a -> b)吗？

考虑(->)c。这样，您的签名读取(a -> (c->b)) -> (c->(a->b))或等效地(a -> c -> b) -> c -> a -> b，事实证明，只是flip.

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

于 2012-12-07T15:26:45.537 回答
3

“是否有一些数据类型 f 具有函数 :: (a -> fb) -> 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必须是 Traversable 的约束——并且没有用于 的 Traversable 实例(->) a，这意味着通常无法使用函数完成此操作。尽管请注意“其他方向” -f (a -> b) -> (a -> f b)适用于所有功能和所有 Applicatives f。

于 2012-12-07T18:10:37.590 回答
3

我最近不得不考虑很多与您的问题非常相似的问题。这是我发现的概括。

首先，这样做很简单（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之间就没有区别。为什么？好吧，我不是 100% 遵循它，但它是这样的：是带有一个参数的非常常见的一元动作类型，而也是非常常见的类型，因为不知道正确的名称，我会调用“适用的应用程序”。可以做不能做的事情的事实与不存在的事实联系在一起。ApplicativeMonadMonad m => a -> m bApplicative f => f (a -> b)MonadApplicativem2a

所以现在，适用于您的问题：

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

我怀疑同样的“Monad /= Applicative”论点（再次强调，我不完全理解）应该适用于此。我们知道Monad []实例可以做实例不能做的事情Applicative []。如果您可以joinFuncs使用指定类型编写 a ，那么与参数[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

请注意，除了我们枚举as 的要求之外，一个有趣的观察是，要做到这一点，我们必须在某种意义上“实现”结果；把它从一个函数/动作变成某种列表、地图或表格。

于 2012-12-07T19:29:11.710 回答
0

问题“我可以使用类型签名的函数joinFuncs :: (a -> [b]) -> [a -> b]是不完整的，并且没有说明您希望此函数满足哪些法律。没有法律，您可以通过定义joinFuncs _ = []（总是返回一个空列表）来解决这个问题。这个平凡的函数满足所需的类型签名但很可能没用。

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

这种类型签名的一个更一般的情况是一些函子(a -> f b) -> f (a -> b)在哪里。f我称这样的函子为“刚性的”。看到这个问题函子的这个属性比单子强吗？ 更多细节。

所有刚性函子都R满足类型R ()只有一个不同值的性质，即它等价于()。这让我们立即看到List函子不是刚性的，因为List ()不等价于().

刚性函子最简单的重要示例是type R a = (a -> p) -> awherep是一个固定类型。R以这种方式定义的函子实际上是一个刚性 monad。

于 2019-06-26T01:31:46.383 回答