How to structure an accumulator for fold

I want to write a function that takes a List [a_n; a_n-1; ...; a_0] with an accumulator acc.

The function is supposed to calculate the sum of every element in the whole list raised to the i'th power. The function fold_left will give f an integer. The formula is acc sum from i=0 to n of a_i ^ i. My problem is that in fold_left:

let fold_left f acc l = 
 match l with 
 | [] -> acc
 | x::xs -> fold_left f (f x acc) xs

the accumulator always returns one integer - so there's no reference for me to know what number the i'th element is.

So my question is how I should structure my f function.

f should be structured like this:

 f a_0 (f a_1(...(f a_n acc)...))

I tried an imperative approach by using a ref variable that stores the previous values that f has calculated thus far. But Im sure there are better solutions to this problem...

CodePudding user response：

The accumulator don't need to be an integer, it can be a tuple, or a record

type 'a acc = { pos:int; acc:'a }

CodePudding user response：

You can use a tuple with two elements for the accumulator:

# let f (s, i) x =
      (s   pow x i, i   1);;
val f : int * int -> int -> int * int = <fun>

# let sum_powers_left l = fst (List.fold_left f (0, 0) l);;
val sum_powers_left : int list -> int = <fun>


# let g x (s, i) =
      (s   pow x i, i   1);;
val g : int -> int * int -> int * int = <fun>

# let sum_powers_right l = fst (List.fold_right g l (0, 0));;
val sum_powers_right : int list -> int = <fun>


# sum_powers_left [2000; 100; 20; 3];;   (* 1   100   20*20   3*3*3 *)
- : int = 528

# sum_powers_right [2000; 100; 20; 3];;  (* 2000*2000*2000   100*100   20   1 *)
- : int = 8000010021

where pow x i evaluates to x to the power of i. Sadly it's not in the standard library.