Concat操作返回空列表

Question

module Sample where
lastPeg = 15
leftCol  = [1, 2, 4, 7 , 11]
rightCol = [1, 3, 6, 10, 15]
rowData = []
makeRowData :: Integer-> Integer-> [Integer] 
makeRowData row pos = 
if (pos <= lastPeg) then
if (pos >= leftCol !! (fromIntegral row-1)) &&
(pos <= rightCol !! (fromIntegral row-1)) then
do
rowData ++ [row]
makeRowData row (pos + 1)
else
makeRowData (row+1) (pos)
else
rowData

我主要想做的是制作一个三角形的矢量表示为单个矢量。给定三角形内的位置我想返回包含该位置的行。

例如：rowData [6] = 4(表示为三角形中的第7个位置(

所需结果：rowData=[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]

实际结果：rowData=[]

我做错了什么？谢谢

Answer 1

您的核心问题在于代码的这一部分：

do
rowData ++ [row]
makeRowData row (pos + 1)

我想知道是否有人向你解释了运算符(++) :: [a] -> [a] -> [a]是"将一个列表附加到另一个列表"，给你的印象是像xs ++ ys这样的表达式修改了xs。第一个问题是事实并非如此；实际上，该操作符返回一个新的列表，该列表由连接在一起的两个输入组成，例如在GHCi:中

> xs = [1, 2, 3]
> ys = [4, 5]
> xs ++ ys       -- Append the lists.
[1, 2, 3, 4, 5]
> xs             -- The original lists aren’t modified.
[1, 2, 3]
> ys
[4, 5]

第二个问题是这里的do块误导了您：它在列表上运行，所以它没有像您期望的IO那样进行排序。do表示法可以与列表一起使用，因为列表类型具有Monad类型类的实例，但列表Monad实例不像IO那样进行排序，而是进行迭代，这与列表理解完全一样。

关于monad和do表示法的完整教程超出了这个答案的范围，但例如，所有这些都是等效的：

-- List comprehension:
[x * y | x <- [2, 3], y <- [3, 5]]
-- Equivalent ‘do’ notation:
do { x <- [2, 3]; y <- [3, 5]; pure (x * y) }
-- Desugared ‘do’ notation:
[2, 3] >>= ( x -> [3, 5] >>= ( y -> pure (x * y)))
-- Instances of ‘Monad’ & ‘Applicative’ for lists:
concatMap ( x -> concatMap ( y -> [x * y]) [3, 5]) [2, 3]
-- Result of all of the above:
[6, 10, 9, 15]

因此，您的do块正在对列表rowData ++ [row]进行迭代，这是始终单个元素row，因为根据其定义，rowData是始终空列表[]。=表示相等！在那个"循环"迭代中，有一个对makeRowData的递归调用，这些调用继续进行，用pos参数向上计数，直到到达lastPeg，此时函数返回rowData，这也是[]的另一个名称。

有更简单、更惯用的方法来解决这个问题，但为了学习，如果你想做尽可能小的修改，并保持基本上相同的显式递归结构，那么解决方案的一般原理是：

• 添加一个带有"累加器"参数的辅助函数，用于跟踪您的中间状态

• 从初始状态为的makeRowData调用此函数

• 如有必要，在从makeRowData返回结果之前，对结果进行一些最终处理

例如：

makeRowData :: Integer -> Integer -> [Integer] 
makeRowData initialRow initialPos
-- Start the “loop” with an initial ‘rowData’ of ‘[]’.
= makeRowDataHelper [] initialRow initialPos
makeRowDataHelper :: [Integer] -> Integer -> Integer -> [Integer]
makeRowDataHelper rowData row pos =
if (pos <= lastPeg) then
if (pos >= leftCol !! (fromIntegral row-1)) &&
(pos <= rightCol !! (fromIntegral row-1)) then
-- To “modify” the state for the next iteration,
-- recursively call ‘go’ with different values.
makeRowDataHelper (rowData ++ [row]) row (pos + 1)
else
makeRowDataHelper rowData (row+1) (pos)
else
-- To exit the iteration, just return a value.
rowData

我还没有测试你的逻辑是否真的正确，但至少这应该能帮助你摆脱困境。

除此之外，您还可以在这里进行一些性能和风格改进：

• 用++追加链表很慢；上述go的每次迭代，++必须遍历整个左手边才能构造其结果，并且该自变量随着每次递归调用而增长，因此该函数最终占用输入长度的二次时间O(n²(。对于这样的小列表来说，这并不重要，但很快就会变得效率太低，无法与较大的输入一起使用。

  解决此问题的一种常见方法是，使用"cons"运算符(element : list(以相反的顺序将元素附加到累加器参数，而不是将元素附加到它们(list ++ [element](，然后在必要时将结果reverse附加到后面，因为这只是线性O(n(。

• 通常认为使用保护更惯用，而不是在定义的顶层使用if … then … else …，例如：

  go rowData row pos
  | pos > lastPeg
  = rowData
  | pos >= leftCol !! (fromIntegral row-1)
  , pos <= rightCol !! (fromIntegral row-1)
  = …
  | otherwise
  = …
  

• 您在列表中重复使用!!，这也需要索引值中的线性时间O(n(来遍历列表。考虑使用不同的数据结构，例如具有恒定时间O(1(索引的Data.Array或Data.Vector，或者不需要随机访问索引到列表中的不同算法。(例如，查看replicate功能。(