users-prolog
[Top][All Lists]

## difference list append

 From: Vic Bancroft Subject: difference list append Date: Fri, 29 Mar 2002 15:17:47 -0500 (EST)

```On Fri, 29 Mar 2002, Henk Vandecasteele remarked that:

>  > o( A, o( B, C)) :- append(A, B, X), o(X, C).
>  > o( X, X) :- X \= o(_, _).
>
> has not linear complexity,

Consider this definition of append for difference lists,

append_dl( d( H1, T1), d( T1, T2 ), d( H1, T2 ) ).

Partial structures such as difference lists might be useful in many
contexts. . . here is an example using the idea for stacks and queues.

Since pushing and popping elements from the head of a list is like a stack
operation, adding an element to the end of a list allows a use as queue.

/** nq(+Element,+Queue,-Resulting_queue)
*
*    Adds the element to the back of the difference list Queue
*    giving Resulting_queue.
*/
nq( E, d( [], _ ), d( [ E | T ], T ) ) :- !.
nq( E, Q, R ) :- append_dl( Q, d( [ E | T ], T ), R ).

/** as(+Element,+Stack,-Resulting_stack)
*
*    Adds the element to the top of the difference list Stack
*    giving Resulting_stack.
*/
as( E, d( [], _ ), d( [ E | T ], T ) ).
as( E, d( T, T2 ), d( [ E | T ], T2 ) ).

/** ps(-Element,+Stack,-Resulting_Stack)
*
*    Pops the Element from the head of the difference list Stack
*    giving Resulting_stack.  Given the defintion of nq(E,Q,R)
*    ps(E,S,R) will also dequeue elements from the difference list.
*/
ps( E, d( [ E | T ], T2 ), d( T, T2 ) ).

/** dl_list( +DifferenceList, -List )
*
*     convert a difference list to a regular list.
*/

dl_list( d( T, [] ), T ).

/** peekq( +List, -First )
*
* peeks at the First element from the head of the difference list.
*
*/

peekq( d( [ First | _], _ ), First ).

/** peekqq( +List , -Second )
*
* peeks at the Second element from the list ( head of the tail ).
*
*/

peekqq( d( [ _ | [ Second | _ ] ], _ ), Second ).

more,
l8r,

--
katabatic cohabitation :  to live together as if a married couple or in
company;
to exist together, relating as or being like a wind produced by the flow of
cold
dense air down a slope (as of a mountain or glacier) in an area subject to