Determining list depth using difference lists.

[fxtdr79]

I'm trying to solve a problem using difference lists (which I don't really understand well and 2 weeks worth of reading on the net hasn't changed that). Basically I want to determine the depth of the elements in a list, ie, if I were to ask

depth([a,b,[c,[],[d,e]],f], L)

Prolog would answer
L = [0,0,[1,1,[2,2]],0]

I realize this is wrong but I really just have no idea what's going on. Any help would be great thanks.

depth(L1, L2) :- depth(L1, L2, 0).
depth([], L2, 0).
depth([H|T], L2, N) :- depth(T, [L2|N], N1), N is N1 + 1.

 

[kahleen]

depth(L1, L2) :- depth(L1, L2, 0).

depth([], [N], N).
depth([H], [HD], N) :-
	H = [_ | _], !,
	N1 is N + 1,
	depth(H, HD, N1).
depth([_], [N], N) :- !.
depth([H | T], [HD | TD], N) :-
	H = [_ | _], !,
	N1 is N + 1,
	depth(H, HD, N1),
	depth(T, TD, N).
depth([_ | T], [N | TD], N) :-
	depth(T, TD, N).

 

[joel76]

Good code, but it uses open lists, not difference-lists.

 

[fxtdr79]

Care to correct the code showing it with difference lists joel?

 

[joel76]

That's a very good question. I'm looking for ...

 

[joel76]

I hope the deadline is passed ...

depth(L1, L2) :- depth_dl(L1-[], 0, L2-[]).

depth_dl([]-[], _N, []-[]).

depth_dl([H|T1]-T2, N, [R|R1]-S) :-
	H \= [],
	is_list(H),
	!,
	N1 is N+1, depth_dl(H-[], N1, R-[]),
	depth_dl(T1-T2, N, R1-S).

depth_dl([_H|T1]-T2, N, [N|R]-S) :-
	depth_dl(T1-T2, N, R-S).

 

[kahleen]

are T2 and S ever going to have other values than [] at any step of the recursivity? it seems each one of the lists after the "-" operator is [] at each step ... i think something different should be there ...

 

[kahleen]

joel, I modified your code a bit:

depth_dl(X - X1, _, X - X1) :-
	unify_with_occurs_check(X, X1), !.
depth_dl([H | T1] - T2, N, [R | R1] - S) :-
	H = [_ | _], !,
	N1 is N + 1,
	depth_dl(H - [], N1, R - []),
	depth_dl(T1 - T2, N, R1 - S).

depth_dl([_H | T1] - T2, N, [N | R] - S) :-
	depth_dl(T1 - T2, N, R - S).

one can launch it like this:

?- depth_dl([a,b,[c,[],[d,e]],f | T] - T, 0, L).

L = [0, 0, [1, 1, [2, 2]], 0 | T] - T

 

[joel76]

I modified it too. As you pointed, the use of difference lists was quite artificial.

depth(L1, L2) :-
	depth_dl(L1, 0,L2-[]).

% special case for [] when it's not the end of the list
depth_dl([[]|T], N, [N|X]-Y) :-
	depth_dl(T, N, X-Y).

% general case
depth_dl([H|T], N, X-Y) :-
	(   is_list(H) ->
	    N1 is N+1, 	depth_dl(H, N1, R-[]), X = [R|X1]
	;
	    depth_dl(H, N, X-X1)),
	!,
	depth_dl(T, N, X1-Y).

% we reach the end of the list
depth_dl([], _N, Z-Z) :- !.

% for every thing else
depth_dl(_H, N, [N|Y]-Y).

Un example is

?- depth_dl([a,[c,[1,2,[3,[4, []]],[d,e,[]]], 5],f] , 0, L-[]).
L = [0,[1,[2,2,[3,[4,4]],[3,3,3]],1],0].

or

?- depth([a,[c,[1,2,[3,[4, []]],[d,e,[]]], 5],f], L).
L = [0,[1,[2,2,[3,[4,4]],[3,3,3]],1],0].

