CODEWITHSUNDEEP
pattern-matchingocamltypechecking
LeT
LeT

Reputation: 37

Finding the different elements of an int list

I am still new to OCaml, and want to write a function to find the alphabet, or the different individual numbers of an int list and return them as a list. I came up with the following:

let rec find_alpha (list: int list) (acc: int list) =
   match list with
   |[]       -> acc
   |hd       -> if List.mem hd acc then acc else hd::acc
   |hd::tl   -> if List.mem hd acc then find_alpha tl acc else find_alpha tl hd::acc

The compiler says:

|hd       -> if List.mem hd acc then acc else hd::acc
                            ^^^
Error: This expression has type int list but an expression was expected of type int list list
Type int is not compatible with type int list.

Even though the message is quite explicit I can not figure out why an expression of type int list list was expected. I check whether the hd element is already in the acc list. If it is, I return the acc as my result, if it was not in the acc I append it and return it.

Why is int list list expected?

I forgot to say, the first case [] should not be reachable, but I still included it for I don't know what reason. I should cut it out shouldn't I?

Upvotes: 3

Views: 257

Answers (2)

Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'

Reputation: 107759

In the second line of the pattern matching, you use hd as the pattern. This pattern matches any value and calls it hd. This makes hd an int list in the line

|hd       -> if List.mem hd acc then acc else hd::acc

When the compiler typechecks the call to List.mem, it happens to analyze the first argument first. Since the compiler already knows that hd has the type int list at this point, it infers that the second argument must have the type int list list, due to the type of List.mem (which is 'a -> 'a list -> bool, with 'a instantiated to int list here). If the function List.hd took its arguments in the opposite order or the compiler typechecked function calls in the opposite order, the complaint would have been that hd had the type int list but was used with the type int.

I'm not sure what you meant with this line. A list either is empty, or has a head and a tail. (I don't know why you think that “the first case [] should not be reachable”; a list certainly can be empty.) The usual pattern matching on a list is

match list with
| []       -> …
| hd::tl   -> …

and in your case you don't need anything more complicated. You can take your existing cases for [] and hd::tl. There's just one more thing to correct: you need to put parentheses in the recursive call find_alpha tl (hd::acc), because find_alpha tl hd::acc is parsed as (find_alpha tl hd)::acc.

let rec find_alpha (list: int list) (acc: int list) =
   match list with
   |[]       -> acc
   |hd::tl   -> if List.mem hd acc then find_alpha tl acc else find_alpha tl (hd::acc)

Since the only variation in the hd::tl case is in the second argument passed to the recursive call, I prefer not to repeat the recursive call. Furthermore the functions don't depend on the type of the arguments, so I would let them stay polymorphic.

let rec find_alpha list acc =
   match list with
   | [] -> acc
   | hd::tl -> find_alpha tl (if List.mem hd acc then acc else hd::acc)

The code is arguably more readable if you define an intermediate variable.

let rec find_alpha list acc =
   match list with
   | [] -> acc
   | hd::tl ->
     let acc' = if List.mem hd acc then acc else hd::acc in
     find_alpha tl acc'

Upvotes: 2

octachron
octachron

Reputation: 18902

| hd -> if List.mem hd acc then acc else hd::acc

This case means "match the whole list and name it hd in the following" compared to 

| [hd] -> if List.mem hd acc then acc else hd::acc

which means "match a list with only one element and name it hd.

In particular, with

| hd -> if List.mem hd acc then acc else hd::acc

List.mem hd acc is checking if the list of int hd belongs to the list acc. This can only makes sense if acc is a list of list of int. However, you precised that acc was a list of int; yielding the compiler error that you saw.

Upvotes: 1

Related Questions