interval to a list
Author Message
interval to a list

hey,

I have to write follow predicate:

interval/3

e.g. interval(2,5,List).

List = [2,3,4,5].

Who is able to help me.

Thank you very much.

Dominique Busch

Thu, 22 Jul 1999 03:00:00 GMT
interval to a list

Quote:
>e.g. interval(2,5,List).

>List = [2,3,4,5].

interval(X,X,[X]).
interval(A,B,[A|Rest]):-
NewA is A+1,
interval(NewA,B,Rest).
--
--
-------------------------------------------------------------------------

:WWW Page/s   : http://www.tardis.ed.ac.uk/~alan/             (Personal):
-------------------------------------------------------------------------
"Some men see things as they are and say 'why?' I dream things that never
were and say 'why not?'"                                [Robert F.Kenedy]
=========================================================================

Sat, 24 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> >e.g. interval(2,5,List).

> >List = [2,3,4,5].

> interval(X,X,[X]).
> interval(A,B,[A|Rest]):-
>         NewA is A+1,
>         interval(NewA,B,Rest).

I'm sure you meant to say:

interval( A, B, [A|Rest] ):-
A < B,
NewA is A+1,
interval( NewA, B, Rest ) .
interval( X, X, [X] ).

--
Regards,

John Fletcher

Sun, 25 Jul 1999 03:00:00 GMT
interval to a list

Quote:

>> >e.g. interval(2,5,List).

>> >List = [2,3,4,5].

>> interval(X,X,[X]).
>> interval(A,B,[A|Rest]):-
>>         NewA is A+1,
>>         interval(NewA,B,Rest).

>I'm sure you meant to say:

>interval( A, B, [A|Rest] ):-
>    A < B,
>    NewA is A+1,
>        interval( NewA, B, Rest ) .
>interval( X, X, [X] ).

I'm won't claim to know what Alan Ogilvie intended, but his code is
certainly broken, and inserting a call to `<' does avoid the infinite loop.

I'm not quite sure why you reordered the clauses, though.
It can't be for performance, since in this example putting
the base case last result in performance that is either the
same, if your Prolog compiler is smart, or (more likely!)
performance that is significantly worse.
It certainly doesn't improve readability, at least not in my opinion.
(How many maths textbooks list the base cases of definitions
or proofs after the recursive cases?  None that I've seen.)

Note that unless you are assuming that your Prolog compiler is quite
smart, your code has a performance bug, because it leaves lots of
choice points around.  This will have the further effect of preventing
the system from reclaiming garbage, so your code can cause space leaks.

This is a good example of why Prolog is IMHO an awful language to use
if you're the least bit interested in performance.

--

WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"

Sun, 25 Jul 1999 03:00:00 GMT
interval to a list

Quote:

>  >> interval(X,X,[X]).
>  >> interval(A,B,[A|Rest]):-
>  >>         NewA is A+1,
>  >>         interval(NewA,B,Rest).

>  >I'm sure you meant to say:

>  >interval( A, B, [A|Rest] ):-
>  >       A < B,
>  >       NewA is A+1,
>  >        interval( NewA, B, Rest ) .
>  >interval( X, X, [X] ).

> I'm won't claim to know what Alan Ogilvie intended, but his code is
> certainly broken, and inserting a call to `<' does avoid the infinite loop.

That's why I put it in :)

Quote:
> I'm not quite sure why you reordered the clauses, though.
> It can't be for performance, since in this example putting
> the base case last result in performance that is either the
> same, if your Prolog compiler is smart, or (more likely!)
> performance that is significantly worse.

The reordering of the clauses was a 'hint' cf: "how I knew it was broken
without testing it". The broken version will survive very rudimentary
tests _because_ of its clause ordering; the corrected version will
survive much more severe tests _irrespective_ of clause ordering.

