在Haskell中搜索无限向量列表的非递归方法

Question

我有一个如下的数据结构：

import qualified Data.Vector.Unboxed as V
mylist :: [V.Vector (Int, Int)]

我需要搜索这个向量列表来寻找满足谓词的元素。算法保证我能找到元素。

到目前为止，我有这样的东西：

go []     = error "Could not find"
go pred (p:ps) =
  case V.find pred p of
    Just a  -> a
    Nothing -> go ps

这很简单，但我想去掉递归。有没有一个结构可以让我"组合"掉递归？

Answer 1

使用newtype包，可以方便地编写

import Control.Newtype
import Data.Monoid
import Data.Foldable
go :: Foldable f => (a -> Maybe b) -> f a -> Maybe b
go = ala' First foldMap

我认为这很好地暴露了你在这个计算中使用的结构。

Answer 2

在某些时候会使用递归，但您当然可以使用Data.Monoid和map:来简化它

go :: (a -> Bool) -> [V.Vector a] -> Maybe a
go pred = getFirst . mconcat . map (First . V.find pred)

我建议将其保留为返回Maybe a，而不是使用error，大多数人通常会建议不要使用error，因为它只会使程序崩溃，而不允许您优雅地退出。

另一种实现方法是使用Data.Maybe函数：

go pred = listToMaybe . catMaybes . map (V.find pred)

或

go pred = listToMaybe . mapMaybe (V.find pred)

或者可以使用MonadPlus实例作为Maybe（首先导入Control.Monad）：

go pred = msum . map (V.find pred)

或者Control.Applicative:中的Alternative实例

go pred = foldr (<|>) empty . map (V.find pred)
-- Or using foldl if you really want to

确实有很多方法可以解决这个问题。