CODEWITHSUNDEEP
listocaml
Jeremy
Jeremy

Reputation: 2044

Adding Elements in List from Left OCaml

I have written a function:

let rec addAll f l =
  match l with
  | [] -> 0
  | [x] -> x
  | hd::tl -> let combined = addAll f tl in
                f (hd) combined
;;

I works as titled, it will add all the elements of a list. However, I want to write this program so it is Left associative, so instead of combining the elements [1;2;3] as 1 - (2 - 3), I want it to be: (1 - 2) - 3.

Any hints on how I can make this forward recursive instead of tail? Or how can I make it so this function works as I intend? I know I could just reverse the list, but I want to try another way.

Upvotes: 0

Views: 817

Answers (2)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66808

Your code does a right fold. Roughly speaking, it's like this:

let addAll f l = List.fold_right f l 0

You want to change it to a left fold. Roughly speaking you want this:

let addAll f l = List.fold_left f 0 l

Or, slightly more accurately you want:

let addAll f = function
| [] -> 0
| h :: t -> List.fold_left f h t

This second function does seem to do what you want:

# addAll (-) [1;2;3];;
- : int = -4

If you want to write it from scratch (not using List.fold_left), the easiest way is with an accumulator:

let addAllScratch f l =
    let rec iadd f accum l =
        match l with
        | [] -> accum
        | a::l -> iadd f (f accum a) l
    in
    match l with
    | [] -> 0
    | h :: t -> iadd f h t

This does do what you want:

# addAllScratch (-) [1;2;3];;
- : int = -4

(In essence, I just inserted the standard definition of List.fold_left into the code.)

Upvotes: 2

V. Michel
V. Michel

Reputation: 1619

let rec addAll f l =
  match l with
  | []       -> 0
  | [x]      -> x
  | x::y::tl -> addAll f ((f x y)::tl) 
;;

Test

# addAll (fun a b -> Printf.printf "(%d %d)" a b; a+b) [1;2;3];;
(1 2)(3 3)- : int = 6

Upvotes: 1

Related Questions