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

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?

Isn’t this logic flawed, or am I being too pedantic?

Well…

1 + 0 = 1

pi * 1 = pi

How can the multiplication be successful if no multiplication has occurred?

3 * 0 is even more absurd.

But of course I hope that someone who has proper math education can give a proper answer.

Maths is different - 0 is a valid number, as are negative numbers and even imaginary numbers.

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

I suppose my question is, what is the use case for a reversal of `[]` or `[_]` to be considered successful? Just seems to be wasting the first 2 choices presented.

I am not so sure, but it is also late here. Are you saying that `[]` and `[_]` are not a valid lists that deserve to be reversed? Like, maybe 0 should not be multiplied because it doesn’t do anything good?

Maybe you get a bunch of lists and reverse them, without knowing if they are all at least 2 elements long?

1 Like

My point is that a reversal cannot be shown to have been performed. That is failure, rather than success.

Similarly: prolog - Split a list in half - Stack Overflow
How can an empty list (or single element) be split in half? There’s nothing to split.

I hope this is relevant, at least touched.

A list is a series (a function whose dom is a subset of N (natural naumberi) which assigns to a natural number. The domain may be empty (the empty list ). The reverse maps a list to a list, and preserves domain and image of the source and target of the map reverse.

From the set theory, if two functions share domain and image , and cardinality of domain is less than 2,
then two function must be identical.

Prolog knows the set theory.

3 Likes

If we’re thinking of reverse/2 as a relation, and not as an operation, I think these results make perfect sense.
Looking at the documentation of reverse/2 I see the following:

`````` reverse(?List1, ?List2)
is true when the elements of List2 are in reverse order compared to List1
``````

I read this as saying that reverse/2 holds when the two lists have the same length, and for each index `I` from 0 to `Len - 1`, the element that appears in the first list in index `I` appears in the second list in index `Len - 1 - I`.
So if the if both lists are empty, `Len = 0` and this holds trivially because there are no indices `I` to consider.
If `Len = 1`, we only have one index to consider, namely `I = 0`. In this case, the first and only element of the first list must appear in the second list in index `Len - I - 1 = 1 - 0 - 1 = 0`, so the second list must be the same one-element list as the first list.

2 Likes

You seem to say that the actual reversal is performed also for and [_],
but in this particular case as identity “operation”.
I feel like to agree on your interpretation, provided that identity operation is actual.

1 Like

Such theory is not a satisfactory excuse for why the first 2 solutions provided by reverse/2 (and suchlike) are practically useless.

When is a reversal of `[]` or `[_]` actually useful?

Presumably it’s extremely rare, and so can be handled as a special case, rather than slowing down and inconveniencing everyone with such nonsense

When you have a “reverse” used in your program and you don’t want a special case to treat empty lists and one-element lists that might end up there. The other option would be to define this helper function:

``````reverse_any([], []).
reverse_any([X], [X]).
reverse_any([X,Y|Rest], R) :-
reverse([X,Y|Rest], R).
``````

We are trying to summon ouroboros again

Altogether reversing a Prolog list is something I try to avoid when I program. Using it is an admission that I am not prepared to think about a proper way to achieve my goal. (EDIT: I do use it often enough)

This is now a question just out of curiosity: when do you @brebs end up reversing lists in your code? Is there something in common between these uses?

1 Like

Dear @brebs, I am afraid that I am missing your point. My comment is
based on the following “common sense”.

Reverse operation R is defined on series (string) of letters
in minimum principle.

1. R(e) = e ( e is the empty string )
2. R(a) = a ( a is a letter)
3. R(uw)=R(w)R(u) for strings u, w.

and Prolog reverse/2 is an implementation of this R in prolog lists.
I am not sure that the reverse operation can be defined in prolog clauses
without 1 and 2 unless Prolog builds-in the reverse, in which codes for 1 and 2
might not be necessary. Anyway, I am missing your point, in particular
"reverse is a rare case. "

I suppose that `reverse([], [])` is true for the same reason that `append([], [], [])` is true - which seems acceptable.

I was being too pedantic

I think this is a surprisingly deep question and @kuniaki.mukai [edit: and @oskardrums each have] a good, principled answer, and @Boris is half-way there. The ultimate cause behind what you describe is that all of mathematics is based on entirely arbitrary axioms and the theorems that follow from them, under various formal systems of inference.

To pick up @Boris’ example, why does `0*x = 0`? Because that’s an axiom. We take it for granted, because. Why does reverse map the empty list to itself and the unary list to itself? Because that’s an axiom.

In a sense, I think if we could really dig deep down into the minds of the people who came up with that, is that it was the least annoying way to define list-reversal. In a sense, if you want to have list reversal that makes sense you have to find somewhere to put the empty list, and the one-element list. It all comes down to where it’s best to put it. Or least worst.

Consider if you will division: why is division by 0 undefined? Multiplication is the mirror of division, but multiplication by 0 is always defined. There’s a semi-formal explanation of why you can’t divide x by 0 (because it does not allow x to be retrieved, like with multiplication) but, at the end of the day, the best explanation is that “you can’t do that, because it’s against the rules”.

So that’s why `reverse([],[])` is true and `reverse([x],[x])` is true: them’s the rules. It is what it is and as it shall ever be.

I recall doing a free online course on computer science given by Jeffrey Ullman where he discussed how when you write any kind of aggregator, you need to give a value to the base case.

For instance, if you take the sum of an arbitrary long list of numbers, the base number is 0, and in most programing languages, including SWI-Prolog’s sum_list/2 with an empty list yields 0.

``````?- sum_list([], S).
S = 0.
``````

Prolog has the concept of semidet, and one could argue the sum of an empty list should be false, not 0. Since one needs helper predicates anyway, it’s possibly easier to adapt the basic pattern to do that in Prolog than other languages by adding a `L \== []` guard:

``````mysum(L, S) :-
L \== [],
mysum_(L, 0, S).

mysum_([], S, S).

mysum_([H|T], S1, Acc) :-
S2 is S1 + H,
mysum_(T, S2, Acc).
``````

Reverse can be written using the same pattern as mysum (the builtin reverse/2 is more complex to make it bidirectional, whereas this simple example only works if the first argument is an input list and the second a variable to be returned).

``````myreverse(L, R) :-
L \== [],
myreverse_(L, [], R).

myreverse_([], R, R).

myreverse_([H|T], R, Acc) :-
myreverse_(T, [H|R], Acc).
``````

Back to Ullman’s course, he said when writing aggregators, it’s important to think what the base or starting value is. For instance, with and you would start with true, and toggle to false as soon as you encountered a false. With or, you would start with false, and toggle to true as soon as a true appeared in the list. So `and_agg([])` would be true and `or_agg([])` would be false.

Long story short, there are conventions for aggregates to return a base value for an empty list, and making that the empty list when shunting or reversing is fairly established and standard I think.

This can be argued both ways – findall/3 returns an empty list if there are no solutions but bagof/3 fails. As a result, findall/3 can be used to define non-logical predicates such as “not P”: `findall(.,P,[])`.

But, in general, it is useful to define a base case, such as `sum([])` is `0` (that’s more-or-less the definition of zero in Peano arithmetic). And, in the case of reverse/2, intuitively, the reversal of an empty list is an empty list; and reversal of a single element list is the same single element (think about walking forwards and backwards on a line of objects – if there’s nothing there, you get nothing whether walking forwards or backwards; with a single object, you get the same result whether walking forwards or backwards).

This reasoning fails with aggregators such as “maximum” – there’s no obvious base case for the maximum of an empty list. So, “maximum” should fail with an empty list (one could perhaps make an argument for negative infinity, but that creates other problems).

3 Likes

Food for thought.

• Is the data in the list typed?
• Is the list homogeneous or heterogeneous?
• What is the operator used on the list?

If the list is typed, the type is integer and the operator is addition then in most cases I would expect `0` to be the base case for an empty list.

If the list is typed, the type is string, the string type allows for an empty string then I would expect `""` to be the base case for an empty list.

If the list is typed, the type is edge, the edges do not form a circular reference and the operator is next then in most cases I would expect either a single vertex (the list is a straight path) or a list of vertices (the list is a graph representing a tree and backtracking walks the tree).

Can “fix” bagof/3 with:

``````bagof_fail_empty(Template, Goal, Bag) :-
bagof(Template, Goal, Bag),
!.
bagof_fail_empty(_Template, _Goal, []).
``````

But now I’m arguing the opposite viewpoint to the start of this thread

2 Likes

I’ve been struggling to understand the difference between `and-or trees` I encountered in Robert Kowalski’s Logic For Problem Solving (I’ve linked to a pdf copy he kindly made freely available on the web) vs `minimax` game trees which is popularly thought to have come from John von Neumann’s and Oskar Morgenstern’s Theory of Games and Economic Behavior, though they never actually used the word minimax.

I had a bit of an epiphany when I realised that if you use 0 and 1 notation for booleans, and is simply min(p1, p2, p3, …) and or is simply max(p1, p2, p3, …), which also works around the problem of that if you think of or as addition, you get the weird arithmetic 1 + 1 + … = 1

Not sure how one would tie that to `min([])` = 1 and `max([])` = 0 if one substituted them for and_agg(L) and or_agg(L) though.

That “fix” is seen often. It mostly implies someone did not understand bagof/3 That happens quite often as while bagof/3 and setof/3 are elegant, they are also hard to understand. Few people realize they are nondet predicates, i.e., on backtracking they return 0 or more non-empty sets/bags with different bindings for the “free” variables. There is no point in returning empty sets/bags as this is always a solution. I guess the other logically correct solution would be to always return `[]` as first/last solution.

Note that if there are no free variables, bagof/3 simply calls findall/3 (with some additional logic to rebind variables), failing on an empty result set and setof/3 calls bagof/3 followed by sort/2.

5 Likes

IMHO, the value of the empty list should depend on the target algebra.
If one expects his function behaves in a homomorphic way, then the function should maps the source unit to the target one.

It might be often confusing about how to define the intersection / union of the emtpy family of sets.
I feel a parallel between the empty list and the empty family. So the value of the empy list depends on how the operation treats the unit on its domain. By the way, the intersection of the empty family usually defined to be the universal set in the discourse.

Sorry for my partial / poor understanding what is discussed in this thread.

1 Like