How do I create a dictionary in OCaml that associates to each element of the first list the number of its occurences in the second list?

I have two lists, ["0","1"] and ["0","1","0"], and I want to get a list, [(0,2),(1,1)], - which associates to each element of the first list the number of its occurrences in the second list. I tried this:

let partialSolution = 
List.map(
    fun x -> 
        let subsubList = List.for_all  (fun y -> (String.compare x y)=0) ) ("0"::("1"::("0"::[]))) in
 (x, List.length ( List.filter ( fun z -> z = true) subsubList ) ) 
) ;;

, but it's not good: it gives me these errors:

# let partialSolution = 
# List.map(
#     fun x -> 
#         let subsubList = List.for_all  (fun y -> (String.compare x y)=0) )
File "", line 4, characters 73-74:
Error: Syntax error: operator expected.
#  ("0"::("1"::("0"::[]))) in
File "", line 4, characters 99-101:
Error: Syntax error
#  (x, List.length ( List.filter ( fun z -> z = true) subsubList ) ) 
# )
File "", line 6, characters 0-1:
Error: Syntax error
#  ;;
File "", line 6, characters 2-4:
Error: Syntax error

I would like to understand how I can fix this - I am a total newbie to OCaml.

Solution

You're a bit overzealous with the parentheses. The syntax error is caused by an extra closing parentheses after (fun y -> ...).

But you'll still have a type error, since List.for_all returns a bool, true if all items satisfy the predicate and false otherwise. It seems you want to use List.map here instead.

You also don't need to surround every use of :: with parentheses. ("0"::"1"::"0"::[]) is fine, but you can also just reduce this to a simple list literal: ["0"; "1"; "0"]. Additionally, z = true is equivalent to z, though perhaps slightly less readable.

This compiles. I haven't checked whether it actually does what you want though:

let partialSolution = 
    List.map
        begin fun x -> 
            let subsubList =
                List.map
                    (fun y -> String.compare x y = 0)
                    ["0"; "1"; "0"]
            in
            (x, List.length (List.filter (fun z -> z) subsubList)) 
        end

Also, if you're using 4.03 or higher you can use String.equal, and if you're using 4.08 you can use Fun.id instead of the ad hoc lambda functions:

let partialSolution = 
    List.map
        begin fun x -> 
            let subsubList =
                List.map (String.equal x) ["0"; "1"; "0"]
            in
            (x, List.length (List.filter Fun.id subsubList)) 
        end

Or instead of dealing with an intermediate bool list, you could use List.fold_left to do a count directly:

let partialSolution = 
    List.map
        begin fun x -> 
            let count =
                List.fold_left
                    (fun count y ->
                        if String.compare x y = 0 then
                            count + 1
                        else
                            count)
                    0 ["0"; "1"; "0"]
            in
            (x, count) 
        end