Haskell列表的连续子列表

Question

你好，我有一个小函数可以找出集合的幂集，但是我需要所有连续子列表。[1,2,3] -> [[],[1],[2],[3],[1,2],[2,3],[1,2,3]]而不是[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

有没有办法修复这个函数以实现我的要求？

sublists :: [a] -> [[a]]
sublists [] = [[]]
sublists (x:xs) = sublists xs ++ map (x:) (sublists xs)  

- Laci Feldsam

---

答案中元素的顺序是否重要？ - bipll

Answer 1

虽然不太优雅，但您可以使用来自 Data.List.Split 的 divvy：

xs = [1,2,3]
[] : concat [ divvy n 1 xs | n <- [1..length xs] ]
-- [[],[1],[2],[3],[1,2],[2,3],[1,2,3]]

- Michael Kohl

Answer 2

Michael Kohl的答案无法构建。Divvy已经返回[[a]]，因此列表推导式返回[[[a]]]。我只会添加注释，但没有足够的声望来这样做。请使用concat。

sublists xs = [] : concat [ divvy n 1 xs | n <- [1..length xs]]

- Anicka Burova

Answer 3

我不确定你是否只是想要已有结果，但元素排列方式不同。如果是这样，一种简单但不太优雅的方法是在执行sublists后进行排序。决定元素顺序的函数将是：

subCompare x y = case (compare (length x) (length y)) of 
     EQ -> compare x y 
     s -> s 

这意味着，按长度进行比较，但如果它们具有相同的长度，则按元素顺序进行比较。 然后：

> sortBy subCompare (sublists [1,2,3])
[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

- Euge

Answer 4

这几乎是一个简单的递归，如果我们想要子列表 [1,2,3,4]并且已经有了尾部的子列表，那就...

[[], [2], [3], [4], [2,3], [3,4], [2,3,4]]

很明显，为了处理新元素1，我们需要添加新的子列表[1]、[1,2]、[1,2,3]和[1,2,3,4]。问题是不清楚应该在哪里插入这些新的子列表。

为了使它更容易，我们可以进行稍微不同的递归，将每个长度的子列表分别保留在自己的列表中，因此我们将会有：

[[[]],
 [[2], [3], [4]],
 [[2,3], [3,4]],
 [[2,3,4]]]

现在插入新子列表的位置更加明显。

最终结果将只是连接。

sublists :: [a] -> [[a]]
sublists = concat . sublists'

sublists' :: [a] -> [[[a]]]
sublists' [] = [[[]]]
sublists' (x:xs) = zipWith (++) withX withoutX
  where
    ysss = sublists' xs
    withX = [] : [[x:ys] | ys:_ <- ysss]
    withoutX = ysss ++ [[]]

注：

• 我们需要使 withX 和 withoutX 的长度相同，以便在 zipWith 不会提前运行完毕，并且由于 withoutX 已经包含了我们不需要在 withX 中包含的零长度子列表。

• 我可以使用 inits（x：xs） 编写 withX，但这将创建新的列表，而不是共享我们在 ysss 中拥有的一些列表。 （尽管最大化共享有时取决于您如何使用结果。）

• sublists' 也可以写成 foldr。

- David Fletcher

Answer 5

尽管不是按照您要求的顺序，

import Control.Monad((<=<))
import Data.List(inits, tails)

-- inits [x, y, z, ...] = [[], [x], [x, y], [x, y, z], ...]
-- tails [x, y, z, ...] = [[x, y, z, ...], [y, z, ...], [z, ...], [...], ..., []]
-- (f <=< g) x = do  y <- g x
--                   f y
-- (f . g) x   = let y = g x
--                in f y

sublists = ([]:) . (tail . inits) <=< tails

这里利用了列表单子模型来模拟非确定性： tails 非确定性地选择子列表的起始位置，inits 选择其结束位置，对于空列表还需要进行一些处理以获得更好的行为，列表单子负责迭代所有可能的开头和结尾组合。

- HTNW

Answer 6

我不确定是否理解问题，但如果是的话，您可以使用combinat包的combine函数：

> import Math-Combinat-Sets
> map (`combine` [1,2,3]) [0..3]
[[[]],[[1],[2],[3]],[[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]],[[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]]

- Stéphane Laurent