在Haskell中绘制部分函数的图表：a -> Maybe b -> [a] -> [(a, b)]

Question

在Haskell中绘制部分函数的图表：a -> Maybe b -> [a] -> [(a, b)]

9

给定一个部分函数 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 . (,))

- robx

3个回答

3

Hoogle没有返回<(a,m b) -> m (a,b)>的内容，所以我猜答案是否定的！但是我已经在本地实现了很多类似的函数。我能想到的最接近的预定义示例是 sequence。

sequence :: Monad m => [m a] -> m [a]

但是您仍然可以通过黑客方式取得胜利（使用Data.Maybe和Control.Arrow）：

graph f xs = map (second fromJust) $ filter (isJust . snd) $ zip xs $ map f xs

- Benesh

很遗憾，p a (m b) -> m (p a b) 或 p a (Maybe b) -> Maybe (p a b) 没有结果。 - robx

3

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和Foldable实例（它们在GHC 7.8中有）。以下是@robx提供的实例:

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

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

- David Young

很有前途！(,) a所需的Traversable实例是否已经定义在某个地方？以下代码对我有效：

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

- robx

@robx：您的建议修改是正确的，我不确定为什么会被拒绝。我已经进行了更改。无论如何，很抱歉，我没有注意到所需实例不在 GHC 的稳定版本中。我正在使用 GHC 7.8 RC，其中在 Data.Traversable 中的可遍历 (,) a 实例。您的定义与标准定义相同，因此应该可以正常工作。 - David Young

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Antal Spector-Zabusky · Accepted Answer

最简单的方法可能是使用列表推导式：

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有点晦涩（特别是如果您内联它的话），但这相当优雅。²

¹这只是列表单子的（稍有问题的）fail（或完全合理的mzero），它仅产生计算[]。

²正如您无法找到liftMaybe一样，我长时间以来也找不到preservingF。