迭代 Data.Set 直到成功

Question

假设我有一个函数代表一些可能会失败的计算

f :: a -> Maybe b

如果我有一个列表 l，我可以使用 findList f l 在列表中找到 f 成功的第一个（当从左到右扫描时）项目，其中findList是下面的函数

findList :: (a -> Maybe b) -> [a] -> Maybe b
findList f [] = Nothing
findList f (x : xs) = case f x of
  Nothing -> findList f xs
  Just y -> Just y

（或使用 extra 包中的 firstJust）。

问题。

如果我想用来自 containers 的 Set 做同样的事情，我该怎么办？

也就是我想要一个带签名的函数

findSet :: (a -> Maybe b) -> Set a -> Maybe b

相当于

findSet f s = findList f (Set.toList s)

上面的行作为一个实现。但是，我不想创建中间列表 Set.toList s（即使使用惰性求值，仍然会有一些不必要的开销，对吧？）。

我也不想在找到成功的项目后遍历整个集合，如以下实现所示：

findSet f s = foldl g Nothing s
  where
    g Nothing x = f x
    g (Just y) _ = Just y

那么有没有一种“从左到右”遍历集合、对每个成员应用可能会失败的计算并在第一个成功结果处停止的好方法？

Answer 1

您可以处理 Set 是 Foldable 的实例这一事实。因此，您可以通过以下方式实现 Fold 函数：

import Control.Applicative((<|>))

findSet :: (a -> Maybe b) -> Set a -> Maybe b
findSet f = foldr (<b>(<|>) . f</b>) Nothing

这实际上适用于 Foldable:

的所有实例

import Control.Applicative((<|>))

findSet :: (Alternative g, Foldable f) => (a -> g b) -> f a -> g b
findSet f = foldr (<b>(<|>) . f</b>) Nothing

或 , we can make use of First，因为 First 将 select 第一个 Just，因此可以与：

一起使用

import Control.Applicative((<|>))

findSet :: Foldable f => (a -> Maybe b) -> f a -> Maybe b
findSet f = getFirst . foldMap (First . f)

toList的实现也是Foldable方面的实现：

toList :: Foldable f => f a -> [a]
toList = foldr <b>(:)</b> []

所以我们在这里做的不是先将它包装在一个 cons 中然后打开它，而是立即应用 f 并使用 (<|>) :: Alternate f => f a -> f a -> f a.

的实现

Answer 2

我想分享一个 IRC 上有人教给我的小技巧：成功时提前退出只是错误时提前退出的另一种解释。考虑到这一点，考虑使用 Either b () 而不是 Maybe b；然后

findOne :: (a -> Either b ()) -> Set a -> Either b ()
findOne = traverse_

几乎不值得命名。如果你必须有Maybe，你可以用明显的同构简单地包装它。

findOneMaybe :: (a -> Maybe b) -> Set a -> Maybe b
findOneMaybe f = to . traverse_ (from . f) where
    from = maybe (Right ()) Left
    to = either Just (const Nothing)

迭代 Data.Set 直到成功

Iterating over a Data.Set until success

haskell

set

maybe

问题。