通过折叠来倍增列表

Question

所以我目前正在尝试编写一个函数，它需要两个长度相等的列表，并通过折叠将两个列表的相同位置相乘，并将结果作为新列表返回。

eg) let prodList [1; 2; 3] [4; 5; 6] ;; 
==> (through folding) ==> [1*4; 2*5; 3*6]
==> result = [4; 10; 18]

我觉得我需要使用List.combine，因为它会将需要相乘的值放入元组中。之后，我不知道如何以允许我乘以值的方式分解元组。这是我到目前为止所拥有的：

let prodLists l1 l2 =
  let f a x =  (List.hd(x)) :: a in
  let base = [] in
  let args = List.rev (List.combine l1 l2) in
  List.fold_left f base args

我走在正确的道路上吗？

Answer 1

您可以使用

fold_left2

来折叠两个相同长度的列表。该文档可以为您提供更多详细信息（https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html）：

val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a

List.fold_left2 f a [b1; ...; bn] [c1; ...; cn]

是

f (... (f (f a b1 c1) b2 c2) ...) bn cn

。如果确定两个列表具有不同的长度，则提高

Invalid_argument

。

另一种方法是按照您的建议折叠组合的输出，我建议您在查看下面的解决方案之前先自己尝试一下。

解决方案：

let prod_lists l s =
  List.rev (List.fold_left2 (fun acc a b -> (a * b) :: acc) [] l s);;

let prod_lists' l s =
  List.fold_left (fun acc (a, b) -> (a * b) :: acc) [] (List.rev (List.combine l s));;

Answer 2

首先让我注意使用折叠来实现这个操作似乎有点强迫，因为你必须同时遍历两个列表。然而，Fold 组合了单个列表的元素。尽管如此，这里还是一个实现。

let e [] = []

let f x hxs (y::ys) = (x*y) :: hxs ys 

let prodList xs ys = List.fold_right f xs e ys

看起来有点复杂，让我解释一下。

右折的通用属性

首先您应该了解

fold_right

的以下属性。

h xs = fold_right f xs e 

当且仅当

h [] = e
h (x::xs) = f x (h xs)

这意味着，如果我们以下面的递归形式编写列表的乘法，那么我们可以使用

e

和

f

来使用上面的折叠来编写它。请注意，虽然我们正在操作两个列表，所以

h

有两个参数。

基本情况 - 空列表

将两个空列表相乘将返回一个空列表。

h [] [] = []

上面的表格该怎么写呢？只是对第二个论点进行抽象。

h [] = fun [] -> []

那么，

e = fun [] -> []`

或者同等地，

e [] = []

递归案例 - 非空列表

h (x::xs) (y::ys) = x*y :: h xs ys

或者，仅使用一个参数，

h (x::xs) = fun -> (y::ys) -> x*y :: h xs ys

现在我们需要以

h (x::xs) = f x (h xs)

的形式重写这个表达式。看起来可能很复杂，但我们只需要抽象

x

和

h xs

即可。

h (x::xs) = (fun x hxs -> fun (y::ys) -> x*y :: hxs ys) x (h xs)

所以我们有

f

定义为

f = fun x hxs -> fun (y::ys) -> x*y :: hxs ys

或者同等地，

f x hxs (y::ys) = x*y :: hxs ys

解决方案为向右折叠

确定了

e

和

f

后，我们只需根据上述属性的第一个方程将其插入折叠即可。我们得到，

h xs = List.fold_right f xs e

或者同等地，

h xs ys = List.fold_right f xs e ys

了解实施

请注意

List.fold_right f xs e

的类型是

int list -> int list

，因此折叠正在列表上构建一个函数，给定一些

ys

会将其与给定参数

xs

相乘。

对于空的

xs

，你会期望一个空的

ys

并返回一个空的结果，所以，

e [] = fun [] -> []

对于递归情况，

f

中的函数

fold_right

必须从

x::xs

的解决方案实现

xs

的解决方案。因此

f

采用

x

类型的

int

和

hxs

类型的函数

int list -> int list

实现尾部的乘法，并且它必须实现

x::xs

的乘法。

f x hxs = fun (y::ys) -> x*y :: hxs ys

因此

f

构造一个函数，将

x

与

y

相乘，然后应用于

ys

已构造的

hxs

，将

xs

乘以列表。

Answer 3

你的想法大多是正确的；您需要

combine

（在其他语言中为

zip

）两个列表，然后

map

在每个元组上：

let prod_lists l1 l2 =
  List.combine l1 l2
  |> List.map (fun (a, b) -> a * b)

关键是您可以使用

(a, b)

在该元组上进行模式匹配。

如果您不想使用

fold

，您还可以

rev

组合列表，然后

map

结果。

Answer 4

任何时候你想使用弃牌的技巧通常是问：“我的累加器是什么？”因为这是您可以从一次迭代传递到下一次迭代的唯一状态。

如果累加器只是结果列表，那么我们实际上没有办法处理第二个列表，但是如果我们的累加器是累加列表和第二个列表的元组，那么每次迭代我们可以更新累加器，但也第二个列表。

# let lst1 = [1;2;3] in
  let lst2 = [4;5;6] in
  List.fold_left (fun (acc, y::ys) x -> (x * y :: acc, ys)) ([], lst2) lst1;;

Line 3, characters 15-57:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(acc, [])

Line 3, characters 15-57:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(acc, [])

- : int list * int list = ([18; 10; 4], [])

• 这里有很多关于非详尽匹配的警告。我们可以忽略这一点，因为您已经指定列表的长度相等。
• 我们将这两个列表作为最终结果。没关系。
• 构建的列表是倒退的。这也没关系。我们可以扭转它。

如果我们看看这个递归：

List.fold_left (fun (acc, y::ys) x -> (x * y :: acc, ys)) ([], [4;5;6]) [1;2;3]

List.fold_left (fun (acc, y::ys) x -> (x * y :: acc, ys)) (4 :: [], [5;6]) [2;3]

List.fold_left (fun (acc, y::ys) x -> (x * y :: acc, ys)) (10 :: 4 :: [], [6]) [3]

List.fold_left (fun (acc, y::ys) x -> (x * y :: acc, ys)) (18 :: 10 :: 4 :: [], []) []

([18; 10; 4], [])

用

fst

和

List.rev

纠正上面的后两个问题：

# let lst1 = [1;2;3] in
  let lst2 = [4;5;6] in
  List.fold_left (fun (acc, y::ys) x -> (x * y :: acc, ys)) ([], lst2) lst1 
  |> fst 
  |> List.rev;;

Line 3, characters 15-57:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(acc, [])

Line 3, characters 15-57:
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(acc, [])

- : int list = [4; 10; 18]

如果我们想避免警告，我们可以通过引发异常来处理空列表情况。

# let lst1 = [1;2;3] in
  let lst2 = [4;5;6] in
  List.fold_left 
    (fun (acc, lst) x -> 
       match lst with
       | [] -> invalid_arg "unequal length lists" 
       | y::ys -> (x * y :: acc, ys)) 
    ([], lst2) 
    lst1
  |> fst
  |> List.rev;;
- : int list = [4; 10; 18]

因此我们可以看到，如果我们对累加器有一点创意，这个任务可以很容易地使用折叠来解决。