[mercury-users] full and empty lists

[Ralph Becket]

Dave Slutzkin, Sunday, 13 January 2002:
> Hi all.
> 
> :- mode ne_tl_io == ground >> non_empty_list.
> :- mode ne_tl_in == non_empty_list >> non_empty_list.

You can use the built-in parametric modes in/1 and out/1 here to say the
same thing:

:- mode ne_tl_io == out(non_empty_list).
:- mode ne_tl_in == in(non_empty_list).

Why did you pick the name "ne_tl_io"?
                                 ^^
Surely you mean "ne_tl_out"?

> :- func empty_timeline = (timeline::out) is det.
> :- pred full_timeline(timeline::ne_tl_io) is semidet.
> 
> empty_timeline = [].
> full_timeline([_|_]).

The mode for full_timeline/1 is wrong.

If it is intended to construct a partially instantiated list then you
need

:- mode ne_tl_skel_out == out(bound([free | free])).

:- mode full_timeline(ne_tl_skel_out) is det.

However, I'm not sure that the current mode system will be happy with
the use of partially instantiated data (Dave?)


If it is intended to *match* against any non-empty list argument then just

:- mode full_timeline(in) is semidet.

will do.


If it is intended only to be *used* on non-empty inputs then

:- mode full_timeline(ne_tl_in) is det.

but that would be rather pointless since it's guaranteed to succeed for
all valid calls!

> Bascially - I was hoping that empty_timeline and
> full_timeline could be used in a switch statement the
> same way as [] and [_|_].

Okay, we have a summer student, Lars Yencken, who is setting about
adding support for this sort of thing.

The idea is that you could write something like this:

:- func empty_timeline = timeline.

:- func non_empty_timeline = timeline.
:- mode non_empty_timeline = out(bound([free | free])) is det.

:- all [X] promise_exhaustive_and_exclusive
	(	X = empty_timeline
	;	X = non_empty_timeline
	).

And then write code like

foo(empty_timeline) :- ...
foo(non_empty_timeline) :- ...

You couldn't use a pred for non_empty_timeline because the compiler
first translates your code into super-homogeneous normal form as

foo(HeadVar1) :- HeadVar1 = empty_timeline, ...
foo(HeadVar1) :- HeadVar1 = non_empty_timeline, ...

But if non_empty_timeline was a pred then you'd get a type mismatch -
HeadVar1 has type timeline whereas non_empty_timeline would have type
pred(timeline).

> Also, after a call to full_timeline, I was hoping that
> the compiler would realise that I had a non-empty list
> and so I could save this checking in many later
> predicates.  Another snippet:
> 
> :- pred crop_timeline(timeline::in,time::in,
> timeline::out) is det.

It's better style to use funcs when you have modes of this kind.

> crop_timeline(Line,T,NewLine) :-
>     Line = empty_timeline ,
>     NewLine = empty_timeline
> ;
>     full_timeline(Line) ,
>     % we know we have a non-empty list here
>     E = first_event(Line) ,
> .
> .
> .
> 
> Note the use of empty_timeline and full_timeline in
> the switch (are they guards?).  And also that
> first_event can be deterministic, because it takes a
> non-empty list so will always succeed.

If the compiler performed inlining before doing mode analysis, this
would (could be...) be true - but it would be more costly to do things
that way round.

For this example, it's definitely easier to just switch on [] and [_|_].
If you want to avoid checking later that you have a non-empty list then
you could do something like this:

crop_timeline([], _) = [].

crop_timeline(Line, T) = NewLine :-
	Line = [_|_],
	NewLine = crop_ne_timeline(Line, T).


:- func crop_ne_timeline(timeline, time) = timeline.
:- mode crop_ne_timeline(ne_tl_in, in) = out is det.

crop_ne_timeline(NELine, T) = NewLine :-
	...

Now the code for crop_ne_timeline/2 doesn't have to keep checking that
NELine is non-empty.

> Well, it doesn't work.  The compiler still sees this
> code as nondeterministic - I quote:
> 
> event.m:108:   In the return value of call to function
> `event:empty_timeline/0':
> event.m:108:   unification with `Line' can fail.
> event.m:111:   call to
> `full_timeline((event:ne_tl_io))' can fail.
> 
> However, it still works when I replace empty_timeline
> with [] and full_timeline with [_|_] - although
> without the mode benefits of non_empty_list.
> 
> Is there anything I can do about this?  Does anyone
> even understand the problem?  Otherwise I'll have to
> go back to the less modular, less deterministic
> version.

Hope the above helps.

- Ralph
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------