Define reverse using fold left

Question

I have this definition of fold left

let rec fold_left f lst u = match lst with
                            | [] -> u
                            |(h::t) -> fold_left f t ( f h u)

I have to define reverse using the fold_left above. I currently have

let reverse l1 = fold_left (fun x y -> y::x) l1 []

but I keep getting this error

Error: This expression has type 'a list
       but an expression was expected of type 'a
       The type variable 'a occurs inside 'a list

What am I missing here?

Some teachers do that to make students understand how it works. My only remark would be that, for fold_left, the accumulator is the second parameter, not the third one, so you might be confused when using List.fold_left. — Lhooq
– Lhooq, Commented Oct 17, 2017 at 7:32

glennsl · Accepted Answer · 2017-10-17 03:33:04Z

1

You just have the accumulator and next item turned around (y::x instead of x::y). This works:

let reverse l1 = fold_left (fun x y -> x::y) l1 []

answered Oct 17, 2017 at 3:33

glennsl

29.2k12 gold badges60 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

You can also write let reverse l = fold_left List.cons l []