OCaml 递归函数：子列表元素乘以它们在列表中的位置，然后求和

Question

我正在尝试创建一个函数，该函数将 int 列表作为参数，returns 是 int 与其在列表中的位置之间的乘积之和。举个例子：multSum [5; 11; 15] 应该 return (5 * 1 + 11 * 2 + 15 * 3) = 72.

它应该递归地写，我正在尝试避免 List.map 或 List.filter 或任何其他预制函数。

通过划分和控制上面的查询，到目前为止，我已经开始尝试以下操作：

let rec tir f acc l =
match l with
|[] -> acc
|h::t -> tir f (f acc h) t ;;
val tir : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

然后我转到了这个:

let rec carto f a b =
match (a,b) with
|([],[])->([])
|(h1::t1,h2::t2)->(f h1 h2):: (carto f t1 t2)
|_->invalid_arg "carto";;
val carto : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>

有了能够做到这一点的最终想法：

let prod arg1 arg2 =
tir (+) 1 (carto ( * ) arg1 arg2);;
val prod : int list -> int list -> int = <fun>

但我现在被困住了，我不确定我今后的方向。我想尝试在“l”中搜索索引并替换 acc 中的每个索引 int，以使其工作，但恐怕我会让事情变得复杂......请帮忙吗？

编辑 1 :

let rec multSum l = 
  let rec indices n xs = match xs with
    | []   -> []
    | h::t -> n::(indices (n+1) t)in

  let rec tir f acc l =
    match l with
    |[] -> acc
    |h::t -> tir f (f acc h) t in

  let rec carto f a b =
    match (a,b) with
    |([],[])->([])
    |(h1::t1,h2::t2)->(f h1 h2):: (carto f t1 t2)
    |_->invalid_arg "carto" in

  let prod arg1 arg2 =
    tir (+) 0 (carto ( * ) arg1 arg2) in

  prod l (indices 1 l);;
val multSum : int list -> int = <fun>

根据您的回复，肯定 'fold' 和 'map' 重写了这些内容。至少，我现在确定我走在正确的轨道上。我已经将上面在 Edit 1.

中指示的整个代码放在一起

它似乎运行良好...我知道我想要一个递归函数，它就在这里。但是，你认为它可以做得更短 递归当然 ?

Answer 1

你的 tir 函数看起来像折叠；实际上与 List.fold_left:

具有完全相同的类型

# List.fold_left;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

在下面的代码片段中，prod 函数看起来像 map2

# List.map2;;
- : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>

您可以使用折叠和映射来计算您想要的函数，但您还需要首先从值列表构建索引列表。您可以按如下方式执行此操作：

let rec indices n xs = match xs with
  | []   -> []
  | h::t -> n::(indices (n+1) t);;

例如：

# indices 1 [5;1;3];;
- : int list = [1; 2; 3]

^{这不是递归终端，如果你先计算列表的长度，你会如何以递归终端的方式构建列表？}

那么您应该可以在列表 xs 和辅助列表 indices 1 xs 上调用 prod。这有点浪费，因为你需要建立一个辅助列表，但它看起来很容易理解，高阶函数如 map 或 fold 处理整个列表，因此需要考虑的极端情况更少。

但是，在走更抽象的路线之前，先为您的特定问题编写一个直接递归函数可能会更好。

直接递归函数也不需要额外的内存分配。如果您编写递归终端函数，您将携带额外的累加器值：

列表中的当前位置，初始为 1
当前乘积总和，初始为0

那么，您的函数具有以下骨架：

let rec f xs index product = match xs with
| []   -> ...
| h::t -> ...

你可以把它包装在一个主函数中 g:

let g xs = f xs 1 0;;

Answer 2

@coredump 说得很对，这看起来像是折叠的理想场景，但额外的功能并不是那么必要。我们可以只使用一个元组来传递索引和求和信息，然后当我们完成后，从元组中丢弃索引信息。

let sum_list_prod lst =
  let (_, result) = List.fold_left 
    (fun (i, sum) x -> (i + 1, sum + i * x)) 
    (1, 0) 
    lst
  in
  result

编辑： 左折叠的简单实现，以演示此处进行的递归。

let rec foldl f init lst =
  match lst with
  | [] -> init
  | first :: rest -> foldl f (f init first) rest

所以用 sum_list_prod 完成一个简单的例子：

sum_list_prod [2; 3; 4]

像这样跟注弃牌：

List.fold_left (fun (i, sum) x -> (i + 1, sum + i * x)) (1, 0) [2; 3; 4]

然后评估：

List.fold_left (fun (i, sum) x -> (i + 1, sum + i * x)) (1, 0) [2; 3; 4]
List.fold_left (fun (i, sum) x -> (i + 1, sum + i * x)) (2, 2) [3; 4]
List.fold_left (fun (i, sum) x -> (i + 1, sum + i * x)) (3, 8) [4]
List.fold_left (fun (i, sum) x -> (i + 1, sum + i * x)) (4, 20) []
(4, 20)

然后我们扔掉 4 因为我们不再需要它了，只剩下 20.

OCaml 递归函数：子列表元素乘以它们在列表中的位置，然后求和

OCaml Recursive function : sublist elements multiplied by their position in a list and then summed

ocaml

recursive-query