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

Question

我正在尝试创建一个函数，该函数将int列表作为参数，并返回int与其在列表中的位置之间的乘积之和。举一个例子：multSum[5；11；15]应该返回(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>

根据你的回答，这些肯定是"折叠"one_answers"地图"重写的。至少，我现在确信我走在了正确的轨道上。我已经把上面在Edit 1中发出的整个代码放在一起了。

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

Answer 1

@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。

Answer 2

您的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;;