haskell - 直接生成 powerset 的特定子集？

Question

Haskell 的表达能力使我们能够相当容易地定义 powerset 函数:

import Control.Monad (filterM)

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

为了能够执行我的任务，按特定功能对所述 powerset 进行排序至关重要，因此我的实现看起来像这样:

import Data.List (sortBy)
import Data.Ord (comparing)

powersetBy :: Ord b => ([a] -> b) -> [a] -> [[a]]
powersetBy f = sortBy (comparing f) . powerset

现在我的问题是是否有办法只生成 子集给定特定的 powerset start和 end点，在哪里 f(start) < f(end)和 |start| < |end| .例如，我的参数是一个整数列表 ( [1,2,3,4,5] )，它们按总和排序。现在我只想提取给定范围内的子集，比如 3至 7 .实现此目的的一种方法是 filter powerset 只包括我的范围，但这在处理较大的子集时似乎(并且是)无效:

badFunction :: Ord b => b -> b -> ([a] -> b) -> [a] -> [[a]]
badFunction start end f = filter (\x -> f x >= start && f x <= end) . powersetBy f

badFunction 3 7 sum [1,2,3,4,5]生产 [[1,2],[3],[1,3],[4],[1,4],[2,3],[5],[1,2,3],[1,5],[2,4],[1,2,4],[2,5],[3,4]] .

现在我的问题是有没有办法直接生成这个列表，而不必生成所有 2^n首先是子集，因为它不必检查所有元素，而是“即时”生成它们，从而大大提高性能。

Answer 1

如果您想允许完全通用的排序功能，则无法绕过检查 powerset 的所有元素。 (毕竟，你怎么知道 is not 是一个内置的特殊子句，它给出了特定集合 [6,8,34,42] 与它的邻居完全不同的排名？)

但是，您可以通过以下方式使算法已经大大加快

过滤后才排序:排序是O(n·log n)，所以这里要保持n低；对于 O (n) 过滤步骤，它不太重要。 (无论如何，排序不会改变元素的数量。)

对每个子集只应用一次排序函数。

所以

import Control.Arrow ((&&&))

lessBadFunction :: Ord b => (b,b) -> ([a]->b) -> [a] -> [[a]]
lessBadFunction (start,end) f
     = map snd . sortBy (comparing fst)
               . filter (\(k,_) -> k>=start && k<=end)
               . map (f &&& id)
               . powerset

基本上，让我们面对现实，除了非常小的基础之外，任何力量集都是不可行的。特定应用程序“一定范围内的总和”几乎是 packaging problem ;有非常有效的方法来做这种事情，但是你必须放弃完美的普遍性和对一般子集进行量化的想法。