More compact definition

Question

Given word/1,

word(W) :-
   abs(ABs),
   ABs = W.

abs([]).
abs([AB|ABs]) :-
   abs(ABs),
   ab(AB).

ab(a).
ab(b).

?- word(W).
   W = []
;  W = [a]
;  W = [b]
;  W = [a,a]
;  W = [b,a]
;  W = [a,b]
;  W = [b,b]
;  W = [a,a,a]
;  W = [b,a,a]
;  W = [a,b,a]
;  W = [b,b,a]
;  W = [a,a,b]
;  W = [b,a,b]
;  W = [a,b,b]
;  W = [b,b,b]
;  W = [a,a,a,a]
;  ... .

how does a more compact definition of word/1 look like, otherwise identical w.r.t. termination and the set of solutions, fairness, with the following constraints:

No use of built-ins like (=)/2.
No use of control constructs like (',')/2 or (;)/2, or call/1.
Uses one fact, one recursive rule, and one rule for word/1.

Maybe simpler is to ask for the terms F1 ... F4 in:

word(W) :-
   p(F1).

p(F2).
p(F3) :-
   p(F4).

For the record: The property exploited here is closely related to the undecidability of termination of a single binary clause. Praise goes to:

Philippe Devienne, Patrick Lebègue, Jean-Christophe Routier, and Jörg Würtz. One binary horn clause is enough STACS '94.

