Reversal of empty or single-element list considered successful why?

[peter.ludemann]

@brebs

Can “fix” bagof/3 with: …

Because of the way that free variables interact with bagof/3, I think this is better:

bagof_fail_empty(Template, Goal, Bag) :-
    (   bagof(Template, Goal, Bag)
    *-> true
    ;   Bag = []
    ).

As @jan says, doing this indicates a misunderstanding of bagof/3, but sometimes it’s convenient to have a predicate always return a value rather than handle a failure case - for example, if I want to do further processing on each item in the “Bag”.
Similarly, whatever the theoretical underpinnings of “reverse” of an empty list might be, it’s sometimes convenient to generate a list in reverse order then use reverse/3, so it simplifies the code if reverse/3 can handle [] and [_] just like any other list.

@boris - do you have any suggestions on how to write predicates so that they generate lists in correct order, without using append/3? Sometimes I have no problems doing this; but at other times (e.g., when using a list as an accumulator, or using foldl), I just give up and use reverse/3 on the result. I suppose this requires using difference lists, but sometimes getting them right (whithout using DCGs) is too difficult for me. “When you are a Bear of Very Little Brain, and you Think of Things, you find sometimes that a Thing which seemed very Thingish inside you is quite different when it gets out into the open and has other people looking at it.”

[EricGT]

@brebs

Using reverse/2 as a simple example of my kinda-generic puzzlement:

?- reverse(L, R).
L = R, R = [] ;      Why?
L = R, R = [_] ;     Why?
L = [_A, _B],        Fair enough
R = [_B, _A] ;

How can the reversal be considered successful in the first 2 cases of [] and [_], when no reversal has occurred?

Remember that list in Prolog and in many programming languages are really just syntactic sugar. Also do not confuse list with array they are not the same.

If one thinks of list using dotted pair notation then the answer hopefully is obvious. To see a list in dotted pair notation with SWI-Prolog use write_term/2 with the dotlists(Bool) option.

?- reverse(L, R),format('----------~n',[]),write_term(L,[dotlists(true)]),nl,write_term(R,[dotlists(true)]).
----------
[]
[]
L = R, R = [] ;
----------
.(_2912,[])
.(_2912,[])
L = R, R = [_] ;
----------
.(_2912,.(_2918,[]))
.(_2918,.(_2912,[]))
L = [_A, _B],
R = [_B, _A] ;
----------
.(_2912,.(_4134,.(_2918,[])))
.(_2918,.(_4134,.(_2912,[])))
L = [_A, _B, _C],
R = [_C, _B, _A] ;
----------
.(_2912,.(_4134,.(_4140,.(_2918,[]))))
.(_2918,.(_4140,.(_4134,.(_2912,[]))))
L = [_A, _B, _C, _D],
R = [_D, _C, _B, _A] ;
----------
.(_2912,.(_4134,.(_5662,.(_4140,.(_2918,[])))))
.(_2918,.(_4140,.(_5662,.(_4134,.(_2912,[])))))
L = [_A, _B, _C, _D, _E],
R = [_E, _D, _C, _B, _A] ;

HTH

---

For those of us who started programming when we had to create list using dotted pair notation, syntactic sugar for list has saved hundreds if not thousands of hours over the years.

[EricGT]

@peter.ludemann

I suppose this requires using difference lists, but sometimes getting them right (whithout using DCGs) is too difficult for me.

Without writing a blog entry here are two clauses that I use as the basis to get my mind adjusted when writing clauses using difference list.

name_start_char(T0,T) -->
    name_start_char(C),
    { T0 = [C|T] }.

'name_char*'(T0,T) -->
    name_char(T0,T1),
    !,
    'name_char*'(T1,T).
'name_char*'(T,T) --> [].

Also remember that the result is still not a list but an difference list with the second list being just a single variable. The difference list can easily be converted to a list, e.g.

functor(A,B) :-
   ...,
   functor_inner(A,B,T0,T),
   T = [], % Converts difference list (open list) to closed list.
   L = T0, % Use L as the variable to remember that now it is a closed list.
   ...
   .

As is obvious to you I am not using the standard notation when passing difference list of DL1-DL2 but instead T0,T which lets me know to think differently when writing the code for the clause.

The trick that helps me the most is to leave T0 = [C|T] in the code until I have it working correctly then I sometimes factor it out. But often I just leave it in as the SWI-Prolog parser will do the change for me when converting the DCG.

One user I know who post production quality code on GitHub using SWI-Prolog with Differnce List is Wouter Beek (GitHub). I have learned a lot over the years reading his code.

[joeblog]

@peter.ludemann

do you have any suggestions on how to write predicates so that they generate lists in correct order, without using append/3? Sometimes I have no problems doing this; but at other times (e.g., when using a list as an accumulator, or using foldl), I just give up and use reverse/3 on the result. I suppose this requires using difference lists, but sometimes getting them right (whithout using DCGs) is too difficult for me.

The relationship between lists and database rows has been something I’ve been struggling with, and reading through the list of PostgreSQL’s Aggregate Functions made something which others may find obvious clear to me: lists are way of aggregating database results. That’s why SQL’s array_agg (the equivalent of Prolog’s findall), PostgreSQL’s jsonb_agg which produces JSON arrays irritatingly indexed from 0 instead of 1 used by SQL arrays, and json_object_agg which produces a dictionary where any duplicate keys overwrite existing values, are in the same group as sum, avg etc

Once I twigged that in both Prolog and SQL whenever I was struggling with very long lists/arrays slowing things down, it was because I wasn’t thinking databases. It’s been a tough learning curve to unlearn all the bad habits of an over-reliance on lists picked up from Python etc.

[lug]

That’s a funny question. What is the reverse of a list? It’s philosophical in nature. Well, you questioned when it could be useful which can be answered very easily. Isn’t the philosophical query more difficult?

“When is it useful?”

Consider the empty chatroom problem. An empty chatroom is a chat with no users, maybe a thread with no replies, etc. I set my program to show the list of users in reverse order. If the chat is in standby or I’m the only user, the program breaks. Unfortunately, the operation of showing the users breaks, I have to redo the whole program/chat and tell it to reverse but only if there are more than 1 user. A situation like this is not rare at all, the chat will have such an amount of users at some point (no one joined, I joined).

“In contrast, there is no concept of a list of length -1”

I’m now questioning the notion, that you have showed me, of negative lists. I think maybe we should have a negative list lib. I want to subtract lists or have a list of minus [1,2]. How do the operations work? Well, I’m sure you can figure it out.

[wlodr]

Negative lists:
It is easy to construct a difference list of negative length. Just remove some elements from the empty difflist. You obtain something that after inserting some elements becomes the empty list.

The details are a not difficult exercise. I may provide a solution if needed.