Re: Converting Scheme to Prolog

On Oct 5, 7:51 am, Jan Wielemaker <j...@xxxxxxxxxxxxxxxxxxx> wrote:
On 2007-10-05, Pierpaolo BERNARDI <pierpa...@xxxxxxxxxxxxx> wrote:

On Thu, 04 Oct 2007 23:09:01 +0200, Chip Eastham <hardm...@xxxxxxxxx> wrote:

On Oct 4, 4:25 pm, pineapple.l...@xxxxxxxxx wrote:

You speak of an "islist" test. I am not aware of this. Is this
a built-in predicate? And is this the preferred way of doing this
sort of thing (testing for a list?).

In both Amzi! Prolog and SWI-Prolog there's a built-in predicate
is_list/1, which succeeds either for something that unifies with
[H|T] or with the empty list, [ ]. So there's a little room for
discrepancy.

To be precise, at least in SWI-Prolog, is_list/1 checks that its argument
is a *proper* list.

I have the impression the community wants to phase out the term
*proper* list. A list is [] or [_|<a list>]. In addition we have a
_partial_ list, which is a variable or [_|<partial list>]. [a|a] is
just a term, most likely unintended. Very old versions of SWI-Prolog
had is_list as

is_list(X) :- var(X), !, fail.
is_list([]).
is_list([_|_]).

and proper list doing what is_list is doing now. Recent versions also
check for cycles, so X = [_|X], is_list(X) fails, as it should.

is_list([a|a]) will fail.

The implication of this is that is_list/1 is O(n) for lists of length n.
Not knowing this fact, one can easily transform a simple linear predicate
to a quadratic one. :)

The consequence is indeed that you should not use is_list/1 in loops.
Use it for a proper type test at entry of the predicate and than use
[] and [_|_] to process the list. Good news is that you are garanteed
to terminate :-)

Cheers --- Jan

Ok folks, last problem/question. As I mentioned earlier in my thread,
I wanted to convert a Scheme program that did the following;

(ncombs n L) returns a list containing lists of size n, one for each
combination of size n from the elements of L. Such that
(ncombs 4 '(a b c d e))

would return

((e d c b) (e d c a) (e d b a) (d c b a) (e c b a)).

I finally figured it out with the following;

ncombs(0, _, []).
ncombs(N, [X | L], [X | L1]) :- N > 0, M is N - 1, ncombs(M, L, L1).
ncombs(N, [_ | L], L1) :- N > 0, ncombs(N, L, L1).

ncombs(4, [a,b,c,d,e], L).

returns;
L = [a, b, c, d] ;

L = [a, b, c, e] ;

L = [a, b, d, e] ;

L = [a, c, d, e] ;

L = [b, c, d, e] ;

What I'm trying to figure out is, how can I make it return;

L = [[a, b, c, d][a, b, c, e][a, b, d, e]a, c, d, e][b, c, d, e]]

"and" not be truncated.

Thanks

.

Relevant Pages

  • Re: Converting Scheme to Prolog
    ... and proper list doing what is_list is doing now. ... one can easily transform a simple linear predicate ... returns a list containing lists of size n, ... (ncombs 4 '(a b c d e)) ...
    (comp.lang.prolog)
  • Re: Converting Scheme to Prolog
    ... one can easily transform a simple linear predicate ... Use it for a proper type test at entry of the predicate and than use ... returns a list containing lists of size n, ... (ncombs 4 '(a b c d e)) ...
    (comp.lang.prolog)
  • Re: I can not find a word better than "CAR"
    ... The Common Lisp standard defines the definitional terms ... proper list n. ... than Otime is not possible in CL --- because CL implements lists on ... top of cons cells and you need Ooperations to get to the last cons ...
    (comp.lang.lisp)
  • Re: An instance of Russells paradox?
    ... >>infinite generalization of the arity of every predicate (I got this ... the representation ... > of lists is actually syntactic sugar for the binary term ... notation, the list notation, and the operator notation. ...
    (sci.logic)
  • Re: backtracking in prolog
    ... The predicate is called foo for example (so foo takes two ... that does not satisfy the given predicate. ... backtracking, ... expect to happen for various lists that have more than ...
    (comp.lang.prolog)