but why would you want to convert a predicate that terminates (with a *semantically* correct solution) into one that does not terminate? At KU Leuven (my *Alma mater*) some people did research on *termination proofs in Prolog* so it looks like a good thing. — Willem Van Onsem, Feb 14 '17 at 18:06
@WillemVanOnsem: The problem is: Given that very definition, ... — false, Feb 14 '17 at 18:07
@WillemVanOnsem: Your comment goes into a completely different direction. — false, Feb 14 '17 at 18:08
Is using a meta-interpreter also excluded? Not that I have an answer, but want to avoid going down a path that is excluded. — Guy Coder, Feb 14 '17 at 18:49
@GuyCoder: It depends on what you mean by a meta-interpreter. Classical meta-interpreters use `clause/2` and conjunction. Both is excluded. — false, Feb 14 '17 at 18:51
So a meta-interpreter that avoids the restrictions is allowed? Meaning one can create a more elaborate MI to get past the `one fact` and `one recursive rule` constraints. — Guy Coder, Feb 14 '17 at 19:02
@GuyCoder: I cannot see how you can circumvent the restrictions. Note: conjunction is not allowed! — false, Feb 14 '17 at 19:06
Do the answers have to appear in the same order? In other words if I just use `0` and successor, then translate that into binary and then translate `0` to `a` and `1` to `b` is that allowed? — Guy Coder, Feb 14 '17 at 19:08
I expect the very same answers, not necessarily in exactly the same order, but at least the enumeration should be fair. Thus each solution will eventually be produced. — false, Feb 14 '17 at 19:10
Not sure why you are thinking of `0` and `1`. In any case, arithmetics is excluded, since no built-ins are permitted. — false, Feb 14 '17 at 19:15
@GuyCoder: The `ABs = W` just prevents that `word/1` has better termination properties. In fact, `word/1` terminates never. It finds solution, but ever terminates. Even for `word(non_word)` it just loops — false, Feb 14 '17 at 19:53
@GuyCoder: Exactly! The rule for `word/1` can only contain a single goal. Conjunction is not permitted (that's much too advanced :-) ). — false, Feb 14 '17 at 19:56
This feels moke like a programming challenge (for e.g. [PPCG](http://codegolf.stackexchange.com/)) than a genuine programming question for SO. However I guess SO is the only place where there are sufficiently many Prolog programmers to be interested in this. — Fatalize, Feb 16 '17 at 09:06
Are there any restrictions on `abs`? if not then you simply move the `=` into `abs`, which is obviously pretty stupid... — Fatalize, Feb 16 '17 at 13:53
`abs`? Do you mean the arguments of the predicates? There are no restrictions. Not sure what you perceive as obviously stupid. — false, Feb 16 '17 at 14:09
Would this SWI-Prolog snippet be acceptable? `length(W,_), maplist([X]>>(X=a;X=b),W).` — gniourf_gniourf, Feb 16 '17 at 18:16
@gniourf_gniourf: Usage of two built-ins `length/2`, and `maplist/2` usage of control constructs like conjunction and disjunction. And then these untypeable lambdas... — false, Feb 16 '17 at 18:30
I think I am close. It could be a win or lose by a nose. I definitely think sleeping on it was part of the way, but as you noted you also have to work with it; basically get the cobwebs out of the brain and then you have less paths and false paths to check. Luckily no one can sleep on it any more. Should I post where I am at an hour before the dead line if I don't have it so that others might see what I have overlooked? — Guy Coder, Feb 23 '17 at 13:47

mat · Accepted Answer · 2017-02-23T16:14:56.227

11

The solution I have come up with is:

word(W) :-
        p([[]|Ls], Ls, W).

p([W|_], _, W).
p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-
        p(Ws, Ls, W).

Sample query and answer:

?- word(W).
W = [] ;
W = [a] ;
W = [b] ;
W = [a, a] ;
W = [b, a] ;
W = [a, b] ;
W = [b, b] ;
W = [a, a, a] ;
W = [b, a, a] ;
W = [a, b, a] ;
W = [b, b, a] ;
W = [a, a, b] ;
W = [b, a, b] ;
W = [a, b, b] ;
W = [b, b, b] ;
W = [a, a, a, a] ;
W = [b, a, a, a] ;
etc.

I am using a difference list to incrementally materialize the solutions I want the toplevel to report.

edited Feb 23 '17 at 16:14

answered Feb 23 '17 at 16:10

mat

40,498
3
51
78

1

I have clarified that this is a solution. Note that it should not be only correct, but also as elegant as possible, and so you may find for example better variable names. – mat Feb 23 '17 at 16:16
Clearly you win. Nice job. Again thanks for posting what I was headed towards. I don't think I would have figured out `[[]|Ls]` in time. I was stuck on `[[]]`. I knew to use `p(..., W).` but didn't know exactly how. – Guy Coder Feb 23 '17 at 16:27
Somewhat I prefer `p([W|_], provisional_end, W).` to better clarify the role of this argument. – false Feb 23 '17 at 17:19
@false you meant `Provisional_end`, I think. I prefer to call it `Production_point` when dealing (mentally) with the lazy queues (as this one is -- very nice!). `p` is a curious character - a cross between, or a sum of two predicates, `member( [E|T], _, E).` ; `member( [_|T], _, E):- member( T, _, E).` and `gen( [E|T], [[a|E], [b|E] | R], _) :- gen( T, R, _).` , thus reading and writing at it at the same time at 2 diffrt pts! Cudos to user:mat for the solution!! btw, 4 comparison, in Haskell it's `abs = [] : gen abs (drop 1 abs) where gen (x:t) p = (0:x):(1:x):gen t (drop 2 p)`. – Will Ness Feb 23 '17 at 18:07
all of the above is clear *in retrospect*, of course. :) the `p` in Haskell isn't used but it does track the production point, which is maintained implicitly by Haskell; Prolog of course needs it explicit. /captain Hindsight signing off. – Will Ness Feb 23 '17 at 18:27
@Will: I really meant a constant that does not occur anywhere else in the program that makes clear how solutions to the goal `p([[]|Ls], Ls, W).` such that anyone can see where the things "end" - so to speak - regardless of any typechecker, indeed. – false Feb 23 '17 at 19:12
@false that would break it though, isn't it? – Will Ness Feb 23 '17 at 19:13
@Will: Is there some working knowledge in Haskell of the minimal Turing complete program? That is, what constructs it has to use, say primitive recursion or more &ct. See [my comment](http://cs.stackexchange.com/questions/19591/what-makes-prolog-turing-complete/19593#comment150392_19593) somewhere else. – false Feb 23 '17 at 19:15
@false sorry, don't know. guys in #haskell irc channel might know more. – Will Ness Feb 23 '17 at 19:24
@Will: If you are completely unhappy, use `[]` in stead which still more concise than the allmighty `_` – false Feb 23 '17 at 19:38
@Will: rest, that sound so operationalizing. Who is resting? – false Feb 23 '17 at 19:52

score 7 · Answer 2 · answered Feb 17 '17 at 09:33

Okay so not an answer yet.

The closest I had was :

s_s1([],[a]).
s_s1([b|T],[a|T]).
s_s1([a|T],[b|T2]):-
 s_s1(T,T2).

word([]).
word(W2):-
 word(W),
 s_s1(W,W2).

Which does not either meet the criteria or give the right solutions!

So next I thought we could try and use prolog to find the answer.. The structure is given so we need to search for the args..

%First define the first 16 correct solutions.. 
correct_sols(X):-
X=[
     [],
     [a],
     [b],
     [a,a],
     [b,a],
     [a,b],
     [b,b],
     [a,a,a],
     [b,a,a],
     [a,b,a],
     [b,b,a],
     [a,a,b],
     [b,a,b],
     [a,b,b],
     [b,b,b],
     [a,a,a,a]
].

%Then a mi
provable(true, _) :- !.
provable((G1,G2), Defs) :- !,
    provable(G1, Defs),
    provable(G2, Defs).
provable(BI, _) :-
    predicate_property(BI, built_in),
    !,
    call(BI).
provable(Goal, Defs) :-
    member(Def, Defs),
    copy_term(Def, Goal-Body),
    provable(Body, Defs).

%From 4 Vars find 16 solutions to word(X)
vars_16sols(Vars,List):-
    Vars =[Args,Args0,Args1,Argsx],
    findnsols(16,X,provable(word(X),[
                            a(Args)-true,
                            a(Args0)-a(Args1),
                            word(X)-a(Argsx)]
                       ),List).
%Evaluate the score, for the solutions found how many match correct
evaluate_score(Solutions,Score):-
   correct_sols(C),
   maplist(correct_test_tf,C,Solutions,TrueFalse),
   findall(_,member(true,TrueFalse),Matches),
   length(Matches,Score).

%The main search, give a form for the starting 4 arguments, if they 
match all 16 correct stop.
startingargs_solution(Start,Sol):-
   vars_16sols(Start,SolsStart),
   evaluate_score(SolsStart,Score),
   Score =16,
   SolsStart=Sol.
%Othewise refine args, and try again.
startingargs_solution(Start,Sol):-
   vars_16sols(Start,SolsStart),
   evaluate_score(SolsStart,Score),
   Score <16,
   start_refined(Start,Refined),
   startingargs_solution(Refined,Sol).

We would still need to define :

correct_test_tf/3
start_refined/2 with some constraints, such as the size of the terms for args(needs to be reasonable to be a 'compact definition', and what things need to be included, i.e. at least a and b somewhere and probably [].

Clearly not finished and not sure if it will be possible to do this but thought I would post an answer to see what people have to say.. The search is naive at the moment!

This is only testing the first 16 solutions but maybe that is adequate to get a correct answer..

Also maybe this is harder then solving the question on its own!

Very interesting and worthwhile approach! It may be harder, but it is more general and flexible. I will give a separate 500 bounty for this answer if you manage to find a solution in this way. `call_with_inference_limit/3` may be useful for this. — mat, Feb 17 '17 at 10:22

score 5 · Answer 3 · edited May 23 '17 at 12:02

My closest yet.

unfold20([], []).
unfold20([H|T], [[a|H], [b|H]|L]) :-
   unfold20(T, L).

member20(X, [X|_]).
member20(X, [_|Tail]) :-
  member20(X, Tail).

swap20(R,R) :-
    write('swap20 R: '),write(R),nl.

swap20(In,L) :-
    write('swap20 In: '),write(In),nl,
    unfold20(In,L),
    swap20(L,_),
    write('swap20 L: '),write(L),nl.

word20(W) :-
    swap20([[]],L),
    write('word20 L: '),write(L),nl,
    member20(W,L),
    write('word20 W: '),write(W),nl.

?- word20(X).
swap20 R: [[]]
word20 L: [[]]
word20 W: []
X = [] ;
swap20 In: [[]]
swap20 R: [[a],[b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a] ;
word20 W: [b]
X = [b] ;
swap20 In: [[a],[b]]
swap20 R: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a] ;
word20 W: [b]
X = [b] ;
swap20 In: [[a,a],[b,a],[a,b],[b,b]]
swap20 R: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a] ;
word20 W: [b]
X = [b] ;
swap20 In: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 R: [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],[b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]]
swap20 L: [[a,a,a,a],[b,a,a,a],[a,b,a,a],[b,b,a,a],[a,a,b,a],[b,a,b,a],[a,b,b,a],[b,b,b,a],[a,a,a,b],[b,a,a,b],[a,b,a,b],[b,b,a,b],[a,a,b,b],[b,a,b,b],[a,b,b,b],[b,b,b,b]]
swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]
word20 L: [[a],[b]]
word20 W: [a]
X = [a]

If you look you will see that there is no use of ; which I am sure is a problem some people are having. Also all of the rules are simple enough that they should be able to be folded into the requirements by using additional arguments. e.g. unfold(A,B) would become unfold(A,B,C,D) or a variation.

The problem with this version is that I get the correct answers as the evaluation progresses, it is just getting them back to the top level.

e.g.

swap20 L: [[a,a,a],[b,a,a],[a,b,a],[b,b,a],[a,a,b],[b,a,b],[a,b,b],[b,b,b]]
swap20 L: [[a,a],[b,a],[a,b],[b,b]]
swap20 L: [[a],[b]]

I will keep working on this before the dead line, but if someone is able to use what I have here, hats off to them, I just ask that you give credit if any part of this helped you get the answer.

The unfold predicate is based on this SO answer. Credit to salva

member is an old friend. Notice that it starts with [[]] and not [].

swap I created this predicate. I have swap working for different variation yet the variation fails for a different reason.

Supplement

Debugger output of mat's answer

I looked at Mat's answer more closely with a debugger because it might hold the answer to a similar problem where I can generate the answers but not return them independently to Top.

Mat's answer copied here for reference.

p([W|_], _, W).

p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-
    p(Ws, Ls, W).

word(W) :-
    p([[]|Ls], Ls, W).

The part of interest is far to the right as comments. I would suggest that you copy from here and past into a app that allows you to see all of the line without wrapping or hidden.

The column on the left was created with SWI-Prolog running the query with trace and the comments on the right were created by running the query with gtrace and hand copying the values and noting the level for indentation.

?- word(W).
   Call: (8) word(_822) ? creep                                                                                                                                      % word(W) :-
   Call: (9) p([[]|_1010], _1010, _822) ? creep                                                                                                                      %   p([[]|Ls], Ls, W).
   Exit: (9) p([[]|_1010], _1010, []) ? creep                                                                                                                        %   p([W|_], _, W).                             % W = []
   Exit: (8) word([]) ? creep                                                                                                                                        % p([[]|Ls], Ls, W).                            % W = []
W = [] ;                                                                                                                                                                                                                       
   Redo: (9) p([[]|_1010], _1010, _822) ? creep                                                                                                                      %   p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-        %              W0 = []    Ws = [[a],[b]|Ls]
   Call: (10) p([[a], [b]|_1028], _1028, _822) ? creep                                                                                                               %     p(Ws, Ls, W).                             %              W0 = []    Ws = [[a],[b]|Ls]
   Exit: (10) p([[a], [b]|_1028], _1028, [a]) ? creep                                                                                                                %     p([W|_], _, W).                           % W = [a]    
   Exit: (9) p([[], [a], [b]|_1028], [[a], [b]|_1028], [a]) ? creep                                                                                                  %   p(Ws, Ls, W).                               % W = [a]      W0 = []    Ws = [[a],[b]|Ls]
   Exit: (8) word([a]) ? creep                                                                                                                                       % p([[]|Ls], Ls, W).                            % W = [a]                                                                               Ls = [[a],[b]|_2312]
W = [a] ;                                                                                                                                                                                                                                                                                             
   Redo: (10) p([[a], [b]|_1028], _1028, _822) ? creep                                                                                                               %     p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-      %              W0 = [a]   Ws = [    [b],[a,a],[b,a]|Ls]                          
   Call: (11) p([[b], [a, a], [b, a]|_1052], _1052, _822) ? creep                                                                                                    %       p(Ws, Ls, W).                           %              W0 = [a]   Ws = [    [b],[a,a],[b,a]|Ls]                          
   Exit: (11) p([[b], [a, a], [b, a]|_1052], _1052, [b]) ? creep                                                                                                     %       p([W|_], _, W).                         % W = [b]                                                                    
   Exit: (10) p([[a], [b], [a, a], [b, a]|_1052], [[a, a], [b, a]|_1052], [b]) ? creep                                                                               %     p(Ws, Ls, W).                             % W = [b]      W0 = [a]   Ws = [    [b],[a,a],[b,a]|Ls]                         
   Exit: (9) p([[], [a], [b], [a, a], [b, a]|_1052], [[a], [b], [a, a], [b, a]|_1052], [b]) ? creep                                                                  %   p(Ws, Ls, W).                               % W = [b]      W0 = []    Ws = [[a],[b],[a,a],[b,a]|_2324]                              Ls = [        [a,a],[b,a]|_2324] 
   Exit: (8) word([b]) ? creep                                                                                                                                       % p([[]|Ls], Ls, W).                            % W = [b]                                                                               Ls = [[a],[b],[a,a],[b,a]|_2324]                            
W = [b] .                                                                                                                                                                                                                                                                                            
   Redo: (11) p([[b], [a, a], [b, a]|_1052], _1052, _822) ? creep                                                                                                    %       p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-    %              W0 = [b]   Ws = [        [a,a],[b,a],[a,b],[b,b]|Ls]                  
   Call: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, _822) ? creep                                                                                         %         p(Ws, Ls, W).                         %              W0 = [b]   Ws = [        [a,a],[b,a],[a,b],[b,b]|Ls]                  
   Exit: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, [a, a]) ? creep                                                                                       %         p([W|_], _, W).                       % W = [a,a]                                                                   
   Exit: (11) p([[b], [a, a], [b, a], [a, b], [b, b]|_1076], [[a, b], [b, b]|_1076], [a, a]) ? creep                                                                 %       p(Ws, Ls, W).                           % W = [a,a]    W0 = [b]   Ws = [        [a,a],[b,a],[a,b],[b,b]|Ls]                  
   Exit: (10) p([[a], [b], [a, a], [b, a], [a, b], [b, b]|_1076], [[a, a], [b, a], [a, b], [b, b]|_1076], [a, a]) ? creep                                            %     p(Ws, Ls, W).                             % W = [a,a]    W0 = [a]   Ws = [    [b],[a,a],[b,a],[a,b],[b,b]|_2348]                  Ls = [                    [a,b],[b,b]|_2348]
   Exit: (9) p([[], [a], [b], [a, a], [b, a], [a, b], [b|...]|_1076], [[a], [b], [a, a], [b, a], [a, b], [b, b]|_1076], [a, a]) ? creep                              %   p(Ws, Ls, W).                               % W = [a,a]    W0 = []    Ws = [[a],[b],[a,a],[b,a],[a,b],[b,b]|_2348]                  Ls = [        [a,a],[b,a],[a,b],[b,b]|_2348] 
   Exit: (8) word([a, a]) ? creep                                                                                                                                    % p([[]|Ls], Ls, W).                            % W = [a,a]                                                                             Ls = [[a],[b],[a,a],[b,a],[a,b],[b,b]|_2348]
