在 Haskell 中创建一个递增数字的列表嵌套列表。

Question

给定一个起始数字和一个增量，我希望能够在 Haskell 中创建一个列表嵌套的列表。

例如：

>listIncrease 5 3
[[5], [5,6], [5,6,7]]

我尝试使用递归函数，但是我还没有能够完全掌握这个函数。

这是我目前的代码：

listIncrease :: Int -> Int -> [[Int]]
listIncrease a 0 = []
listIncrease a b = [[a..a+b-1], (listIncrease a (b-2))]

我知道这不行，因为基础情况是错误的，无法递归处理，因为你不能把一个[[Int]]当成[Int]。

- lex449

Answer 1

我们可以用以下方法构造一个范围：

[5 .. 7]

为了创建我们想要的最终列表：

Prelude> [5 .. 7]
[5,6,7]

我们可以使用 inits :: [a] -> [[a]] 来生成所有前缀：

Prelude Data.List> inits [5 .. 7]
[[],[5],[5,6],[5,6,7]]

我们可以使用 drop :: Int -> [a] -> [a] 来省略第一个元素。

因此，我们可以这样实现 listIncrease：

import Data.List(inits)

listIncrease :: (Num a, Enum a) => a -> a -> [[a]]
listIncrease lo n = drop 1 (inits [lo .. lo + n - 1])

例如：

Prelude Data.List> listIncrease 7 0
[]
Prelude Data.List> listIncrease 7 1
[[7]]
Prelude Data.List> listIncrease 7 2
[[7],[7,8]]
Prelude Data.List> listIncrease 7 3
[[7],[7,8],[7,8,9]]

- Willem Van Onsem

Answer 2

这将起作用：

listIncrease :: Int -> Int -> [[Int]]
listIncrease a b = [[a..i] | i <- [a..a+b-1]]

为了理解这为何有效，考虑对您的示例中的 5 和 3 进行外层求值: [[5..i] | i <- [5..7]], [[5..i] | i <- [5,6,7]], 然后是 [[5..5], [5..6], [5..7]]。

- Joseph Sible-Reinstate Monica

---

非常好的答案。涵盖了所有内容。 - developer_hatch

这是输出列表的代码：take 3 [ [5..n] | n <- [5..] ] - fp_mora

Answer 3

有一个标准库函数可以做到这一点 - inits。它返回列表的所有可能前缀，包括空前缀：

> inits ['a', 'b', 'c']
[[], ['a'], ['a', 'b'], ['a', 'b', 'c']]

为了得到你需要的内容，你只需删除第一个空列表即可完成：

listIncrease a n = drop 1 $ inits [a .. (a+n-1)]

- Fyodor Soikin

---

哈哈，我们几乎在同一时间写了几乎完全相同的答案 :) - Willem Van Onsem

Answer 4

另一种使用 inits 的选项：创建一个无限的范围列表，删除第一个（空）范围，然后取下一个 n 个元素：

listIncrease from n = take n (tail (inits [from..]))

这甚至有一个几乎可读的无点版本：

listIncrease = flip take . tail . inits . enumFrom

以下是每个步骤的类型说明和使用5和3作为参数的示例：

• enumFrom :: Enum a => a -> [a] 产生 [5..]
• inits . enumFrom :: Enum a => a -> [[a]] 产生 [[],[5],[5,6],[5,6,7],...]
• tail . inits . enumFrom :: Enum a => a -> [[a]] 产生 [[5],[5,6],[5,6,7],...]
• flip take . tail . inits . enumFrom :: Enum a => a -> Int -> [[a]] 产生函数调用 (flip take) [[5],[5,6],[5,6,7],...] 3 == take 3 [[5],[5,6],[5,6,7],...] == [[5],[5,6],[5,6,7]]

- chepner

Answer 5

我认为这是最清晰的递归实现：

listIncrease :: Int -> Int -> [[Int]]
listIncrease a 0 = []
listIncrease a b = map (a:) $ [] : listIncrease (a + 1) (b - 1)

- Robin Zigmond

Answer 6

如果您想使用传统的模式匹配来实现，可以尝试以下方法：

listIncrease :: Int -> Int -> [[Int]]
listIncrease a 0 = []
listIncrease a 1 = [[a]]
listIncrease a b = reverse $ ([a..a+b-1] : [a..a+b-2] : (listIncrease a (b-2)))

由于数字可能是奇数，而且每次递归你都会走两步，所以当数字为1时，你应该添加额外的模式，并将列表反转以获得所需的顺序。

使用Sequence的优化版本应该是：

import Data.Sequence ((|>), empty, fromList)
import Data.Foldable (toList)

listIncrease :: Int -> Int -> [[Int]]
listIncrease a b = toList (fromSeq a b)

fromSeq a 0 = empty
fromSeq a 1 = fromList([[a]])
fromSeq a b = (fromSeq a (b-2)) |> [a..a+b-2] |> [a..a+b-1]

- developer_hatch