Concat操作returns空列表

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

我基本上想做的是制作一个三角形矢量表示为单个向量。给定三角形内的位置我想要 return 包含该位置的行。

例如： 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。第一个问题是事实并非如此。实际上，此运算符 returns 是一个 new 列表，由连接在一起的两个输入组成，例如在 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 类型类的实例，但是不像 IO 那样排序，列表 Monad 实例做迭代，就像列表理解一样。

关于 monads 和 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，此时函数 returns 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) 以相反的顺序代替将元素添加到累加器参数81=]追加它们（list ++ [element]），然后reverse如果需要，之后的结果，因为这只是线性O（n）。

而不是 if … then … else …，通常认为使用 guards 更符合习惯，例如：

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 函数。）

Concat操作returns空列表

Concat operation returns empty list

haskell

concat