Subject: Re: [SWIPL] keysort

From: Paul Singleton <[email-masked]>
Date: Tue, 20 Feb 2001 12:57:41 +0000

"Richard A. O'Keefe" wrote:

> Assuming for the sake of argument that they represent weighted edges in
> a graph, a better representation (requiring less space to store it and
> less time to process it) would be
>         [edge(a,b,2), edge(a,c,3), edge(a,b,1),
>          edge(b,a,5), edge(d,c,4), edge(f,r,6)].
> Whatever they represent, a compound term with a well-chosen word to label
> it would be a better choice than a list.

I think there's a case for choosing a compound term to represent the arc:

          a-b

and a compound term to represent the weighted arc:

          (a-b)-2

where -/2 is -(well,chosen) if you have a library of predicates for
manipulating lists of pairs (keysort and much more), and another library
of graph operations on lists of arcs (NB this is not a great graph ADT,
but it has its uses), in each case using the functor -/2

I only mention this to illustrate a weakness of Prolog (compared to e.g.
Java) in defining new types: it doesn't support implementation inheritance,
so I cannot define a specialisation of an old type which both inherits
useful operations yet has its own identity (for polymorphism etc.).

E.g. ordsets are conventionally represented as, and indistinguishable
from, lists.

So there often seems to be a conflict between choosing a data structure
for design-time efficiency and choosing it for run-time efficiency, and
between expressing its particular semantics and compactly representing
its essential structure.

Is this inherent in a dynamically typed language?

Are there any general techniques for gettiong the best of both worlds?

Paul Singleton