且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

Haskell:集合上的递归函数

更新时间:2023-02-27 09:10:47

问题在于使用 [(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]