W = [a, a] ;                                                                                                                                                               
   Redo: (12) p([[a, a], [b, a], [a, b], [b, b]|_1076], _1076, _822) ? creep                                                                                                                         
   Call: (13) p([[b, a], [a, b], [b, b], [a, a, a], [b, a, a]|_1100], _1100, _822) ? creep                                                                           %         p([W0|Ws], [[a|W0],[b|W0]|Ls], W) :-  %              W0 = [a,a] Ws = [              [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls]                                              
   Exit: (13) p([[b, a], [a, b], [b, b], [a, a, a], [b, a, a]|_1100], _1100, [b, a]) ? creep                                                                         %           p(Ws, Ls, W).                       %              W0 = [a,a] Ws = [              [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls]                                                  
   Exit: (12) p([[a, a], [b, a], [a, b], [b, b], [a, a, a], [b, a|...]|_1100], [[a, a, a], [b, a, a]|_1100], [b, a]) ? creep                                         %           p([W|_], _, W).                     % W = [b,a]                                                                                                                                    
   Exit: (11) p([[b], [a, a], [b, a], [a, b], [b, b], [a, a|...], [b|...]|_1100], [[a, b], [b, b], [a, a, a], [b, a, a]|_1100], [b, a]) ? creep                      %         p(Ws, Ls, W).                         % W = [b,a]    W0 = [a,a] Ws = [              [b,a],[a,b],[b,b],[a,a,a],[b,a,a]|Ls]                                                                                                                                
   Exit: (10) p([[a], [b], [a, a], [b, a], [a, b], [b, b], [a|...], [...|...]|...], [[a, a], [b, a], [a, b], [b, b], [a, a, a], [b, a|...]|_1100], [b, a]) ? creep   %       p(Ws, Ls, W).                           % W = [b,a]    W0 = [b]   Ws = [        [a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]  Ls = [                                [a,a,a],[b,a,a]|_2372]                                                                                                                                                         
   Exit: (9) p([[], [a], [b], [a, a], [b, a], [a, b], [b|...], [...|...]|...], [[a], [b], [a, a], [b, a], [a, b], [b, b], [a|...], [...|...]|...], [b, a]) ? creep   %     p(Ws, Ls, W).                             % W = [b,a]    W0 = [a]   Ws = [    [b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]  Ls = [                    [a,b],[b,b],[a,a,a],[b,a,a]|_2372]                                                                                                                                                           
   Exit: (8) word([b, a]) ? creep                                                                                                                                    %   p(Ws, Ls, W).                               % W = [b,a]    W0 = []    Ws = [[a],[b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]  Ls = [        [a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]     
W = [b, a] ;                                                                                                                                                         % p([[]|Ls], Ls, W).                            % W = [b,a]                                                                             Ls = [[a],[b],[a,a],[b,a],[a,b],[b,b],[a,a,a],[b,a,a]|_2372]

You may be able to use an additional argument to make the toplevel report the answer via a *binding*! — mat, Feb 23 '17 at 15:22
@mat I get what you are saying, but between idea and implementation I still have a difficulty. Still working on it. Thanks. — Guy Coder, Feb 23 '17 at 15:24
I really like the `unfold20`!!! But think of it: It will also have to give one element "back". — false, Feb 23 '17 at 15:49
@false I do too, that is why I used it but gladly give credit to salva. — Guy Coder, Feb 23 '17 at 15:50
(Just a general remark: There is really notreason to use write/1. The toplevel writes much better!) — false, Feb 23 '17 at 15:52
Just post your queries in such a matter that the toplevel produces the answers for you - no need for write (and **if**, then rather use `writeq/1`). — false, Feb 23 '17 at 16:05
@GuyCoder you were pretty close! swap args in your `member20`; erase first clause of `unfold20`; then see that the two predicates share the first argument! so, `member20flipped(A,B,_) +++ unfold20(A,_,C)` ===> `p(A,B,C)` ! (in hindsight, everything is easy; I was bogged down with trying to make *trees* work here somehow... dead end) :) — Will Ness, Feb 23 '17 at 18:34

Guy Coder · Answer 4 · 2017-10-26T11:24:38.870

Normally I would post these as a single answer, but @false asked me to keep them separate.

If you read my comments and answers you will see that I was aware that I had to pass the result from one iteration back into the next iteration. What gave me insight into that was using a cross-product predicate which I found in

"The Craft of Prolog" by Richard A. O'Keefe pg. 243

If you are serious about learning Prolog, the book is a must have.

To quote the Preface

There are a lot of introductory Prolog books around. This is not one of them. Think of it as "second steps in Prolog". If you have already read one of the introductory books, if you have taken an introductory course on Prolog, if you have written ore or two Prolog programs, and if you are wondering why it is still hard to write good Prolog programs, this book is meant to help you. The purpose of the book is to show you how you can write Prolog programs that work, that don't take an unreasonable amount of time, and that are clean enough to show to your friends.

Here is a slight variation that I used for one variation that did not work.

combine(X,Y,[X,Y]).

product(P,Xs,Ys,PXYs) :-
    product1(Xs,Ys,PXYs,P).

product1([],_,[],_).

product1([X|Xs],Ys,PXYs0,P) :-
    product1(Ys,X,P,PXYs0,PXYs1),
    product1(Xs,Ys,PXYs1,P).

product1([],_,_) --> [].

product1([Y|Ys],X,P) -->
    {
        call(P,X,Y,PXY)
    },
    [PXY],
    product1(Ys,X,P).

?- product(combine,[a,b],[a,b],R).
R = [[a, a], [a, b], [b, a], [b, b]].

score 4 · Answer 5 · answered Feb 16 '17 at 16:45

4

So to clarify, the intended solution is an instance of the following schema?

fact(Args).

recursive_rule(Args0) :-
    recursive_rule(Args1).

word(W) :-
    recursive_rule(Args).

Where each occurrence of an Args variable stands for zero or more terms and presumably (but not necessarily) fact and recursive_rule are actually the same functor?

answered Feb 16 '17 at 16:45

Isabelle Newbie

9,258
1
20
32

Yes. Only when fact and recursive_rule are of the same predicate you have a chance to get what we want. The number of arguments is irrelevant since you can always represent arguments in a single argument with a corresponding function symbol. – false Feb 16 '17 at 16:48

score 3 · Answer 6 · answered Feb 23 '17 at 15:50

3

With Guy coder's suggestions this is closer?

unfold([], []).
unfold([H|T], [[a|H], [b|H]|L]) :-
 unfold(T, L).

ab([], [[]]).   
ab([_|N1],L):-
 ab(N1, L1),
 unfold(L1, L).

word(X):-
 length(List,_),
 ab(List,Values),
 member(X,Values).

answered Feb 23 '17 at 15:50

user27815

4,767
14
28

Guy Coder · Answer 7 · 2017-03-30T21:02:25.677

3

Not a solution, but an insight toward a solution.

This started with using DCG

abs4 --> [].
abs4 --> abs4, ([a] | [b]).

?- phrase(abs4,X).
X = [] ;
X = [a] ;
X = [b] ;
X = [a, a] ;
X = [a, b] ;
X = [b, a] ;
X = [b, b] ;
X = [a, a, a] ;
X = [a, a, b] ;
X = [a, b, a] ;
X = [a, b, b] ;
X = [b, a, a] ;
X = [b, a, b] ;
X = [b, b, a] ;
X = [b, b, b] ;
X = [a, a, a, a] ;
X = [a, a, a, b] ;

then looking at the listing

?- listing(abs4).
abs4(A, A).
abs4(A, C) :-
        abs4(A, B),
        (   B=[a|C]
        ;   B=[b|C]
        ).

and using member to remove the ;.

word5(W) :-
    abs5(W,[]).
abs5(A, A).
abs5(A, C) :-
    abs5(A, [D|C]),
    member5(D,[a,b]).
member5(X, [X|_]).
member5(X, [_|Tail]) :-
  member5(X, Tail).

?- word5(X).
X = [] ;
X = [a] ;
X = [b] ;
X = [a, a] ;
X = [a, b] ;
X = [b, a] ;
X = [b, b] ;
X = [a, a, a] ;
X = [a, a, b] ;
X = [a, b, a] ;
X = [a, b, b] ;
X = [b, a, a]

edited Mar 30 '17 at 21:02

answered Feb 23 '17 at 16:52

Guy Coder

24,501
8
71
136

too disjunctive, the original `unfold20` shows you that such local disjunction is not needed – false Feb 23 '17 at 16:54
@false Thanks. I know that now, but this was variation `4` and `5`, I didn't discover the power of `unfold` for this question until later. I did find `unfold` in my initial research for parts that could be used, but until I started working with it, as you like to suggest, did I see that it was on the path to the correct solution. Since I have been doing functional programming for years, `F#` I knew how powerful `fold` and `unfold` are, but I just was not as adept as using them with Prolog. Need to work with them more, especially now that I have seen the solution. :) – Guy Coder Feb 23 '17 at 17:30

More compact definition

7 Answers7

Supplement

Debugger output of mat's answer

Linked