haskell - 字典顺序中的 Haskell Powerset

Question

我想在 Haskell 中编写一个 powerset 函数，函数声明为：

powerset :: Ord a => [a] -> [[a]]

但是，我正在尝试按字典顺序进行排序，以便：

powerset [1,2,3] = [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

我找到了其他方法来做 powerset，例如：

powerSet = filterM (const [True, False])

但没有任何东西可以按字典顺序提供 powerset。有没有办法编写 powerset 函数来提供它或将未排序的 powerset 排序到这个顺序中？

Answer 1

你可以做一个正确的折叠：

powerset :: Foldable t => t a -> [[a]]
powerset xs = []: foldr go [] xs
    where go x acc = [x]: fmap (x:) acc ++ acc

然后：

\> powerset [1, 2]
[[],[1],[1,2],[2]]
\> powerset [1, 2, 3]
[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

_{（编辑答案以删除对tail函数的调用）}