Quote:
> (How many maths textbooks list the base cases of definitions
> or proofs after the recursive cases?  None that I've seen.)

the original faulty code.......

Quote:
> Note that unless you are assuming that your Prolog compiler is quite
> smart, your code has a performance bug, because it leaves lots of
> choice points around. This will have the further effect of preventing
> the system from reclaiming garbage, so your code can cause space leaks.

How do you know? If the code is usually called with an interval size of
1 or 2 the reordered clauses might be better. It's always dangerous to
make generalisations about performance, not that you'd ever guess from

Quote:
> This is a good example of why Prolog is IMHO an awful language to use
> if you're the least bit interested in performance.

Here I go again, claiming to know what people meant to say: "This is a
good example of why Prolog is I(Fergus')HO an awful language to use if
you're obsessed by performance." :)

--
Regards,

John Fletcher

Sun, 25 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> I'm not quite sure why you reordered the clauses, though.
> It can't be for performance, since in this example putting
> the base case last result in performance that is either the
> same, if your Prolog compiler is smart, or (more likely!)
> performance that is significantly worse.
> It certainly doesn't improve readability, at least not in my opinion.
> (How many maths textbooks list the base cases of definitions
> or proofs after the recursive cases?  None that I've seen.)

> Note that unless you are assuming that your Prolog compiler is quite
> smart, your code has a performance bug, because it leaves lots of
> choice points around.  This will have the further effect of preventing
> the system from reclaiming garbage, so your code can cause space leaks.

> This is a good example of why Prolog is IMHO an awful language to use
> if you're the least bit interested in performance.

I don't know whether you consider the following more readable or not,
but it should be more efficient, and it covers all the cases properly:

interval(A, B, Result) :-
interval(A, B, Result, []).

/* Use DCGs to build up the list */

interval(A, B) -->
(  {A =< B}
-> {A2 is A+1},
[A],
interval(A2, B)
;  []
).

--
Peter Ludemann          +1.415.813.6806  (fax: +1.415.813.7499)

InXight Software, Inc.  http://www.inxight.com
PAHV 105, 3400 Hillview  Ave., Palo Alto, CA 94304

Sun, 25 Jul 1999 03:00:00 GMT
interval to a list

] >

] >

] >  >>
] >  >> interval(X,X,[X]).
] >  >> interval(A,B,[A|Rest]):-
] >  >>         NewA is A+1,
] >  >>         interval(NewA,B,Rest).
] >  >
] >  >I'm sure you meant to say:
] >  >
] >  >interval( A, B, [A|Rest] ):-
] >  >       A < B,
] >  >       NewA is A+1,
] >  >        interval( NewA, B, Rest ) .
] >  >interval( X, X, [X] ).
] >
] > I'm won't claim to know what Alan Ogilvie intended, but his code is
] > certainly broken, and inserting a call to `<' does avoid the infinite loop.
]
] That's why I put it in :)
]
] > I'm not quite sure why you reordered the clauses, though.
] > It can't be for performance, since in this example putting
] > the base case last result in performance that is either the
] > same, if your Prolog compiler is smart, or (more likely!)
] > performance that is significantly worse.
]
] The reordering of the clauses was a 'hint' cf: "how I knew it was broken
] without testing it".

Ah, I see.  Fair enough.

] > Note that unless you are assuming that your Prolog compiler is quite
] > smart, your code has a performance bug, because it leaves lots of
] > choice points around. This will have the further effect of preventing
] > the system from reclaiming garbage, so your code can cause space leaks.
]
] How do you know? If the code is usually called with an interval size of
] 1 or 2 the reordered clauses might be better.

In the case of an interval size of exactly 2, both versions (your code
and code with the original clause ordering) will leave a choice point
around, so although one may be marginally better than the other, they
*both* have a performance bug.  The only time that you don't have a
performance bug is if you *know* that the interval size will never be 2
or more (i.e. it is always size 1 or empty).  If you know that, and
your code relies on it, then you should at very least *document* that
assumption.  Furthermore, if you're going to make that assumption, then
you would probably be better off using a different algorithm (e.g.
there's no need for any recursion).

Anyway, the example that the original poster used

?- interval(2, 5, L).
L = [2,3,4,5]

makes it clear that he wanted it to work for interval sizes greater
than one.

] > This is a good example of why Prolog is IMHO an awful language to use
] > if you're the least bit interested in performance.
]
] Here I go again, claiming to know what people meant to say: "This is a
] good example of why Prolog is I(Fergus')HO an awful language to use if
] you're obsessed by performance." :)

Anyone who is the least bit interested in performance should
take space leaks seriously.

If we were just talking constant factors, then I wouldn't worry about
it.  But the performance bug here can make the difference between
a program that uses O(1) space and one that uses unbounded space,
i.e. between a program that works and a program that doesn't.

--

WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"

Mon, 26 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> <snip>

> Anyone who is the least bit interested in performance should
> take space leaks seriously.

I agree with your last comment entirely. My original solution was
emphasizing clarity rather than performance; the declarative rather than
the procedural interpretation. I consider it to be a benefit of Prolog
that I have that _choice_, and I'm happy to accept that the price is the
risk of poor performance.

If I was writing an 'interval to set' predicate from scratch, I would
write:

interval_to_set( From, To, [From|Rest] ) :-
( From =:= To ->
Rest = []
; From < To ->
Next is From + 1,
interval_to_set( Next, To, Rest )
).

which I believe to be readable, safe and efficient.

However, a problem remains: why have two representations of an interval?

--

Regards,

John Fletcher

Mon, 26 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> [...]
> If I was writing an 'interval to set' predicate from scratch, I would
> write:

> interval_to_set( From, To, [From|Rest] ) :-
>         ( From =:= To ->
>                 Rest = []
>         ; From < To ->
>                 Next is From + 1,
>                 interval_to_set( Next, To, Rest )
>         ).

> which I believe to be readable, safe and efficient.

> However, a problem remains: why have two representations of an interval?
> [...]

There are reasons to have both representations. The merits of the list
form for sets of integers are, I believe, obvious and unremarkable. The
interval form fort sets of integers can have a tremendous speed and
space advantage because it is, if you think about it, a compressed form
equivalent to run-length encoding (RLE).

I currently work with a warehouse of GIS data that is hundreds of
gigabytes in size and may reach terabytes before I leve the project. Whe
have data that would be as much as 100 times larger if we used sets of
mere integers instead of sets of integer intervals.

Using sets of intervals has its downside though, if the interval is part
of a unique key -- which it usually is in our case -- standard data
modeling techniques and tools, as well as DBMS declarations for
referential integrity, are not usable (not without hacking and cheating)
because the data isn't normalized, it's zeroth order.

On the side I've been looking at how to extend relational algebra to
rigorously support interval-encoded sets of integers. Once you have
that, you can then design properly normalized data models and treat the
intervals as a implementation issue of the physical data.

--

personal)
1801 California         (on assignment from Analysts International)
Suite 310
Denver, CO 80202        42 = the 8-bit checksum of the universe.
303-965-8473

Tue, 27 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> If I was writing an 'interval to set' predicate from scratch, I would
> write:

> interval_to_set( From, To, [From|Rest] ) :-
>    ( From =:= To ->
>            Rest = []
>    ; From < To ->
>            Next is From + 1,
>            interval_to_set( Next, To, Rest )
>    ).

> which I believe to be readable, safe and efficient.

Ummm ... with your definition, we have interval_to_set(7,5,X) failing.
Isn't it more reasonable to have interval_to_set(7,5,[])?  That's what
my solution provides, just as efficiently (using the more readable DCG
notation):

interval_to_set(From, To, Result) :-
interval(From, To, Result, []).

interval_to_set(From, To) -->
(  {From =< To}
-> {FromNext is From + 1},
[From],
interval_to_set(FromNext, To)
;  []
).

Quote:
> However, a problem remains: why have two representations of an interval?

Why stop at just two?  I can think of many different representations
that make sense under different circumstances; just as I can think of
many different represetnation for sets.  The important thing is to
define the abstraction layers so that the representation doesn't
matter, except as an efficiency consideration.

--
Peter Ludemann          +1.415.813.6806  (fax: +1.415.813.7499)

InXight Software, Inc.  http://www.inxight.com
PAHV 105, 3400 Hillview  Ave., Palo Alto, CA 94304

Tue, 27 Jul 1999 03:00:00 GMT
interval to a list

Quote:

>>  >> interval(X,X,[X]).
>>  >> interval(A,B,[A|Rest]):-
>>  >>         NewA is A+1,
>>  >>         interval(NewA,B,Rest).

>>  >I'm sure you meant to say:

[...snip]

Okay, so in actual fact. When I originally hashed the predicate into
my version of Sicstus I did check that A<B in predicate/3 rule. If you
insist that you are never going to redo it, then it works without it,
hence this is why I dropped it from my posted code. But I see now that
it is necessary _if_ you are going to make it redo.

Quote:
>> I'm not quite sure why you reordered the clauses, though.
>> It can't be for performance, since in this example putting
>> the base case last result in performance that is either the
>> same, if your Prolog compiler is smart, or (more likely!)
>> performance that is significantly worse.
>The reordering of the clauses was a 'hint' cf: "how I knew it was broken
>without testing it". The broken version will survive very rudimentary
>tests _because_ of its clause ordering; the corrected version will
>survive much more severe tests _irrespective_ of clause ordering.

Yes, but then I like to put base cases before others, unless there is
a specific reason for doing so (and if there is I frown upon the code,
and think that there must be some other way to do it - which usually
results in better efficiency). So, in my eyes the reordered version
_looks_ worse and is probably less efficient....

Quote:
>> (How many maths textbooks list the base cases of definitions
>> or proofs after the recursive cases?  None that I've seen.)
>the original faulty code.......

before.  Possibly more commonly known as 'a stupid mistake', 'a bug',
'a feature', or 'doing a Micro\$oft'.

Quote:
>> Note that unless you are assuming that your Prolog compiler is quite
>> smart, your code has a performance bug, because it leaves lots of
>> choice points around. This will have the further effect of preventing
>> the system from reclaiming garbage, so your code can cause space leaks.

Choice points are highly difficult to notice (or at least I find
this), perhaps someone just never explained to to me correctly. But
then my theory above of reordering probably sorts this out...

Quote:
>How do you know? If the code is usually called with an interval size of
>1 or 2 the reordered clauses might be better. It's always dangerous to
>make generalisations about performance, not that you'd ever guess from

...on the other hand, maybe it doesn't...

Quote:
>> This is a good example of why Prolog is IMHO an awful language to use
>> if you're the least bit interested in performance.
>Here I go again, claiming to know what people meant to say: "This is a
>good example of why Prolog is I(Fergus')HO an awful language to use if
>you're obsessed by performance." :)

Prolog vs Performance - an interesting point. From what I've done with
it (Artificial Intelligence) I really haven't had many performance
problems, but then I am using a SparcStation 5, and if I use my
reordering theory I laid out above, then usually have no problems.

--
--
-------------------------------------------------------------------------

:WWW Page/s   : http://www.tardis.ed.ac.uk/~alan/             (Personal):
-------------------------------------------------------------------------
"Some men see things as they are and say 'why?' I dream things that never
were and say 'why not?'"                                [Robert F.Kenedy]
=========================================================================

Thu, 29 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> However, a problem remains: why have two representations of an interval?

As others have pointed out (and I will also becaue it *so* important), the
more representations you can think of the better!  Finding a good way to
represent data is often the key to solving problems efficiently.

One of my favourite example is representing graphs - look up a text book on
data structures and the chances are it will talk about adjacency lists and
matrices.  Each node will be represented as an integer.  The "direct"
representation using pointers might also be mentioned.  To represent the
game tree of Go you would need squillions of terabytes of memory, not to
mention bignums for the nodes.  Yet anyone who has passed an AI course
should be able to tell you that the graph can be represented in a few
kilobytes (the *code* for the edge or "successor" relation).

Here is another favourite of mine I came up with for my Logic Programming
Techniques class: write a predicate which checks that all leaves of a binary
tree (represented with t/3 and nil) are at the same level.  I'll spare you
the gross coding I gave the students.  As an exercise you might like to
come up with the "obvious" version and the "nice" version and show how the
nice version can be over a million times as fast!

lee

Fri, 30 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> > However, a problem remains: why have two representations of an interval?

> As others have pointed out (and I will also becaue it *so* important), the
> more representations you can think of the better!

Just make sure you don't use them all in your program :) Simply,
transforming one representation into another doesn't add any value; so,
presumably, there must be a good reason for using more than one
representation in a program.

Quote:
> Finding a good way to represent data is often the key to solving problems
> efficiently.
> <snip>

Yes, of course.

However, my question was concerned with _intervals_. I was wondering why
the original poster wanted to convert the interval to a list in the
first place ie. "What can you do with an interval represented as a _list
of integers_ that doesn't work _at least as well_ with a _pair of
integers_?"

--
Regards,

John Fletcher

Sat, 31 Jul 1999 03:00:00 GMT
interval to a list

Quote:

>I was wondering why
>the original poster wanted to convert the interval to a list in the
>first place ie. "What can you do with an interval represented as a _list
>of integers_ that doesn't work _at least as well_ with a _pair of
>integers_?"

Well, for one thing you can reuse all those list-processing predicates

--

WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"

Sat, 31 Jul 1999 03:00:00 GMT
interval to a list

Quote:

> However, my question was concerned with _intervals_. I was wondering why
> the original poster wanted to convert the interval to a list in the
> first place ie. "What can you do with an interval represented as a _list
> of integers_ that doesn't work _at least as well_ with a _pair of
> integers_?"

I can't speak for the original poster, however I have had to support
syntax rich enough to express both intervals and set enumeration and
have them interact.
Here is a (silly) example query and response from such an interpreter.

?- (1 .. 6) union {5,7,9,11}
{1, 2, 3, 4, 5, 6, 7, 9, 11}

It was not feasible considering the range of other objects in this
language to express them all as lists of intervals.
Now whether you ever explicitly _convert_ intervals to lists
is probably a question of taste, but there are instances where
it is necessary to extract all the elements of an interval
and have them end up as elements of a list.

I do agree with your sentiment though,
Dan Hazel

Sun, 01 Aug 1999 03:00:00 GMT

 Page 1 of 2 [ 21 post ] Go to page: [1] [2]

Relevant Pages