CODEWITHSUNDEEP
ocaml
Jonathan Bishop
Jonathan Bishop

Reputation: 167

How to write a function to count the number of elements in a list?

How can I write a function using fold_left and not using fold to count the number of elements in a list?

I tried

 let rec count_elements l c =
     match l with
     |[] ->  c
     |h::t -> c = c+1

I don't believe this works, and I am not how to do this using fold_left, any guidance would be appreciated

Upvotes: 0

Views: 10320

Answers (2)

Lhooq
Lhooq

Reputation: 4441

To add some clarity to the answers, I'd like to stress some things :

fold_left is just a way of doing some operations on a list in a tail-recursive way. The best way to understand fold_left is to do your own implementation of it :

# let fold_left f acc l =
    let rec fr acc l =
      match l with
        | [] -> acc
        | hd :: tl -> fr (f acc hd) tl
    in fr acc l;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

That's exactly what length does when you write

# let length l = List.fold_left (fun c _ -> c + 1) 0 l;;
val length : 'a list -> int = <fun>

What happens is equivalent to :

# let length l =
    let rec lr acc l =
      match l with
        | [] -> acc
        | _ :: tl -> lr (acc + 1) tl
     in lr 0 l;;
val length : 'a list -> int = <fun>

So, the solution 

let rec length l =
  match l with
    | [] -> 0
    | _ :: tl -> 1 + length tl

corresponds to fold_right and is not tail-recursive.

Hoping this will clarify some things for you :-)

Upvotes: 4

alifirat
alifirat

Reputation: 2927

Using fold_left, you can do it like this :

# let size l = List.fold_left (fun acc _ -> acc + 1) 0 l;;
val size : 'a list -> int = <fun>
# size [1;2;3];;
- : int = 3
# size [];;
- : int = 0
#

You start with the accumulator 0 and then you add it +1 for every element in the list.

Upvotes: 1

Related Questions