0

I am implementing a words/2 predicate in which a list of characters can be rendered to a list of the character as a word inside a list. I use the mathematical symbol <=> to denote that they're working in any mode. Please advise if there's a better expression.

The example:

?- words([p,r,o,l,o,g,' ',i,s,' ',g,o,o,d],Y).
Y = [[p,r,o,l,o,g],[i,s],[g,o,o,d]]

?- words(X,[[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]

What I've done is trying to use append/3 as below, trying to put the empty string in between, and concatenate them together. And recurse the List with NewCharList, but failed with "out of local stack".

% base case, empty list
words([],[]).
% X is a list of characters
% Y is a list with characters list as a word
words(CharList,[WordList|List]):-
    append(WordList,[' '],NewWord),
    append(NewWord,CharList,NewCharList),
    words(NewCharList,List).

How could I improve the code? Thanks.

Edit1 Million thanks from @rajashekar. Now I understand the code

% base case
split(_, [], [[]]).

% when the the element list of Ys is empty
% add a C to the Xs, in this case, C is a empty string ' '
split(C, [C|Xs], [[]|Ys]) :-
    split(C, Xs, Ys).

% put the X character from [X|Y] list to Xs
% and goes on next word list
split(C, [X|Xs], [[X|Y]|Ys]) :-
    split(C, Xs, [Y|Ys]).

but in my SWI-prolog, it seems weird that:

?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p, r, o, l, o, g, ' ', i, s|...]

Here is the trace record:

[trace]  ?- split(X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
   Call: (10) split(_5702, [[p, r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
   Call: (11) split(_6210, [[r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
   Call: (12) split(_6266, [[o, l, o, g], [i, s], [g, o, o, d]]) ? creep
   Call: (13) split(_6322, [[l, o, g], [i, s], [g, o, o, d]]) ? creep
   Call: (14) split(_6378, [[o, g], [i, s], [g, o, o, d]]) ? creep
   Call: (15) split(_6434, [[g], [i, s], [g, o, o, d]]) ? creep
   Call: (16) split(_6490, [[], [i, s], [g, o, o, d]]) ? creep
   Call: (17) split(_6546, [[i, s], [g, o, o, d]]) ? creep
   Call: (18) split(_6596, [[s], [g, o, o, d]]) ? creep
   Call: (19) split(_6652, [[], [g, o, o, d]]) ? creep
   Call: (20) split(_6708, [[g, o, o, d]]) ? creep
   Call: (21) split(_6758, [[o, o, d]]) ? creep
   Call: (22) split(_6814, [[o, d]]) ? creep
   Call: (23) split(_6870, [[d]]) ? creep
   Call: (24) split(_6926, [[]]) ? creep
   Exit: (24) split([], [[]]) ? creep
   Exit: (23) split([d], [[d]]) ? creep
   Exit: (22) split([o, d], [[o, d]]) ? creep
   Exit: (21) split([o, o, d], [[o, o, d]]) ? creep
   Exit: (20) split([g, o, o, d], [[g, o, o, d]]) ? creep
   Exit: (19) split([' ', g, o, o, d], [[], [g, o, o, d]]) ? creep
   Exit: (18) split([s, ' ', g, o, o, d], [[s], [g, o, o, d]]) ? creep
   Exit: (17) split([i, s, ' ', g, o, o, d], [[i, s], [g, o, o, d]]) ? creep
   Exit: (16) split([' ', i, s, ' ', g, o, o, d], [[], [i, s], [g, o, o, d]]) ? creep
   Exit: (15) split([g, ' ', i, s, ' ', g, o, o|...], [[g], [i, s], [g, o, o, d]]) ? creep
   Exit: (14) split([o, g, ' ', i, s, ' ', g, o|...], [[o, g], [i, s], [g, o, o, d]]) ? creep
   Exit: (13) split([l, o, g, ' ', i, s, ' ', g|...], [[l, o, g], [i, s], [g, o, o, d]]) ? creep
   Exit: (12) split([o, l, o, g, ' ', i, s, ' '|...], [[o, l, o, g], [i, s], [g, o, o, d]]) ? creep
   Exit: (11) split([r, o, l, o, g, ' ', i, s|...], [[r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
   Exit: (10) split([p, r, o, l, o, g, ' ', i|...], [[p, r, o, l, o, g], [i, s], [g, o, o, d]]) ? creep
X = [p, r, o, l, o, g, ' ', i, s|...] .

EDIT2 I found out that using ! (cut) could cut down the backtracking.

% base case
split(_, [], [[]]).

% when the the element list of Ys is empty
% add a C to the Xs, in this case, C is a empty string ' '
split(C, [C|Xs], [[]|Ys]) :-
    split(C, Xs, Ys),!.

% put the X character from [X|Y] list to Xs
% and goes on next word list
split(C, [X|Xs], [[X|Y]|Ys]) :-
    split(C, Xs, [Y|Ys]),!.
Woden
  • 1,054
  • 2
  • 13
  • 26
  • 2
    Use [tag:dcg]-notation! – false Jun 07 '21 at 13:59
  • @false Thank you for the suggestion. I've found an example of DCG such as `sentence(s(S,V,O)) --> subject(S), verb(V), object(O).` from https://www.amzi.com/manuals/amzi/pro/ref_dcg.htm . How could I express the mode that mathematically in this example that subject, verb, and object can also form a sentence, in which the relation is bidirectional? – Woden Jun 07 '21 at 15:42
  • 1
    [Consider this](https://stackoverflow.com/a/10401614/772868). – false Jun 07 '21 at 15:44
  • 1
    Press `w` key to make SWI show the complete answer – gusbro Jun 07 '21 at 20:51
  • @gusbro Thanks! It works. But since there's a testing case for the implementation, I can only write the predicate. – Woden Jun 08 '21 at 03:44

2 Answers2

1

The code does exactly what you want. Here:

?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).
X = [p, r, o, l, o, g, ' ', i, s|...]

X is exactly the expected output.

If you want to see all of X, do:

?-split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]), write_canonical(X).
[p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]
X = [p, r, o, l, o, g, ' ', i, s|...]

Long lists are shortened on the output in SWI prolog.

Marco
  • 50
  • 5
  • Thanks for another solution, but since there's a testing case, what I can do is only writing the predicate. – Woden Jun 08 '21 at 03:40
  • 1
    The abbreviation of `X = [p, r, o, l, o, g, ' ', i, s|...]` is only visual. Internally SWI knows that X is unified with `[p,r,o,l,o,g,' ',i,s,' ',g,o,o,d]` – Marco Jun 08 '21 at 11:44
0
split(_, [], [[]]).
split(C, [C|Xs], [[]|Ys]) :-
    split(C, Xs, Ys).
split(C, [X|Xs], [[X|Y]|Ys]) :-
    split(C, Xs, [Y|Ys]).

| ?- split(' ', [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d], X).

X = [[p,r,o,l,o,g],[i,s],[g,o,o,d]] ? 

yes
| ?- split(' ', X, [[p,r,o,l,o,g],[i,s],[g,o,o,d]]).

X = [p,r,o,l,o,g,' ',i,s,' ',g,o,o,d] ? 

yes
  • you can use mode declaration to say the predicate works in both modes. e.g., you could have said the words/2 predicate needs to work in both words(+Chars, -Words) and words(-Chars, +Words) modes(or in words(+, -) and words(-, +) modes). See for mode details. These are mostly used for documentation purposes in prolog (check out mercury where they really work).
  • Using Definite Clause Grammers DCGs will make problems like this a whole lot easier.
  • Try using trace when you feel a run away recursion. You can spot the problem most of the time if you use it.
rajashekar
  • 3,460
  • 11
  • 27
  • Thanks for the answer and other suggestions, but as you can see, the requirement is using only two arguments. – Woden Jun 07 '21 at 15:35
  • And, regarding mode, in the question that both arguments could be generated, so based on the manual, it should be `words(?,?)`? Thanks. – Woden Jun 07 '21 at 15:47
  • 1
    I used `C` as an extra argument for a more general solution. You can remove it and just replace `C` with `' '` in the body of the clauses. Or just say `words(X, Y) :- split(' ', X, Y).`. A predicate can have more than one mode, you can just document the ones you need and can guarantee the correctness. For e.g., you can say `length` works in `length(+, +)`, `length(+, -)`, `length(?, +)` and `length(?, -)` modes, but it is generally documented as just `length(?, ?)`. – rajashekar Jun 07 '21 at 15:52
  • Thanks for the comprehensive explanation. – Woden Jun 07 '21 at 15:56
  • I did a test, but it seems not working. Could you please have a look? I've edited the post. Thanks, again. – Woden Jun 07 '21 at 19:11
  • 1
    @Woden: `SWI-Prolog` is eliding your solution. When the lists get too big `swipl` doesn't print all of the list by default. You can do `write(X)` to explicitly print it or press `w` at a choice point or in trace to change the default setting. – rajashekar Jun 08 '21 at 04:47