[erlang-questions] View patterns

ok <>
Wed Jul 25 04:13:27 CEST 2007


Haskell is starting to eat Erlang's lunch, except for hot loading.
Data.ByteString (and especially Data.ByteString.Lazy) is an effective
replacement for Erlang binaries, with support for packing and unpacking
stuff.  There's even talk about an analogue of 'bit syntax'.

One of the things which is about to be added to GHC is view patterns.
The idea is that if E is an expression and P is a pattern, then
	(E -> P)
is a pattern.  This pattern matches a value V if and only if
P = (E)(V).

Here's an example in Erlang syntax.

	min_list([]) -> empty;
	min_list([X|Xs]) -> min_list_loop(Xs, X, []).

	min_list_loop([], X, Zs) -> {min,X,Zs};
	min_list_loop([Y|Ys], X, Zs) when Y < X ->
	    min_list_loop(Ys, Y, [X|Zs]);
	min_list_loop([Y|Ys], X, Zs) ->
	    min_list_loop(Ys, X, [Y|Zs]).

Given the function min_list/1, we can now write selection sort:

	selection_sort((min_list -> empty)) ->
	    [];
	selection_sort((min_list -> {min,X,Xs})) ->
	    [X | selection_sort(Xs)].

This renders "as"-patterns obsolete.  With the aid of

	both(X) -> {X,X}.

we can write

	add_leaf(Datum, Tree = {fork,Size,Left,Right}) -> ...

as

	add_leaf(Datum, (both -> {Tree,{fork,Size,Left,Right}})) -> ...

People who dislike n+k patterns in Haskell can no longer hurt us much
by taking them out.  With the aid of

	np(K, X) when integer(X), integer(K), X >= K ->
	    {X};
	np(_, _) ->
	    false.

we can rewrite

	factorial(0) -> 1;
	factorial(N+1) -> (N+1)*factorial(N).

as

	factorial(0) -> 1;
	factorial((np(1) -> {N})) -> (N+1)*factorial(N).

Haskell view patterns are both more and less general than my abstract
patterns (which turned out to have been a reinvention of the original
view idea).  They are less general because they cannot be used as
constructors.  Apparently every view proposal that does that has run
into trouble, although reading some of the papers it doesn't seem to
me that the trouble would be anywhere near as acute in Erlang, in which
equational reasoning isn't valid anyway.  They are more general in that
the functions can be any function at all, whereas abstract patterns are
limited to non-recursive stuff, so cannot do the selection sort example
at all (probably a Good Thing).

I haven't told the whole story about Haskell view patterns; you'll find
that on the Haskell wiki.  But it suggests to me that we might want to
think about moving abstract patterns in Erlang a little higher up the
agenda.





More information about the erlang-questions mailing list