Passing from append to difference list on prolog

Question

could someone help me on transforming this code with appends into one using difference of list?

leaves(nil,[]).
leaves(t(X,nil,nil),[X]) :- !.
leaves(t(_,L,R),S) :- leaves(L,SL),
                      leaves(R,SR),
                      append(SL,SR,S).

I tried with this, but it doesn't work and I don't know why.

leaves(BinTree,Leaves) :- leaves_dl(BinTree,Leaves-[]).    
leaves_dl([],X-X).
leaves_dl(t(X,nil,nil), [X|A]-A) :- !.
leaves_dl(t(X,L,R),C-F) :- leaves_dl(L, C-A),
                           leaves_dl(R, A-[X|F]).

Thanks in advance, I would also appreciate a little explanation.

Edit: The purpose of this code is to Traverse a Binary Tree in Post Order

So, a **leaf** in that binary tree is always a compound term `t(X,nil,nil)` but an **inner node** is a node `t(X,L,R)` with at least one of the `L`, `R` not `nil` whereas an empty tree is just `nil`. — David Tonhofer, Dec 09 '20 at 11:17
So I'm breaking the search too soon because it stops without looking for inner nodes? — Micu, Dec 09 '20 at 11:25
If you are just collecting the leaves, preorder/inorder/postorder should not matter. — David Tonhofer, Dec 09 '20 at 11:48

DuDa · Accepted Answer · 2020-12-09T21:31:58.060

2

Your first problem is

leaves_dl([],X-X).

which should be

leaves_dl(nil,X-X).

Changing the behaviour from

?- leaves(t(notleaf,t(leaf1,nil,nil),nil),L).
false.

to

?- leaves(t(notleaf,t(leaf1,nil,nil),nil),L).
L = [leaf1, notleaf].

Now the code does show all the nodes, not just the leaves. If you want to show only the leaves, change leaves_dl(R, A-[X|F]). to leaves_dl(R, A-F)..

?- leaves(t(notleaf1,t(leaf1,nil,nil),t(notleaf2,t(leaf2,nil,nil),nil)),L)
L = [leaf1, leaf2].

edited Dec 09 '20 at 21:31

answered Dec 09 '20 at 11:26

DuDa

3,718
4
16
36

A lot of thanks! This exactly was what I couldn't find – Micu Dec 09 '20 at 11:59
whether you build your list bottom up while traversing the tree's fringe right-to left, or you build it top-down while traversing the fringe left-to-right, the result is exactly the same. and Prolog doesn't care, it is not Lisp, it is just as capable of building lists top-down as it is bottom-up. :) so you can just flip the order of your two sub-goals and it'll work just the same. – Will Ness Dec 09 '20 at 18:48
@WillNess yeah, I switched the order because it was more logical to build the history in order than to piece it together. The order of the subgoals does not matter, but I wanted to tell a more straight forward story ^^ – DuDa Dec 09 '20 at 19:15
I think [going forward](https://stackoverflow.com/a/19951540/849891) is the more straightforward order. :) it's also natural in parsing/DCGs where diff-lists also appear. – Will Ness Dec 09 '20 at 21:18
@WillNess I guess I'll retreat my explanation until I'm more satisfied with it. – DuDa Dec 09 '20 at 21:31
I never claimed it's invalid in this case, it's just a matter of preference and perhaps overall consistency. And it was interesting to see, I've never before realized this about this equivalency and the second - yours - way to write this thing down, and its connection to the Lisp-like reading of it. I think it was valuable to see, maybe you could restore it. :) – Will Ness Dec 10 '20 at 06:23

David Tonhofer · Answer 2 · 2020-12-09T11:51:59.587

Here we collect only leaf nodes, depth first, leftmost first:

leaves(BinTree,Leaves) :- 
   Tip=Fin,                              % create a new "empty open list" which is just an unbound variable
   leaves_dl(BinTree,Fin,FinOut),        % grow the list ending in Fin, giving a new ending FinOut
   FinOut=[],                            % close the list at FinOut; now Tip names a proper list
   Leaves=Tip.                           % this is just about making names equal
   
leaves_dl(nil,Fin,Fin).                  % special case of empty tree

leaves_dl(t(X,nil,nil),Fin,FinOut) :-    % special case of leaf node
   !,                                    % commit to this case
   Fin=[X|FinOut].                       % empty cell at Fin is unified
                                         % with a new listcell with X and
                                         % and an empty cell at FinOut
                                         
leaves_dl(t(_,L,R),Fin,FinOut) :-        % case of inner node
   leaves_dl(L,Fin,Fin2),                % grow the list ending in Fin, giving a new ending Fin2
   leaves_dl(R,Fin2,FinOut).             % grow the list ending in Fin2, giving a new ending FinOut

And so:

?- leaves(t(_,t(_,t(1,nil,nil),t(2,nil,nil)),t(_,t(2,nil,nil),t(3,nil,nil))),L).
L = [1, 2, 2, 3].

This is an application of the "Difference List" applied to the "Open List" While the "Difference List" is about two variables denoting different positions in the same list, in this case we go to the extreme and have one of the variables denote the tip of the list (the first listcell), while the other denotes whatever is on second position of the last listcell (what I call the "fin"). For a closed list this is [], for an open list, it is an "empty cell" in memory (a non-logical concept, but maybe someone has "logicized" this using modal logic at some point; it certainly seems possible).

A generic "Difference List" (really, "list difference": Pos1-Pos2) on a proper (or closed) list

Pos1 ------->[|]             ^
            /   \            | "list difference" Pos2-Pos1 is
           1    [|]          | [1,2]      
               /   \         V   
              2    [|] <----Pos2
                  /   \         
                 3     [] <--- list properly ends in []: proper list

A "Difference List" applied to an "open list" ending in an empty cell:

             [|]<------- Tip (of open list) ^
            /   \                           |
           1    [|]                         | "list difference" Fin-Tip
               /   \                        | is [1,2,3]
              2    [|]                      |
                  /   \                     V
                 3   ~empty cell~ <--- Fin

Analogous to imperative programming with pointer Fin=[X|FinOut] grows the open list with X, and yield a fresh variable FinOut denoting the new fin, which is an empty cell. We can then grow it some more later:

            [|]<-----------  Tip (of longer open list)
           /   \
          1    [|]
              /   \
             2    [|]
                 /   \
                3    [|] <--- Fin after unification
                    /   \
                   X   ~empty cell~ <--- NewFin, a fresh variable

When we are done, we just need to unify the current Fin with [], closing the list:

            [|]<------------  Tip (now of a proper list)
           /   \
          1    [|]
              /   \
             2    [|]
                 /   \
                3    [|]
                    /   \
                   X     [] <--- Fin unified with `[]`

whats the procedure for moving on? Should I retreat or do we have a race condition or just ignore each other? — DuDa, Dec 09 '20 at 11:37
@Raubsauger Good question. I don't know whether OP will change his/her question, but I will have to go away for a few hours now. So you can go ahead. — David Tonhofer, Dec 09 '20 at 11:53
Thanks a lot for the detailed answer! I'm starting with prolog so some of this things seem a bit advanced to me; but now I understand a bit better how it works what I was trying to do — Micu, Dec 09 '20 at 12:00

Passing from append to difference list on prolog

2 Answers2