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

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插入到列表的位置3(第四个位置),则[100,200,300]可以使用递归将5插入到列表的位置2(第三个位置)[200,300],这意味着将产生递归调用[200,300,5].

我们可以假设递归调用将起作用; 我们现在唯一的工作就是将这个小问题的答案转换成我们给出的原始问题的答案.我们在示例中想要的答案是[100,200,300,5](将5插入到列表的第4位的结果[100,200,300],以及我们所拥有的是列表[200,300,5].那么我们如何才能获得我们想要的结果？只需添加回第一个元素!(想想看!为什么这是真的.)

完成该案例后,我们已经涵盖了要更新的列表和职位组合的所有可能情况.由于我们的功能将适用于所有可能性,并且我们的可能性涵盖所有可能的输入,这意味着我们的功能将始终正常工作.所以我们完成了!

我会留给你把这些想法翻译成Haskell,因为练习的目的是让你学习它,但希望能让你知道如何解决这个问题.

Answer 2

您可以在索引 z 处拆分列表，然后将列表的第一部分与元素连接（使用++ [y]），然后与列表的第二部分连接。但是，这将创建一个新列表，因为默认情况下数据是不可变的。按照惯例，列表的第一个元素具有索引0（因此z，如果您希望第一个元素的含义由 索引，请相应调整1）。

insertAt :: Int -> Int-> [Int] -> [Int] 
insertAt z y xs = as ++ (y:bs)
                  where (as,bs) = splitAt z xs