P.S. kahleen you modify the initial list [a,b,[c,[],[d,e]],f | T] - T is not [a,b,[c,[],[d,e]],f]

 

[kahleen]

that was my understanding of difference lists ...

 

[joel76]

I'm sorry, what you wrote is correct :

depth(L, L1) :-
  % with your code
  depth_dl(L-[], 0, L1-[]).

 

[kahleen]

but then again, we come to the same problem of artificial difference lists, with the trailing -[] ...

i think your last code is better suited for solving the problem. my version would only work if one can build, for example, the list [a, b, c, d, e | T] from list [a, b, c, d, e], with T being any list ...

then, the call depth([a, b, c, d, e], ...) will call depth_dl([a, b, c, d, e | T] - T, ...)

i didn't manage to get it right so far, so i stopped trying

 

[kahleen]

i finally got it right, i think:

difflistify(L, A, B) :-
	nonvar(L), !,
	expand_term(( o --> L ), E),
	E = (o(A, B) :- true).
difflistify([], A, B) :-
	unify_with_occurs_check(A, B), !.
difflistify([H|T], [H|A], B) :-
	difflistify(T, A, B).


depth(L1, L2) :-
	difflistify(L1, L1t, T1),
	depth_dl(L1t - T1, 0, L2t - T2),
	difflistify(L2, L2t, T2).


depth_dl(X - X1, _, X - X1) :-
	unify_with_occurs_check(X, X1), !.

depth_dl([H | T1] - T2, N, [R | R1] - S) :-
	H = [_ | _], !,
	N1 is N + 1,
	depth_dl(H - [], N1, R - []),
	depth_dl(T1 - T2, N, R1 - S).

depth_dl([_H | T1] - T2, N, [N | R] - S) :-
	depth_dl(T1 - T2, N, R - S).

difflistify is using DCGs to transform any list to a diff list, and vice-versa:

list -> diff list
?- difflistify([a, b, c], A, B).

A = [a, b, c | B]


diff list -> list
?- difflistify(L, [a, b, c | B], B).

L = [a, b, c]

once we have [a, b, c | B], we call:

?- depth_dl([a, b, c | B] - B, 0, L2t - T2).

B = T2
L2t = [0, 0, 0 | T2]

and we use difflistify to turn L2t - T2 back into an open list

i'm not sure how portable DCGs are, though

 

[kahleen]

oops, my bad ... DCGs are not required at all ... they only solve half the problem (list -> diff list), but the other rules solve the whole problem all by themselves ... took me a while to figure out a complicated solution to a simple problem

final version of the code:

difflistify([], A, B) :-
	unify_with_occurs_check(A, B), !.
difflistify([H|T], [H|A], B) :-
	difflistify(T, A, B).


depth(L1, L2) :-
	depth(L1, 0, L2).

depth(L1, N, L2) :-
	difflistify(L1, L1t, T1),
	depth_dl(L1t - T1, N, L2t - T2),
	difflistify(L2, L2t, T2).

depth_dl(X - X1, _, X - X1) :-
	unify_with_occurs_check(X, X1), !.

depth_dl([H | T1] - T2, N, [R | T3] - T4) :-
	H = [_ | _], !,
	N1 is N + 1,
	depth(H, N1, R),
	depth_dl(T1 - T2, N, T3 - T4).

depth_dl([_ | T1] - T2, N, [N | T3] - T4) :-
	depth_dl(T1 - T2, N, T3 - T4).

 

[joel76]

but then again, we come to the same problem of artificial difference lists, with the trailing -[] ...

No, we must use [] to unify the trailing [...|X]-X and get a proper list as a result.

 

[kahleen]

Yes but putting L - [] instead of just L doesn't make use of the full power of difference lists, as I understand them. The depth_dl code uses [...|X] - X, but if the code is launched with X being a ground term like [] then there is no conceptual difference between this and normal lists. One has to ensure that the code is called with X unbound, in my opinion.

 

[joel76]

You can try

depth(L1, L2) :-
    depth_dl(L1, 0,R),
    R = L2-[].