Search code examples
ocaml

What's wrong with my attempt to add 1 to every element in my list in Ocaml?

I don't understand the error message I'm getting or what's wrong with what I'm trying to doenter image description here

I just want to use List.fold_left to apply my add1 function to this list [1,2,3]

My add1 function should just add 1 to each element, so I would get [2, 3, 4]

My main goal in doing this exercise is just to experiment with List.fold_left. I don't actually care about adding 1, I just choose that function because it seemed easy to write (I'm an ocaml beginner).

My ultimate goal is actually to populate the keys of a empty StringMap using List.fold_left and a function already written elsewhere, so if anyone has insight on that it would also be appreciated

Here's the 1st try (which I tried twice)

let rec add1 = function
  | [] -> []
  | h::t -> (h+1)::(add1 t) in List.fold_left add1 [1, 2, 3];;

Here's the 2nd try

 let a(b) =
let rec add1 = function
  | [] -> []
  | h::t -> (h+1)::(add1 t)
in 
let c = List.fold_left add1 b
in a [1,2,3];;
Solution

  • It may help you to see how fold_left can be implemented.

    let rec fold_left f init lst =
  match lst with
  | [] -> init
  | x::xs -> fold_left f (f init x) xs

    So consider what's happening when something like a sum function works, when implemented in term of fold_left.

    let sum lst = 
  fold_left (+) 0 lst

    If we evaluate sum [1; 2; 3; 4]:

    sum [1; 2; 3; 4]
fold_left (+) 0 [1; 2; 3; 4]
fold_left (+) (0 + 1) [2; 3; 4]
fold_left (+) (1 + 2) [3; 4]
fold_left (+) (3 + 3) [4]
fold_left (+) (6 + 4) []
10

    We can define map in terms of fold_left:

    let map f lst =
  let f' init x = f x :: init in
  fold_left f' [] lst

    Let's evaluate map (fun x -> x + 1) [5; 2; 6]:

    map (fun x -> x + 1) [5; 2; 6]
fold_left f' [] [5; 2; 6]
fold_left f' (5 + 1 :: []) [2; 6]
fold_left f' (2 + 1 :: [6]) [6]
fold_left f' (6 + 1 :: [3; 6]) []
[7; 3; 6]

    Now, because of the way we destructure and create lists, the result is backwards. we can overcome this with fold_left by reversing the resulting list.

    let map f lst =
  let f' init x = f x :: init in
  let lst' = fold_left f' [] lst in
  List.rev lst'

    Or with the |> operator:

    let map f lst =
  let f' init x = f x :: init in
  lst |> fold_left f' [] |> List.rev

    Taking this to the next level

    At each iteration, fold_left transforms the first element in a list and an accumulator, into the accumulator for the next iteration. If you want to apply this concept to your StringMap module, consider StringMap.empty which generates an empty StringMap.t, and StringMap.add which take a key, an associated value, and an existing map, and returns a new map with that added mapping.

    You can readily use fold_left to take an initially empty map and build it into a complete map step by step. The only question remaining will be what value you choose to associate with each string in your list.