Let the OCaml code fit input as either int or list

Question

let rec fold_inorder f acc t =
  match t with
  | Leaf           -> acc
  | Node (l, x, r) -> 
      let ar = fold_inorder f acc r in
      let an = x :: ar in
      fold_inorder f an l;;

I'm trying to print the infold of a tree as following :

assert (
  fold_inorder
    (fun acc x -> acc @ [x])
    []
    (Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)))
  = [1; 2; 3] ) ;

assert (
  fold_inorder
    (fun acc x -> acc + x)
    0
    (Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)))
  = 6 )

The first one worked, but second I got this error:

Error: This expression has type int but an expression was expected of type
         'a List.t = 'a list

So how can I adjust it to fit either int or list?

Answer 1

When you are writing

    let an = x :: ar in
    fold_inorder f an l

you are building a list accumulator using the List.cons function.

This is not fold but a to_list function which is a special case of fold.

Hint: you need to use the f function in the body of fold_inorder.