0

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

Improve this question
2
  • The right function for fold_left? ;-) Commented Dec 10, 2021 at 14:04
  • 1
    If you have tried something, even if it has not worked (or you wouldn't be here, right?) you should include it in your post. You may be close. Commented Dec 10, 2021 at 16:10

4 Answers 4

Reset to default
1

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

type 'a acc = { pos:int; acc:'a }
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

actually the function fold_left will give f an integer. The formula is acc + sum from i=0 to n of a_i ^ i
You are still free to define the type of the accumulator: the type of fold_left is ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a . As you can see, the type of f is not restricted to int -> int -> int.
Using a tuple or record as an accumulator may mean fold_left is returning more information that you need. You can use pattern-matching in a let binding or a match expression to isolate the information you need and discard the rest.
The accumulator should essentially be all of the state you need to keep track of as you iterate. The only thing it doesn't need to track is the current element.
1

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.

Improve this answer

Comments

0

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 ✅
Improve this answer

Comments

0

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)

Alternatively...

We could simply use List.mapi to get each element raised to its index as an exponent, and then use List.fold_left to sum those values.

# [1; 4; 7; 2]
  |> List.mapi @@ Fun.flip pow
  |> List.fold_left (+) 0;;
- : int = 62

For a large list you might wish to employ sequences to avoid generating another list.

# [1; 4; 7; 2]
  |> List.to_seq
  |> Seq.mapi @@ Fun.flip pow
  |> Seq.fold_left (+) 0;;
- : int = 62
Improve this answer

2 Comments

I suggest a small modification to your pow function, to make it logarithmic instead of linear: Integer exponentiation in Ocaml. This is especially important if it is going to be called repeatedly by fold_left or iter.
I thought about that, but was going for the easiest version of pow to understand to not distract.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.