一起添加2个Int列表F#

Question

我正在做家庭作业,问题是我们得到两个相同大小的int列表,然后将这些数字加在一起.示例如下.

    vecadd [1;2;3] [4;5;6];; would return [5;7;9]

我是新手,我需要保持我的代码非常简单,以便我可以从中学习.到目前为止我有这个.(不工作)

    let rec vecadd L K =
         if L <> [] then vecadd ((L.Head+K.Head)::L) K else [];;

我本质上想要用添加的数字替换第一个列表(L).此外,我尝试使用匹配案例以不同的方式对其进行编码.

    let rec vecadd L K =
       match L with
         |[]->[]
         |h::[]-> L
         |h::t -> vecadd ((h+K.Head)::[]) K

他们都没有工作,我希望得到任何帮助.

Answer 1

首先,您对修改第一个列表而不是返回新列表的想法是错误的.突变(即修改数据到位)是今天错误的首要原因(曾经是goto,但现在已经被禁止了很长时间).使每个操作产生一个新的数据而不是修改现有的数据更加安全.在某些情况下,它可能更具性能,非常违反直觉(见下文).

其次,你尝试这样做的方式,你没有做你认为你正在做的事情.双冒号并不意味着"修改第一项".这意味着"将物品放在前面".例如:

let a = [1; 2; 3]
let b = 4 :: a    // b = [4; 1; 2; 3]
let c = 5 :: b    // c = [5; 4; 1; 2; 3]

这就是列表的实际构建方式:从一个空列表开始,并为其添加项目.[1; 2; 3]你正在使用的语法只是一个语法糖.就是这样[1; 2; 3] === 1::2::3::[].

那你怎么修改列表呢？答案是,你没有!F#列表是不可变的数据结构.创建列表后,您无法再修改它.

这种不变性允许有趣的优化.再看看我上面贴的例子中,一个有三个列表a,b和c.你认为这三个列表占用多少内存单元？第一个列表有3个项目,第二个 - 4个,第三个 - 5个,因此占用的内存总量必须为12,对吧？错误!这三个列表占用的内存总量实际上只有5个单元.这是因为list b不是长度为4的内存块,而是4与指向列表的指针配对的数字a.该数字4称为列表的"头部",指针称为"尾部".类似地,该列表c由一个数字5(其"头部")和一个指向列表的指针组成b,这是它的"

如果列表不是不可变的,那么就不能像这样组织它们:如果有人修改我的尾巴怎么办？每次都必须复制列表(谷歌"防御性副本").

因此,列表的唯一方法是返回一个新列表.您尝试做的事情可以这样描述:如果输入列表为空,则结果为空列表; 否则,结果是前缀与头部总和之间的尾部总和.您可以在F#中写下这几乎是逐字的:

let rec add a b =
    match a, b with
    | [], [] -> []   // sum of two empty list is an empty list
    | a::atail, b::btail -> (a + b) :: (add atail btail)  // sum of non-empty lists is sum of their tails prepended with sum of their heads

请注意,此程序不完整:它没有指定当一个输入为空而另一个输入为空时结果应该是什么.编译器将生成关于此的警告.我将把解决方案作为练习留给读者.

Answer 2

您可以使用 List.map2 映射两个列表（请参阅文档）它成对地遍历两个列表，您可以给它一个函数（List.map2 的第一个参数）以应用于列表中的每一对元素。这会生成新列表。

 let a = [1;2;3]
 let b = [4;5;6]

 let vecadd  = List.map2 (+)

 let result  = vecadd a b
 printfn "%A" result

如果你不想“自己”做更多的工作，像这样吗？

let a = [1;2;3]
let b = [4;5;6]

let vecadd l1 l2 = 
    let rec step l1 l2 acc = 
        match l1, l2 with
            | [],  [] -> acc
            | [], _ | _, [] -> failwithf "one list is bigger than the other"
            | h1 :: t1, h2 :: t2 -> step t1 t2 (List.append acc [(h1 + h2)])
    step l1 l2 []
let result  = vecadd a b
printfn "%A" result

step 函数是一个递归函数，它需要两个列表和一个累加器来承载结果。

• 在最后一个 match 语句中，它做了三件事
  • 对两个列表的头部求和
  • 将结果添加到累加器
  • 使用新的累加器和列表的尾部递归调用自身
• 当剩余列表为空时，第一个匹配返回累加器
• 当其中一个列表比另一个长时，第二个匹配项将返回错误。当剩余列表为空时，累加器作为结果返回。

该调用step l1 l2 []使用两个提供的列表和一个空的累加器启动它。