Haskell中部分函数的图:a - >也许b - > [a] - > [(a,b)]

Question

鉴于部分功能f和参数列表xs,我找对的列表(x, f(x)),其中f定义.这似乎是一件很自然的事情,但到目前为止我还没有优雅地表达出来.我想知道在Maybe/Monad/Applicative/...区域中是否有任何可以帮助的东西？以下作品,但似乎有点明确.

import Data.Maybe (mapMaybe)

graph :: (a -> b) -> [a] -> [(a, b)]
graph f = map (\x -> (x, f x))

liftMaybe :: (a, Maybe b) -> Maybe (a, b)
liftMaybe (x, Just y)  = Just (x, y)
liftMaybe (_, Nothing) = Nothing

partialgraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialgraph f = mapMaybe liftMaybe . graph f

是否liftMaybe存在其他名称？我发现其中一些重新制定:

import Control.Monad (ap)

graph' :: (a -> b) -> [a] -> [(a, b)]
graph' = map . ap (,)

liftMaybe' :: (a, Maybe b) -> Maybe (a, b)
liftMaybe' (a, mb) = do
    b <- mb
    return (a, b)

liftMaybe'' :: (a, Maybe b) -> Maybe (a, b)
liftMaybe'' (a, mb) = fmap ((,) a) mb

liftMaybe''' :: (a, Maybe b) -> Maybe (a, b)
liftMaybe''' = uncurry (fmap . (,))

Answer 1

最简单的方法可能是使用列表理解:

partialGraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialGraph f xs = [(x, fx) | (x, Just fx) <- graph f xs]

这利用了列表推导中模式匹配的失败语义:如果模式匹配失败,则跳过该列表元素.¹

例如,

ghci> partialGraph (\x -> if even x then Just $ x `quot` 2 else Nothing) [1..10]
[(2,1),(4,2),(6,3),(8,4),(10,5)]

似乎没有liftSnd :: Functor f => (a, f b) -> f (a,b)任何地方定义的功能; uncurry $ fmap . (,)就像你要得到的一样简洁.

如果你定义

preservingF :: Functor f => (a -> f b) -> a -> f (a, b)
preservingF = liftA2 fmap (,)

那么你可以用这个函数来定义

partialGraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialGraph = mapMaybe . preservingF

这是相当优雅的,虽然定义preservingF有点不透明(特别是如果你内联它).²

¹这只是列表monad 的(有点可疑)fail(或完全合理的mzero),它只是产生计算[].

²就像你一直无法找到的那样liftMaybe,我已经找不到preservingF很久了.

Answer 2

最简单的定义liftMaybe是

import Data.Traversable (sequenceA)

liftMaybe :: (a, Maybe b) -> Maybe (a, b)
liftMaybe = sequenceA

sequenceA可以在此处找到文档http://hackage.haskell.org/package/base/docs/Data-Traversable.html。

一般类型签名是sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)，但在本例中t是(,) c和f是Maybe。

另外，partialgraph可以用traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)（也来自Data.Traversable）来表达：

partialgraph :: (a -> Maybe b) -> [a] -> [(a, b)]
partialgraph f = mapMaybe $ \x -> traverse f (x, x)

或者，如果你更喜欢毫无意义的话：

partialgraph f = mapMaybe (traverse f . join (,))

编辑：当我写这个答案时，我没有意识到GHC 7.6.3 标准库中没有定义必需的Traversable和实例（尽管它们在 GHC 7.8 中）。Foldable这是@robx 提供的：

instance Foldable ((,) a) where
  foldr f y (u, x) = f x y

instance Traversable ((,) a) where
  traverse f (u, x) = (,) u <$> f x