Subject: Re: UNDERSTANDING LISTS

From: Paul Singleton <[email-masked]>
Date: Fri, 28 Apr 2000 12:50:53 +0100

"Richard A. O'Keefe" wrote:

> [snip]

> Prolog lists are identical to lists in (pure) Lisp, ML, Haskell, Clean,
> Hope, NPL, lots of other things.

> [snip]

> Not many things can be done with simple pattern matches,
> but that's true of any data structure.

Multilists and difference lists can (each) be concatenated by pattern
matching, which is advantageous (in runtime performance and source
conciseness) for *some* applications (where decomposition and their
non-canonicity are unimportant, among other things probably...)

Multilists have the further advantage that they can be built from proper
lists; difference-list versions of setof/3 (and relatives), atom_chars/2
etc. are not commonly available (and I guess there would be little point
providing portable implementations using append/3). 

It is unfortunate that the empty list is (conventionally and now standardly)
denoted by an atom, as this means that multilists of atoms (or constants,
or of any superset type of atoms) are ambiguous (i.e. '[]' could denote
no members, or one) (yes I know the quotes are spurious).

An example multilist app: I build somewhat abstract representations of
HTML bodies as multilists of "block" structures, some of which contain
multilists of "inline" structures (text fragments, image references, links);
ultimately these are traversed and converted to textual HTML.

This HTML-oriented data structure is designed with one main goal; that
the necessary effort of writing and evolving code to generate it is as low
as possible.

Difference lists are not an option, because many of the available reusable
procedures return proper lists only.

Appending proper lists involves extra copying at runtime and extra typing
at development time :-)

There seems no satisfactory way to eliminate the [] ambiguity, either by
forbidding empty lists in multilists, or by forbidding '[]' as an atom,
so I'm forced to wrap every atomic multilist member in some arbitrary
functor, which hinders my "minimal effort" aspirations...

Do Lisp, ML, Haskell, Clean, Hope, NPL etc. have this property?

Paul Singleton