[m-users.] Pattern matching in Mercury

[Paul Bone]

On Sun, Oct 26, 2014 at 06:14:18PM +1100, Roger Qiu wrote:
> Ok so deterministic and semi-det functions and predicates requires that  
> there can only be 1 valid clause (mutually exclusive clauses). The thing  
> I’m confused about is how to reconcile this requirement with this simple  
> example:
>
> |:- func convert(int) = string.
> convert(1) = "good".
> convert(_) = "bad".
> |
>
> The above kind of setup would work in Erlang, in the sense I can pass 1,  
> and then get “good” and if I pass anything else I would get “bad”.  
> However such a thing is not possible in Mercury as if I pass 1, both  
> clauses execute which of course results in an error.

Mercury isn't Erlang.  What I mean by this is that design choices like this
arn't right or wrong, they're just different or farmiliar and unfarmiliar.
I don't mean to imply that you said or implied that there is a right and
wrong, but it doesn't hurt to remind everyone that "different" is okay.

> I was suggesting that perhaps a guard clause would help here, so that I  
> can still do pattern matching and ensure that there was only 1 valid  
> clause by guarding /against/ 1 on the second convert clause.

In this case I don't see the problem with an if-then-else (ITE).  Because
ITE goals can be chained:

something(X) = 
    ( X = 1 ->
        "good"
    ; X = 2 ->
        "better"
    ;
        "Pretty damn awesome"
    ).

Guards don't help us to avoid nesting becase we can already do that.  What
they do help with is ensuring that this code still looks like multiple
clauses.

something(X) X = 1 ! = "good".
something(X) X = 2 ! = "better".
something(X) otherwise ! = "Pretty damn awesome".

So this makes the code shorter but it may not necessarily help making it
more readable.  For instance, it makes these lines longer which, if there's
a long predicate name or a long argument list the code may become less
readable.

hat I'd look for is an example where the guards make the program
_obviously_ more readable - and sufficiently enough to motivate several
developers especially those that end up implementing and maintaining the new
feature.

>
>    This leads to programs that tend to use structual induction-like
>    predicate definitions.
>
> Can you give me some examples as to what you’re referring to?

Structual induction is a methematical logic thing.  But it can be seen in
programming when your code closely matches the same "shape" as your
datatype.

    length([], 0).
    length([_ | Xs], L + 1) :-
        length(Xs, L).

The list has two constructors, nil and cons, the clauses match against each
constructor.

A more complicated example.  The cord datatype (see library/cord.m) here
I've simplified it to remove details not important to the discussion.  Cords
are like lists but they have a constant time append operation but other
operations may be faster or slower.

    :- type cord(T)
        --->    nil
        ;       unit_node(T)
        ;       list_node(list(T))
        ;       branch_node(cord(T), cord(T)).

    head_tail(Node, Head, Tail) :-
        (
            Node = nil,
            false
        ;
            Node = unit_node(Head),
            Tail = nil 
        ;
            Node = list_node(List),
            (
                List = [],
                false
            ;
                List = [Head | TailList],
                Tail = list_node(TailList)
        ;
            Node = branch_node(A0, B),
            head_tail(A0, Head, A),
            (
                A = nil,
                Tail = B
            ;
                ( A = unit_node(_)
                ; A = list_node(_)
                ; A = branch_node(_, _)
                ),
                Tail = branch_node(A, B)
            )
        ).

Note that one of the key things that structual induction gives you, is
whereever there's recursion in your type definition.  (List's tail is another
list, and cords's branch_node cotains two cords.)  The algorithm recurse when
it needs to process these elements.  In the cord example we also do the same
thing when taking the head element out of the list, and when processing A,
the result of a recursive call to head_tail in order to decide how to
construct the result Tail.

This is often an obvious way to write such a predicate, but formalising it
as structual induction can help.



-- 
Paul Bone