haskell - 快速过滤有界枚举类型

Question

假设我有一个函数接受一些谓词 f 并将其应用于整个域:

someFilter :: (Enum a, Bounded a) => (a -> Bool) -> [a]
someFilter f = filter f [minBound ..]

我也知道这个谓词 f 只对相对较少的参数返回 True，例如

isA c = (c == 'A')

是否有可能以某种方式使 someFilter 变得更快，即不依赖于类型 a 的可能值的数量，而不更改其签名？

Answer 1

一般情况下你不能真的这样做，因为你给函数的只是a是Enum和 Bounded ，这意味着您永远无法判断谓词是否使用了 == (并不是说您无论如何都可以这样做)。相反，您可以编写一个可以在执行过滤器之前检查的自定义数据类型:

import Control.Applicative

infixr 2 `Or`
infixr 3 `And`
data Pred a
    = LessThan a
    | GreaterThan a
    | EqualTo a
    | Generic (a -> Bool)
    | And (Pred a) (Pred a)
    | Or  (Pred a) (Pred a)

someFilter :: (Enum a, Bounded a, Ord a) => Pred a -> [a]
someFilter p = go p [minBound ..]
    where
        go :: (Enum a, Bounded a, Ord a) => Pred a -> [a] -> [a]
        go (LessThan x)    = takeWhile (< x)
        go (GreaterThan x) = dropWhile (<= x)
        go (EqualTo x)     = const [x]
        go (Generic f)     = filter f
        go (And p q)       = go q . go p
        go (Or  p q)       = (++) <$> go p <*> go q

naiveFilter :: (Enum a, Bounded a) => (a -> Bool) -> [a]
naiveFilter f = filter f [minBound ..]

这为您提供了您需要的大部分工具(不是全部，这只是一个粗略的概述)来重新创建支持通用谓词的排序谓词的基本 bool 组合。对于某些情况 someFilter将比 naiveFilter 表现得好得多，例如 someFilter (LessThan 128) :: [Word32]与 naiveFilter (< 128) :: [Word32] .在我的电脑上，前者基本上以 0 结束，而后者我什至没有让它运行完成。您还可以运行类似 someFilter (And (LessThan 128) (GreaterThan 256)) :: [Word32] 的查询立即完成，但用 naiveFilter 会花很长时间.我用过 Word32而不是 Int这里是为了避免负数的问题。

如果你想把一堆谓词组合在一起，你可以这样做

allPs, anyPs :: [Pred a] -> Pred a
allPs = foldr1 And
anyPs = foldr1 Or

或者您可以尝试从中构建一棵平衡树，但这已经足够简单了。它确实让您可以相当轻松地表达相当复杂的查询:

> :set +s
> someFilter $ EqualTo 1 `Or` EqualTo 100 `Or` LessThan 1000 `And` GreaterThan 975 :: [Word32]
[1,100,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999]
(0.00 secs, 0 bytes)

请注意，这里的操作顺序很重要，因为 takeWhile和 dropWhile ，你也可以以重复结束(尝试制作大于或等于和小于或等于，你会明白我的意思)。这些修复将开始影响该算法的性能，但总的来说，您应该不会看到比 naiveFilter 更差的性能。 .