1

函数必须是这样的：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]

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

4

2 回答 2

3

假设索引列表是排序的，就像@AndyG 说的那样，如果您跟踪当前索引可能会有所帮助。因此，您可以实现如下功能：

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）。如果索引大于当前索引，则产生 element y，并在列表尾部产生递归并增加累加器索引。

于 2020-04-22T11:05:19.703 回答
1

你可以从你已经知道的开始：

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

这是一个完全有效的定义，它甚至会产生一个正确的结果，即使对于一个非常具体的情况，并且在其他任何地方都存在分歧。

但我们可以将其概括为

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

还有更多，

insertElemAt _0 [
          2,         5,           9] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a, _0, b, c, _0, d, e, f, _0, g, h, i, j ]

我们可以添加一些显然也必须成立的特殊情况，比如

insertElemAt _0 [
          2,         5] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a, _0, b, c, _0, d, e, f,     g, h, i, j ]

和

insertElemAt _0 [
          2] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a, _0, b, c,     d, e, f,     g, h, i, j ]

乃至

insertElemAt _0 [
          ] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
    = [a,     b, c,     d, e, f,     g, h, i, j ]

; 我们可以更进一步地概括这一点，因为

insertElemAt _0 [] xs
    = xs

很明显

insertElemAt _0 [
          2] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
  =
       a : insertElemAt _0 [
          1]
             [b, c,     d, e, f,     g, h, i, j ]

和

insertElemAt _0 [
          2,         5] 
      [a,     b, c,     d, e, f,     g, h, i, j ] 
  =
       a : insertElemAt _0 [
          1,         4]
             [b, c,     d, e, f,     g, h, i, j ]

总的来说_

insertElemAt _0 (i:is) (x:xs)
    | i > 1  =  x : insertElemAt _0 (minus1 (i:is)) xs

必须成立，那么为什么我们不把它也作为我们定义的一部分呢？和

-- minus1 is = [i-1 | i <- is]

minus1 []      = _____
minus1 (i:is) = ( ____ - 1) : ______ is

（填空白）。所以对于这个i==1案子，

insertElemAt _0 (i:is) (x:xs)
    | i == 1  =  x : _0 : insertElemAt _0 (minus1 (_____)) xs
  -- or is it
  --             _0 : x : ........   ?

所以你已经成功了一半。剩下要做的就是添加几个边缘情况，你就完成了。

现在它不会是最有效的版本，因为它会反复1从索引列表的每个成员中减去；您可以通过添加一个新的辅助参数来简化这部分，这将否定从索引列表的每个元素中减去的需要，并用一个加法替换它，向上计数而不是向下计数。要使用该附加参数，您必须定义和使用辅助的嵌套函数定义。

于 2020-08-11T11:04:40.703 回答