Re: Sublists question

From: Bill Spight (Xbspight_at_pacbell.net)
Date: 03/24/04 

Date: Wed, 24 Mar 2004 20:55:48 GMT

Dear zeus,

Bart's comments are right on. :-)

> sublist(S,L):-append(_,S,P),append(P,_,L).

Since any of the variables can be []s, this clause is certainly true.
And it seems to cover all possibilities.

However, I believe that it is the cause of your stack overflows. When
append(P,_,L) fails, it will backtrack into append(_,S,P), which can
always succeed by increasing the length of the anonymous list by one.
Since P gets longer than L (given that the size of L is determined
before calling sublist(S,L)), append(P,_,L) keeps failing and
append(_,S,P) keeps succeeding. That gives you a kind of infinite loop.

Here is an alternative predicate that does not have that problem.

sublist(Sublist,List) :-
    append(Midlist,_,List),
    append(_,Sublist,Midlist).

All we did was switch the goals, so that the information about List gets
used first. Remember that if List is uninstantiated, there will be an
infinity of solutions to sublist/2. That's generally not what you want.
With this ordering, you fail early, which is usually what you want.

> langford_sublists(0,_,_).
>
> %recursively generate all sublists
> langford_sublists(N,K,L) :-
> N>0,
> % every list consists on K copies of N + K-1 copies of N variables
> Size is K+(K-1)*N,
> generate_list(N,Size,List,L),
> NN is N-1,
> langford_sublists(NN,K,L).

List in generate_list(N,Size,List,L) occurs only once in this clause.
That means that you neither extract nor provide information using it.
Sometimes that's what you want, but often it indicates a problem. In
fact, the corresponding variable does not appear in the first clause,
either, and that is definitely problematic.

> generate_list(_,0,L1,L2) :-
> sublist(L1,L2).
>
> % responsible for placing the Ns in the sublist
> generate_list(N,I,List,L) :-
> I>0,
> II is I-1,
> NNN is N+1,
> III is II mod NNN,
> III is 0,
> generate_list(N,II,[N|List],L).
>
> % responsible for placing the variables in the sublist
> generate_list(N,I,List,L) :-
> I>0,
> II is I-1,
> generate_list(N,II,[_|List],L).

I like your style of commenting, but here you may want to get more
specific about what is going on, particularly as you are learning the
language. I do not really get what the predicate means or does. It often
helps just to write the predicate out clearly in natural language, and
then translate into Prolog.

What Prolog are you using? What debugging facilities does it provide?
You need to learn to use them. :-)

Anyway, with the new sublist/2 predicate, the query, langford(4,2,List),
does not blow the stack. Instead, it returns this answer:

> List = [4, 2, 3, 1, 2, 4, 3, _G239]

_G239 is an anonymous variable generated by Prolog. Plainly this is
wrong. There is no substitution for the anonymous variable that will
produce a Langford list. The problem probably lies in generate_list/4.

Best,

Bill

P. S. After a query has produced an answer, to get another one, if
Prolog can find it, enter a semicolon.

Relevant Pages

  • Re: Make deterministic without using cut?
    ... Overall, I think using cut in this predicate is fine, it simply ... expresses when a predicate commits to the clause. ... But as I personally dont like to have to call strtok/3 from other clauses ... O'Keefe s book "The Craft of Prolog" it is excellent on this respect. ...
    (comp.lang.prolog)
  • Re: Circular definition
    ... there some way I can get prolog to detect that move_suceedsdepends on itself, and throw some sort of exception to resolve the situation another way? ... whenever you define a predicate with just one clause, ... variants of Prolog do; find XSB Prolog ...
    (comp.lang.prolog)
  • Re: Prolog list question
    ... I have created a predicate that takes a list and a character, ... returns the elements beginning with that character: ... Because of the 'write' clause, Prolog just outputs the elements. ...
    (comp.lang.prolog)
  • Prolog list question
    ... I have created a predicate that takes a list and a character, ... returns the elements beginning with that character: ... Because of the 'write' clause, Prolog just outputs the elements. ...
    (comp.lang.prolog)
  • Re: negotiation by failure- list operations
    ... > from other Prolog systems, why it was worth to go through the trouble ... As soon as a clause is typed in it is instantly asserted into ... same full-screen editor window. ... software patents (did you know even tab controls are supposedly ...
    (comp.lang.prolog)
Loading