Why is the OCaml pattern weaker than Erlang?

Question

I am new to OCaml and reading the book Real World OCaml (RWO). Pattern matching is described in Chapter 3 and seems weak compared to Erlang (or Prolog) pattern matching.

My questions:

• Why is the OCaml pattern weaker?
• Are there any advantages to the OCaml style for pattern matching?

Specific example:

The following function (taken from RWO p. 63) destroys the list

let rec destutter list = match list with | [] -> [] | [hd] -> [hd] | hd :: hd' :: tl -> if hd = hd' then ds1 (hd' :: tl) else hd :: ds1 (hd' :: tl) ;; # destutter [1;2;3;3;4;5;5;6];; - : int list = [1; 2; 3; 4; 5; 6] 

In Erlang, it would be possible (and, it seems to me, preferable) to use pattern matching instead of conditional:

 destutter([]) -> []; destutter([X]) -> [X]; destutter([H,H|T]) -> destutter([H|T]); destutter([H|T]) -> [H | destutter(T)]. 

An attempt of this type in OCaml ...

 let rec destutter list = match list with | [] -> [] | [hd] -> [hd] | hd :: hd :: tl -> destutter tl (* error *) | hd :: tl -> hd :: destutter tl ;; 

... causes an error on the marked line:

 Error: Variable hd is bound several times in this matching 

So, Erlang / Prolog pattern matching in OCaml does not work. What for? What are the benefits of the OCaml approach?

With thanks and best regards

Ivan

Answer 1

The Erlang template is more powerful because it can match something specific at runtime. OCaml samples are mapped to strings set at compile time. It follows that OCaml templates can probably be accelerated. I also find that OCaml style templates are easier to reason about.

Answer 2

First, you can always fix the equality between template variables using the when clause in OCaml, for example:

 let rec destutter = function | [] -> [] | [hd] -> [hd] | hd :: hd' :: tl when hd = hd' -> destutter (hd :: tl) | hd :: hd' :: tl -> hd :: destutter (hd' :: tl) 

There is a compromise here. Although Erlang is more expressive, OCaml pattern matching is simpler (meaning a simpler language definition, compiler, etc.), and you can still do what you need (by writing more code).

Note that while you can rewrite a non-linear pattern as a linear pattern with the when clause, this is not a major issue. More critically, pattern matching should then have the notion of equality for arbitrary types in order to support non-linear patterns. This is not a problem in Erlang, but OCaml not only has a built-in = vs == (structural equality versus identity), but for any given type it may not be the equality you need (for example, thought strings and case sensitivity). Then, as a result, exhaustiveness or overlap testing becomes non-trivial. In the end, it is doubtful whether it is worth providing a special case for one particular type of equality, given how many useful relationships between parts of the template can be. (I note that non-strict languages ​​have additional problems.)

In contrast, Prolog pattern matching is based on unification and is strictly more powerful than Erlang or OCaml (but also harder to implement).

Answer 3

The templates in OCaml are compiled into very efficient code with a lot of complex optimizations . Bjarne Stroustrup even boasted that they were able to write something comparable in some cases in C ++. But in general, the OCaml template is much faster. And his charming look at the assembly. And perhaps Erlang provides more flexibility, but is expected from a dynamic language. Otherwise, why use them at all.

There is another problem. Patterns are mapped structurally. If you want to combine [H,H|T] , you are actually invoking the comparison of the first two elements. In most cases, the comparison function should be provided by the user, and it is not known in advance.