list - 在 Haskell 中将元素插入列表中给定的索引

Question

该函数必须如下所示:insertElemAt::a -> [Int] -> [a] -> [a]。

示例:

insertElemAt 0 [2,5,9] [1..10] 
    = [1, 0, 2, 3, 0, 4, 5, 6, 0, 7, 8, 9, 10]

insertElemAt 0 [1,2,4,8] [0,1,0,0,1,1,0,1] 
    = [0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1]

我只知道初学者Haskell(if与管道|和递归)，但我尽了最大努力来解决这个问题，但它从来没有奏效。这是我最近的尝试:

insertElemAt x [0] ys = ys
insertElemAt x [1,2] ys = x:x:ys
insertElemAt x [] ys = ys
insertElemAt x xs [] = []
insertElemAt x (n:ns) (y:ys) = y:insertElemAt x (n-1:ns) ys  

我也尝试过类似的方法，但这似乎很困惑，我认为第一个更好:

insertElemAt :: a -> [Int] -> [a]-> [a] 
insertElemAt x [0] ys = ys
insertElemAt x [1,2] ys = x:x:ys
insertElemAt x (n:ns) (y:ys) = y:insertElemAt x (map reduc (n:ns)) ys 

reduc (n:ns) = n-1 : reduc ns

也许我的模式不好？我尝试用很多方式来写它们。

我还必须能够使用此函数并在名为 insertElemsAt (::[(a, Int)] -> [a] -> [a]) 的函数中使用它 ，它必须是上述函数的“通用”版本。所以我必须能够给出在哪个位置我想要插入什么类型的元素。

既然第一个我做不到，那我对这个就更迷失了。这是一个例子。我不知道如何使用管道 if-s 和递归来做到这一点:

insertElemsAt (zip [0,1,1] [2,5,9]) [1..10] 
    = [1, 0, 2, 3, 1, 4, 5, 6, 1, 7, 8, 9, 10]

insertElemsAt (zip [0,1,1,1] [1,2,4,8]) [0,1,0,0,1,1,0,1] 
    = [0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1]

有人可以向我解释如何以最简单的方式做到这一点吗？预先感谢您的帮助!

Answer 1

假设索引列表已排序，例如 @AndyG says ，如果您跟踪当前索引，可能会有所帮助。因此，您可以实现如下功能:

insertElemAt :: a -> [Int] -> [a] -> [a]
insertElemAt x = go 0
    where go _ [] ys = ys         -- (1)
          go i ns [] = …          -- (2)
          go i (n:ns) (y:ys) = …  -- (3)

您需要填写...部分。

这里的 go 是一个使用递归插入元素的函数。基本情况 (1) 是您要插入元素的索引列表已用完的情况，在这种情况下我们可以返回列表本身。

如果列表本身已用尽，情况 (2)，但仍有项目需要填写，您将需要创建一个列表，其中重复 x 您仍需要填写的项目数插入。

最后一种情况 (3) 您必须检查索引 i 与需要插入元素 n 的第一个索引的比较情况。如果相等，则必须插入元素 x 并进行递归(您应该在其中调用 go)。如果索引大于当前索引，则生成元素y，并在列表尾部递归并递增累加器索引。