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

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.

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>

then I moved to this :

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>

with the final idea to be able to do that :

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

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 ?

Edit 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>

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?

Solution

@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

Edit: 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

So working through a simple example with sum_list_prod:

sum_list_prod [2; 3; 4]

Calls the fold like so:

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

And as that evaluates:

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)

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