Haskell：集合上的递归函数 [英] Haskell: Recursive Function on Sets

问题描述

我是Haskell的新手，我试图编写一个基本的递归函数来生成一个集合的分区。我参考了这个wiki页面（ https://en.wikipedia.org/wiki/Partition_of_a_set ）为我定义的分区。

I am new to Haskell and I am trying to write a (somewhat) basic recursive function that generates the partitions of a set. I am referencing this wiki page (https://en.wikipedia.org/wiki/Partition_of_a_set) for my definition of set partitions.

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

I currently have a function that produces most, but not all, of the partitions:

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]] 变体。

As you can see it is missing the [[1,3],[2]] variant.

我想知道这个函数是否可以很容易地修改来适应我的需求，或者是否需要创建一个全新的函数。感谢。

I was wondering if this function could be easily modified to accommodate my requirements, or if a whole new function would need to be created. Thanks.

推荐答案

问题在于使用 [（b：qs）：qss | （qs：qss）< - separate bs] ，您只需将 b 添加到每个 bs 分区。您希望将它预先添加到每个子集中。

The problem is that with [(b:qs):qss | (qs:qss) <- separate bs], you only prepend b to the first subset of each of the bs partitions. You want to prepend it to 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) 

如果您不明白 = << 操作符会：它变平列表的嵌套。 单独的bs 已经生成了一个分区列表;对于其中的每一个，我们从 singleModifies 获得另一个列表，但最终我们对哪个列表来自哪里并不感兴趣，所以我们只是 join （aka concat ）。另一种写作方式是单独购买（b：bs）= [[b]：s | b

In case you don't understand what the =<< operator does: it “flattens” the nesting of lists. separate bs already generates a list of partitions; for each of these we get another list from singleModifies, but in the end we're not interested in which list came from where, so we just join (aka concat) them together. Another way for writing this would be

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

这篇关于Haskell：集合上的递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！