对有界枚举类型进行快速筛选

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 ..]

这为您提供了所需的大多数工具（不是所有工具，这只是一个粗略的概述），以重新创建支持泛型谓词的排序谓词的基本布尔组合。对于某些情况，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更差的性能。

Answer 2

对于固定字w :: Word160，考虑a是Word160，f是(== w) . sha1，其中sha1 :: Word160 -> Word160是SHA-1的一些实现。则谓词仅对极少数输入（很可能为1）为真。如果你有一种快速找到匹配值的方法，你可以构建SHA-1的逆函数，这将允许你破解数字签名和各种类似的东西。所以不，没有有效的方法来做到这一点，除非你以某种方式限制谓词。