Haskell：集合上的递归函数

我是 Haskell 的新手，我正在尝试编写一个（有点）基本的递归函数来生成集合的分区。我正在引用这个维基页面（https://en.wikipedia.org/wiki/Partition_of_a_set https://en.wikipedia.org/wiki/Partition_of_a_set）作为我对集合分区的定义。

我目前有一个函数可以生成大部分（但不是全部）分区：

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (b:bs) = [[b]:s | s <- separate bs] ++ [(b:qs):qss | (qs:qss) <- separate bs]

>separate [1,2,3]
[[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]

正如你所看到的，它缺少[[1,3],[2]]变体。

我想知道是否可以轻松修改此函数以满足我的要求，或者是否需要创建一个全新的函数。谢谢。

问题在于[(b:qs):qss | (qs:qss) <- separate bs]，你只需前置b to the first每个的子集bs分区。你想把它放在前面every subset.

separate (b:bs) = [[b]:s | s <- separate bs]
               ++ (singleModifies (b:) =<< separate bs)

-- | All possibilities of applying a function to exactly one element in the list.
singleModifies :: (a->a) -> [a] -> [[a]]
singleModifies _ [] = []
singleModifies f (x:xs) = (f x:xs) : map (x:) (singleModifies f xs) 

如果您不明白什么=<< http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:-62--62--61-运算符的作用是：它“展平”列表的嵌套。separate bs已经生成分区列表；对于每一个，我们都会得到另一个列表singleModifies，但最终我们对哪个列表来自哪里不感兴趣，所以我们只是join http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Monad.html#v:join (aka concat http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:concat）他们在一起。另一种写法是

separate (b:bs) = [[b]:s | s <- separate bs]
               ++ concat [singleModifies (b:) bp | bp <- separate bs]