difference list append

[Vic Bancroft]

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 
radiational cooling.   mailto:address@hidden  http://america.net/~bancroft