遍历Data.Set直到成功 [英] Iterating over a Data.Set until success

问题描述

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

Suppose I have a function representing some computation that can fail

f :: a -> Maybe b

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

If I have a list l, I can find the first (when scanning left-to-right) item in the list on which f succeeds using findList f l, where findList is the following function

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

(或使用例如

(or using, e.g., firstJust from the extra package).

如果我想对 设置 ?

What do I do if I want to do the same thing with a Set from containers?

也就是说，我想要一个带有签名的功能

That is, I want a function with signature

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

等效于

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

上面的行用作实现.但是，我不想创建中间列表 Set.toList s (即使使用惰性评估，仍然会有一些不必要的开销，对吧?).

The line above works as an implementation. However, I don't want to create the intermediate list Set.toList s (even with lazy evaluation, there is still some unnecessary overhead, right?).

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

I also don't want to iterate over the entire set once a successful item has been found, as in the following implementation:

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

那么，有没有一种好的方法来遍历一组从左到右"，对每个成员应用可能失败的计算，并在第一个成功的结果处停止?

So is there a good way of traversing over a set "left-to-right", applying a computation that can fail to each member, and stopping at the first successful result?

推荐答案

您可以使用 Set 是 Foldable 的实例这一事实.因此，您可以通过以下方式实现 Fold 函数:

You can work with the fact that the Set is an instance of Foldable. You can thus implement a Fold function with:

import Control.Applicative((<|>))

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

这实际上可以与 Foldable 的所有实例一起使用:

this can in fact work with all instances of Foldable:

import Control.Applicative((<|>))

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

或 @DanielWagner说，我们可以使用 First ，因为 First 将选择第一个 Just ，因此可以使用:

or as @DanielWagner says, we can make use of First, since First will select the first Just, and thus work with:

import Control.Applicative((<|>))

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

tolist 的实现也可以通过 Foldable 来实现:

The implementation of toList is also implemented in terms of Foldable:

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

所以我们在这里要做的不是先将其包装在一个弊端中，然后再将其拆开，立即应用 f 并使用

so what we here do is instead of first wrapping it in a cons and then unwrap it, immediately apply f and work with the implementation of (<|>) :: Alternate f => f a -> f a -> f a.

这篇关于遍历Data.Set直到成功的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！