OCaml 递归函数:子列表元素乘以它们在列表中的位置，然后求和 [英] OCaml Recursive function : sublist elements multiplied by their position in a list and then summed

问题描述

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

I’m trying to create a function that takes an int list as an argument and returns the sum of the product between an int and its position in the list. To put in an example this : multSum [5; 11; 15] should return (5 * 1 + 11 * 2 + 15 * 3) = 72.

它应该以递归方式编写，我正在尝试避免使用 List.map 或 List.filter 或任何其他预制函数.

It should be written recursively and I’m trying while avoiding List.map or List.filter or any other prefabricated functions.

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

By dividing and reigning the query above, I have so far started by trying the following :

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 以使其正常工作，但恐怕我使事情变得复杂了...有什么帮助吗?

But I am stuck now and I’m not sure of my orientation from here forward. I thought of trying to search for the index in a "l" and replace each index int in the acc, in order to make it work but I'm afraid I'm rather complicating things... Any help please ?

编辑 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>

根据您的回复，这些肯定是重写了折叠"和地图".至少，我现在确定我走在正确的轨道上.我已经按照上述编辑 1 中的指示将整个代码组合在一起.

Building on your replies, surely these are 'fold' and 'map' rewritten. At least, I'm sure now that I was on the right track. I have come to put together the whole code as signaled above in Edit 1.

它似乎运行良好......我知道我想要一个递归函数，它就在这里.但是，您认为它可以在更短的时间内递归地完成吗?

It seems to be working well... I know that I want a recursive function and here it is. But, do you think it could be done even shorter recursively of course?

推荐答案

@coredump 非常正确，这看起来像是折叠的理想场景，但额外的功能并不是真正必要的.我们可以只使用一个元组来传递索引和求和信息，然后当我们完成时，从元组中丢弃索引信息.

@coredump is quite right about this looking like an ideal scenario for a fold, but the extra functions aren't really that necessary. We can just use a tuple to pass the index and sum information around, then when we're done, discard the index information from the tuple.

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

左折叠的简单实现，用于演示此处进行的递归.

A simple implementation of a left fold to demonstrate the recursion going on here.

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

因此使用 sum_list_prod 完成一个简单的示例:

So working through a simple example with 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.

And then we throw away the 4 because we don't need it anymore and are just left with 20.

这篇关于OCaml 递归函数:子列表元素乘以它们在列表中的位置，然后求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！