How to structure an accumulator for fold_left with index access-CodePudding

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 should I 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 I'm 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：

Let's consider a really imperative solution to your problem first.

A utility function so we can do integer exponentiation. We'll use List.iter to run an imperative loop over an int list.

let rec pow x =
  function
  | 0 -> 1
  | 1 -> x
  | n -> x * pow x (n - 1)

let lst = [1; 4; 7; 2]

let pos = ref 0
let sum = ref 0

let () = List.iter (fun x -> sum := !sum   pow x !pos; pos := !pos   1) lst

Printf.printf "The sum is %d\n" !sum

There were two pieces of information we needed to keep track of across the iteration: pos and sum. In this imperative style, we kept track of them by mutating a value.

When we use List.fold_left and use an accumulator to contain this same state, we no longer need to mutate any values.

let (pos, sum) = List.fold_left (fun (p, s) x -> (p   1, s   pow x p)) (0, 0) lst

You can see how the initial state provided mirrors the zeroes I provided in the imperative example.

If we look at how this progresses as it works over the list it's possible to get a better picture of how the accumulator tuple works.

List.fold_left f (0, 0) [1; 4; 7; 2]
List.fold_left f (1,  0   pow 1 0) [4; 7; 2]
List.fold_left f (2,  1   pow 4 1) [7; 2]
List.fold_left f (3,  5   pow 7 2) [2]
List.fold_left f (4, 54   pow 2 3) []
(4, 62)

CodePudding user response：

List.fold_left can accept an accumulator of any type

(* given some pow function *)
let rec pow a b =
  match b with
  | 0 -> 1
  | _ -> a * pow a (b - 1)

(* your initial accumulator *)
let init = (0, 0) in 

(* your folding function *)
let f (i, r) v = 
  (i   1, r   pow v i) in

(* note the output is a tuple of the last i and the sum *) 
let (i, result) = List.fold_left f init [10;20;30;40] in

(* print the result *)
Format.printf "result: %d\n" result

result: 64921

Check your work -

10^0   20^1   30^2   40^3 = 64921 ✅

CodePudding user response：

You can use a pair 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.