Why in SWI Prolog I get the result with `` sign?

List is a data type that has two types of functors / constants:

• an empty list []
  
  that has no arguments; and
• "cons" [element|list]
  
  .

As stated in the second option, the second minus parameter must be a list . It can be still a minus (and hence recursively further) or an empty list. However, Prolog is not actually typed, so you can use an integer, character, ... as the second element, but then it is not a list.

So now the question is, "How do we create such a strange list." In this answer, I used a smaller example to reproduce the bug because it makes things easier:

?- trace.
true.

[trace]  ?- pack([1,1], X).
   Call: (7) pack([1, 1], _G1066) ? creep
   Call: (8) 1\=1 ? creep
   Fail: (8) 1\=1 ? creep
   Redo: (7) pack([1, 1], _G1066) ? creep
   Call: (8) pack([1], [_G1144|_G1141]) ? creep
   Exit: (8) pack([1], [1]) ? creep
   Exit: (7) pack([1, 1], [[1|1]]) ? creep
X = [[1|1]] .

      

        
        
        
      

    

If we pack two items this way, something goes wrong. First we call pack([1,1],X)

.

The third sentence appears first, but the element H \= T

fails. Therefore, as a result, Prolog repeats the call, but now with the last sentence. In the last paragraph, we see something strange:

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).
      

        
        
        
      

    

We see that we are making a recursive call pack/2

with [TFR|TR]

. Thus, it [TFR|TR]

should be a list of lists . But the second clause does not create a list of lists , only a list of items. So the error is:

pack([X], [X]).
%%        ^ list of items??
      

        
        
        
      

    

So, what we need to do to fix the error is to rewrite the second sentence like this:

pack([X], [[X]]).
%%        ^ list of list
      

        
        
        
      

    

Now we have solved this problem, but we still don't see it: there is an error like this in the third section :

pack([H, T|TS], [H|TR]):-
    %%           ^ item instead of a list?
    H \= T,
    pack([T|TS], TR).
      

        
        
        
      

    

Again, we can simply list the items:

pack([H, T|TS], [[H]|TR]):-
    %%           ^ list
    H \= T,
    pack([T|TS], TR).
      

        
        
        
      

    

And now we get the following code:

pack([], []).
pack([X], [[X]]).

pack([H, T|TS], [[H]|TR]):-
    H \= T,
    pack([T|TS], TR).

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).
      

        
        
        
      

    

Then we get:

?- pack([1,1,1,1,2,3,3,1,1,4,5,5,5,5], X).
X = [[1, 1, 1, 1], [2], [3, 3], [1, 1], [4], [5, 5, 5|...]] [write]
X = [[1, 1, 1, 1], [2], [3, 3], [1, 1], [4], [5, 5, 5, 5]] .

      

        
        
        
      

    

EDIT

If there is only one item, you apparently don't want to create a list. This makes the task difficult. There are two options:

• we adapt the code so that if such an element occurs, we do not add it to the list; or
• we do some post-processing where we write off lists with one item.

The latter is pretty trivial, so let's do the first. In this case, the second sentence should indeed be read:

pack([X],[X]).

      

        
        
        
      

    

The second sentence should now read:

pack([H, T|TS], [H|TR]):-
    H \= T,
    pack([T|TS], TR).

      

        
        
        
      

    

... But the last sentence is more complicated:

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).

      

        
        
        
      

    

There are two possibilities here:

• TFR
  
  - a list of elements, in this case we simply add to the list; or
• TFR
  
  is not a list, in which case we are building a list.

To solve this problem, we can define a predicate:

prepend_list(H,[HH|T],[H,HH|T]).
prepend_list(H,X,[H,X]) :-
   X \= [_|_].

      

        
        
        
      

    

and then use:

pack([H, H|HS], [HTFR|TR]):-
    pack([H|HS], [TFR|TR]),
    prepend_list(H,TFR,HTFR).

      

        
        
        
      

    

So now we get:

pack([], []).
pack([X], [X]).

pack([H, T|TS], [H|TR]):-
    H \= T,
    pack([T|TS], TR).

pack([H, H|HS], [HTFR|TR]):-
    pack([H|HS], [TFR|TR]),
    prepend_list(H,TFR,HTFR).

prepend_list(H,[HH|T],[H,HH|T]).
prepend_list(H,X,[H,X]) :-
   X \= [_|_].

      

        
        
        
      

    

Note, however, that this program will crash if you wish to pack/2

list yourself . In such a case, you are better off using a post-processing step.

Now it constructs:

?- pack([1,1,1,1,2,3,3,1,1,4,5,5,5,5], X).
X = [[1, 1, 1, 1], 2, [3, 3], [1, 1], 4, [5, 5, 5|...]] [write]
X = [[1, 1, 1, 1], 2, [3, 3], [1, 1], 4, [5, 5, 5, 5]] .