list - 将整数插入列表中的特定位置

Question

我想要编写一个程序 insertAt，其中 z 是列表中的位置，y 是要插入到列表 xs 中的数字。我是 Haskell 新手，这就是我到目前为止所拥有的。

insertAt :: Int-> Int-> [Int]-> [Int]
insertAt z y xs
  | z==1 = y:xs

但我不知道该去哪里。

我有一个 elementAt 函数，其中

elementAt v xs
  | v==1 = head xs
  | otherwise = elementAt (v-1) (tail xs)

但我不确定如何将其放入或者是否需要。如果可能的话，我想避免追加。

Answer 1

如果这不是家庭作业:let (ys,zs) = splitAt n xs in ys++ [new_element]++ zs

在本文的其余部分中，我将假设您正在将这个问题作为家庭作业或自学如何做此类事情。

解决这类问题的关键是将其分解为自然情况。您正在处理两条数据:要插入的列表以及该列表中的位置。在这种情况下，每条数据都有两种自然情况:您正在处理的列表可以为空或不为空，并且您正在处理的数字可以为零或不为零。所以第一步是写出所有四种情况:

insertAt 0 val []     = ...
insertAt 0 val (x:xs) = ...
insertAt n val []     = ...
insertAt n val (x:xs) = ...

现在，对于这四种情况中的每一种，您都需要考虑在这种情况下应该给出什么答案。

对于前两种情况，答案很简单:如果您想插入到列表的前面，只需将您感兴趣的值放在开头，无论列表是否为空。

第三种情况表明，问题实际上存在歧义:如果要求您插入空列表的第三个位置，会发生什么？对我来说听起来像是一个错误，但您必须自己回答在这种情况下您想做什么。

第四种情况最有趣:假设您想要将一个值插入到非空列表的非第一个位置。在这种情况下，请记住您可以使用递归来解决问题的较小实例。在这种情况下，您可以使用递归来解决，例如，insertAt (n-1) val xs——即将相同的值插入到输入列表尾部的结果第 n-1 个位置。例如，如果您尝试将 5 插入列表 [100,200,300] 的位置 3(第四个位置)，则可以使用递归将 5 插入列表的位置 2(第三个位置) [200,300]，这意味着递归调用将产生 [200,300,5]。

我们可以假设递归调用会起作用；我们现在唯一的工作就是将那个较小问题的答案转换为给我们的原始问题的答案。示例中我们想要的答案是 [100,200,300,5] (将 5 插入到列表 [100,200,300] 的位置 4 的结果，我们得到的就是列表[200,300,5]。那么我们怎样才能得到我们想要的结果呢？只需添加回第一个元素即可!(想想为什么这是真的。)

完成该案例后，我们已经涵盖了要更新的列表和位置组合的所有可能情况。由于我们的函数将在所有可能性下正确工作，并且我们的可能性涵盖所有可能的输入，这意味着我们的函数将始终正确工作。这样我们就完成了!

我将让您将这些想法转化为 Haskell，因为练习的目的是让您学习它，但希望这能让您知道如何解决问题。