Re: Converting Scheme to Prolog

On Sat, 6 Oct 2007, Pierpaolo BERNARDI wrote:
On Sat, 06 Oct 2007 17:58:08 +0200, Daemon <kewldaemon@xxxxxxxxx> wrote:

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]]

use findall.

There is no need to use findall. As ever, the problem here comes
from trying to save information over backtracking, which can't easily
be done in Prolog. But then you don't have to use backtracking for this
problem, just think logically and recursively with lists.

I haven't even tried to code it up, but here's how I start thinking
about it.

We have ncombs(N,L1,L2)

where we want L2 to be all combinations of length N from L1 which
preserve the order of their elements from L1.

Well, thinking recursively, all the combinations must come from two
sublists which can be appended together:

all combinations of length N preserving the order from the tail of L1

all combinations of length N-1 preserving the order from the tail of
L1 with the head of L1 consed to the front of each.

Also we have all combinations of length 0 from any list is [[]] i.e.
there is one combination which fits, the empty list, and we are
returning a list of lists. Plus there are no combinations of length
greater than 0 from the empty list, so in this case return [].

This should translate naturally to a Prolog program.

Matthew Huntbach
.

Relevant Pages

  • Re: N-QUEENS problem with some differences
    ...     M is K-1, ... little different from Prolog. ... If the syntax for lists and "anonymous variables" ... squares and the position of queens as another ...
    (comp.lang.prolog)
  • Re: This Logo program in Prolog?
    ... Term is the basic data structure of Prolog, ... easily use a compound term for building many of the other data ... including lists (lists are just compound terms ... only other language I've seen with such love for the list type is ...
    (comp.lang.prolog)
  • Re: This Logo program in Prolog?
    ... Term is the basic data structure of Prolog, ... easily use a compound term for building many of the other data ... including lists (lists are just compound terms ... only other language I've seen with such love for the list type is ...
    (comp.lang.prolog)
  • Re: Hilbert-Style proof in propositional calculus
    ... The topic lends itself to Prolog. ... about the representation of formulas as Prolog terms and ... We can then implement a Prolog predicate which succeeds ... Now let's briefly discuss representing proofs as lists ...
    (comp.lang.prolog)
  • Re: N-QUEENS problem with some differences
    ... I confirm you that a "queen" who is on a square, ...     M is K-1, ... little different from Prolog. ... If the syntax for lists and "anonymous variables" ...
    (comp.lang.prolog)