Difference List

How to: Difference List

Note: This is a work in progress. When it is complete these notes will be removed.

Note: Do not reply to this topic. Questions, concerns, comments, etc. are to handled in
Wiki Discussion: Wiki: How to - Difference List

Note: This is just to get the topic started and hopefully others to jump in and make this useful. Even if you are brand new to Prolog, this is such a basic and fundamental concept that you can and should join in to help improve the value of this Wiki. Join the discussion at Wiki Discussion: Wiki: How to - Difference List

Note: This is a wiki and if you have Trust level: Basic you can edit this by clicking on the pencil icon in the lower right. Capture
These topics also have history so they can be rolled-back if needed.

References:

“The Craft of Prolog” by Richard A. O`Keefe (WorldCat) Section 1.5 - Difference Lists

Difference lists in Prolog by Attila Csenki
Difference Lists by Frank Pfenning
Open Lists and Difference Lists by Paul Brna
Efficiency of Difference-List Programming by Ulrich Geske and Hans-Joachim Goltz

Learn Prolog Now! Chapter 7 Definite Clause Grammars by Patrick Blackburn, Johan Bos and Kristina Striegnitz
Common version
Testing version - using SWISH
Early version

Amzi - Difference List
Wikipedia DCG
WikiBooks

Difference list in other programming languages

Mercury - DCG
F# - DList
Haskell - Difference list
OCaml - DList

Difference Lists Explored


Difference list go by a few other names such as open list or partial list and what most Prolog programmers refer to as list are also known as closed list or proper list.

A closed list always ends with [] but a partial list always ends with an unbound variable. The unbound variable that ends a partial list is sometimes called a hole. To state in another way, the base case for a closed list will be [] and the base case for a partial list will be an unbound variable.

There are also lazy list. A lazy list is a list whose tail is an attributed value and when you unify against the tail the lists gets longer (and will either terminate in [] or in a new attributed variable). (ref).

Concrete list is probably a closed list but it is not well defined. (ref)


In learning to use partial list having a type check is handy. Here is the code to type check that a value is a partial list.

:- multifile
error:has_type/2.

error:has_type(partial_list,L0) :-
    '$skip_list'(_, L0,L),
    var(L).

Test case that help to illustrate the differences between a closed list and an open list.

:- begin_tests(list_info).

dot_list_test_case_generator( _      , 'A'            , open   ).  % Hole            % Base case
dot_list_test_case_generator( [_|_]  , '.(A,B)'       , open   ).  % .(A,Hole)
dot_list_test_case_generator( [_,_|_], '.(A,.(B,C))'  , open   ).  % .(A,.(B,Hole))
dot_list_test_case_generator( [a|_]  , '.(a,A)'       , open   ).  % .(a,Hole)
dot_list_test_case_generator( [a,b|_], '.(a,.(b,A))'  , open   ).  % .(a,.(b,Hole))
dot_list_test_case_generator( []     , '[]'           , closed ).  %                 % Base case
dot_list_test_case_generator( [_]    , '.(A,[])'      , closed ).  %
dot_list_test_case_generator( [_,_]  , '.(A,.(B,[]))' , closed ).  %
dot_list_test_case_generator( [a]    , '.(a,[])'      , closed ).  %
dot_list_test_case_generator( [a,b]  , '.(a,.(b,[]))' , closed ).  %

test(001,[forall(dot_list_test_case_generator(List,Expected_dot_list,_))]) :-
    numbervars(List,0,_),
    with_output_to(atom(Dot_list),write_term(List,[numbervars(true),dotlists(true)])),

    assertion( Dot_list == Expected_dot_list ).

test(002,[forall(dot_list_test_case_generator(List,_,Expected_list_type))]) :-
    (
        is_of_type(partial_list,List)
    ->
        List_type = open
    ;
        List_type = closed
    ),
    assertion( List_type == Expected_list_type ).

:- end_tests(list_info).

% This is the classic difference list append but with type checking added.
difference_append(Open_list,Hole,Open_or_closed_list) :-
    must_be(partial_list,Open_list),
    must_be(var,Hole),
    must_be(list_or_partial_list,Open_or_closed_list),
    Hole = Open_or_closed_list.

% This predicate is useful in learning how to use difference list.
% This is often not seen in code because it can be replaced with 
%    Hole = Open_list
dl_combine(Hole,Open_list) :-
    difference_append(_,Hole,Open_list).

% Create closed list given open list.
open_closed_list(Open_list,Hole,Closed_list) :-
    is_of_type(var,Closed_list),
    is_of_type(partial_list,Open_list),
    is_of_type(var,Hole),
    !,
    Hole = [],
    Closed_list = Open_list,
    must_be(proper_list,Closed_list).

% Create open list and hole given closed list
open_closed_list(Open_list,Hole,Closed_list) :-
    is_of_type(proper_list,Closed_list),
    is_of_type(var,Open_list),
    is_of_type(var,Hole),
    open_closed_list_prime(Closed_list,Hole,Open_list),
    must_be(partial_list,Open_list).

open_closed_list_prime([],Hole,Hole).
open_closed_list_prime([H0|T0],Hole,[H0|T]) :-
    open_closed_list_prime(T0,Hole,T).

Test case for proceeding difference list predicates.


:- begin_tests(difference_list).

% This is here to allow a quick comparison of append/3
test(001) :-
    L1 = [a],
    L2 = [b],
    L3 = _,
    append(L1,L2,L3),

    assertion( L1 == [a]   ),          % NB L1    DID NOT change its value
    assertion( L2 == [b]   ),          % NB L2    DID NOT change its value
    assertion( L3 == [a,b] ).          % NB L3    DID     change its value

test(002) :-
    DL1 = [a|Hole1],
    DL2 = [b|Hole2],
    difference_append(DL1,Hole1,DL2),

    assertion( DL1   == [a,b|Hole2] ), % NB DL1   DID     change its value
    assertion( Hole1 == [b|Hole2]   ), % NB Hole1 DID     change its value
    assertion( DL2   == [b|Hole2]   ). % NB DL2   DID NOT change its value

% Demonstrates how to see a difference list as a dot list and output with a variable name for use with comparison
test(003) :-
    DL1 = [a|Hole1],
    DL2 = [b|Hole2],
    difference_append(DL1,Hole1,DL2),

    numbervars(DL1,0,_),
    with_output_to(atom(Dot_list),write_term(DL1,[numbervars(true),dotlists(true)])),

    assertion( DL1 == [a,b|Hole2] ),
    assertion( Dot_list == '.(a,.(b,A))' ).

test(004) :-
    L1 = [a,b,c|H1],
    L2 = [d,e,f|H2],
    L3 = [g,h,i|H3],
    dl_combine(H1,L2),
    dl_combine(H2,L3),

    assertion( L1 == [a,b,c,d,e,f,g,h,i|H3] ),
    assertion( H1 == [d,e,f,g,h,i|H3] ),
    assertion( L2 == [d,e,f,g,h,i|H3] ),
    assertion( H2 == [g,h,i|H3] ),
    assertion( L3 == [g,h,i|H3] ),
    assertion( H3 == H3 ).

% Notice that dl_combine(H1,L2) is the same as H1 = L2.
test(005) :-
    L1 = [a,b,c|H1],
    L2 = [d,e,f|H2],
    L3 = [g,h,i|H3],
    H1 = L2,
    H2 = L3,

    assertion( L1 == [a,b,c,d,e,f,g,h,i|H3] ),
    assertion( H1 == [d,e,f,g,h,i|H3] ),
    assertion( L2 == [d,e,f,g,h,i|H3] ),
    assertion( H2 == [g,h,i|H3] ),
    assertion( L3 == [g,h,i|H3] ),
    assertion( H3 == H3 ).

test(006) :-
    L1 = [32|H1],
    L2 = [32|H2],
    L3 = [32|H3],
    H1 = L2,
    H2 = L3,

    assertion( L1 == [32,32,32|H3] ),
    assertion( H1 == [32,32|H3] ),
    assertion( L2 == [32,32|H3] ),
    assertion( H2 == [32|H3] ),
    assertion( L3 == [32|H3] ),
    assertion( H3 == H3 ).

open_closed_list_test_case_generator( Hole      , Hole, []    ).
open_closed_list_test_case_generator( [a|Hole]  , Hole, [a]   ).
open_closed_list_test_case_generator( [A|Hole]  , Hole, [A]   ).
open_closed_list_test_case_generator( [a,b|Hole], Hole, [a,b] ).
open_closed_list_test_case_generator( [A,b|Hole], Hole, [A,b] ).
open_closed_list_test_case_generator( [a,B|Hole], Hole, [a,B] ).
open_closed_list_test_case_generator( [A,B|Hole], Hole, [A,B] ).

test(007,[forall(open_closed_list_test_case_generator(Open_list,Hole,Expected_close_list))]) :-
    open_closed_list(Open_list,Hole,Closed_list),

    assertion( Closed_list == Expected_close_list ),
    assertion( Hole == [] ).

test(008,[forall(open_closed_list_test_case_generator(Expected_open_list,_,Closed_list))]) :-
    open_closed_list(Open_list,_,Closed_list),

    assertion( Open_list =@= Expected_open_list ).

:- end_tests(difference_list).

Example that creates a difference list useful for adding spacing when generating pretty printed text.

Notice that code is recursive and the base case

spacing_difference_list(0,Hole,Hole)

uses a variable Hole and not []

spacing_difference_list(0,Hole,Hole) :- !.
spacing_difference_list(Length0,Spacing,Hole) :-
    must_be(nonneg,Length0),
    must_be(partial_list,Spacing),
    must_be(var,Hole),
    succ(Length,Length0),
    spacing_difference_list(Length,Spacing0,Hole),
    Spacing = [32|Spacing0].

Test cases for spacing_difference_list/3

:- begin_tests(spacing_difference_list).

test(001) :-
    spacing_difference_list(0,Spacing,Hole),

    assertion( Spacing == Hole ),
    assertion( is_of_type(var,Hole) ).

test(002) :-
    spacing_difference_list(1,Spacing,Hole),

    assertion( Spacing == [32|Hole] ),
    assertion( is_of_type(var,Hole) ).

test(003) :-
    spacing_difference_list(2,Spacing,Hole),

    assertion( Spacing == [32,32|Hole] ),
    assertion( is_of_type(var,Hole) ).

test(004) :-
    spacing_difference_list(3,Spacing,Hole),

    assertion( Spacing == [32,32,32|Hole] ),
    assertion( is_of_type(var,Hole) ).

test(005) :-
    spacing_difference_list(3,Spacing1,Hole1),
    spacing_difference_list(4,Spacing2,Hole2),

    assertion( Spacing1 == [32,32,32|Hole1] ),
    assertion( is_of_type(var,Hole1) ),

    assertion( Spacing2 == [32,32,32,32|Hole2] ),
    assertion( is_of_type(var,Hole2) ),

    Hole = Spacing1,
    Hole1 = Spacing2,
    Hole2 = [],

    assertion( Hole == [32,32,32,32,32,32,32] ).

:- end_tests(spacing_difference_list).

Here is a variation of a popular predicate string_without//2 form the DCG/basics library (source)

string_without_partial_list(End,Codes,Hole) -->
	{
        string(End), !,
        string_codes(End,EndCodes)
	},
	list_string_without_partial_list(EndCodes,Codes,Hole).
string_without_partial_list(End,Codes,Hole) -->
	list_string_without_partial_list(End,Codes,Hole).

list_string_without_partial_list(Not,[C|T],Hole) -->
	[C],
	{ \+ memberchk(C,Not) }, !,
	list_string_without_partial_list(Not,T,Hole).
list_string_without_partial_list(_,Hole,Hole) --> [].

Test cases for string_without_partial_list//3

:- begin_tests(string_without).

control_dcg(Before) -->
    string_without("c",Before).

test(control_test) :-
    Input = "abcdef",
    string_codes(Input,Codes),
    DCG = control_dcg(Before),
    phrase(DCG,Codes,Rest),

    assertion( Codes == `abcdef` ),
    assertion( Before == `ab` ),
    assertion( Rest == `cdef` ).

partial_list_dcg(Partial_list,Hole) -->
    string_without_partial_list("c",Partial_list,Hole).

test(partial_list) :-
    Input = "abcdef",
    string_codes(Input,Codes),
    DCG = partial_list_dcg(Partial_list,Hole),
    phrase(DCG,Codes,Rest),

    assertion( Codes == `abcdef` ),
    assertion( Partial_list =@= [0'a,0'b|_] ),
    assertion( Hole =@= _ ),
    assertion( Rest == `cdef` ).

:- end_tests(string_without).

Pretty print of XML using DCG to parse the XML and difference list to reconstruct the XML with the added whitespace.

Still working on this, but compete enough to show.

If you ever heard the expression

Using difference list is about filling the holes

and you understand the code below then the statement should make sense.


xml_pretty_print(Transformed_text) -->
    element_04(0,Hole0,Hole),
    {
        Hole = [], % Convert open list to closed list
        string_codes(Transformed_text,Hole0)
    }.

element_04(Spacing_length,Hole0,Hole) -->
    tag_begin_04(Spacing_length,Hole0,Hole1),
    optional_line_end_04,
    value_04(Spacing_length,Hole1,Hole2),
    optional_line_end_04,
    tag_end_04(Spacing_length,Hole2,Hole3),
    optional_line_end_04,
    { Hole = Hole3 }.

elements_04(Spacing_length,Hole0,Hole) -->
    { Hole0 = [10|Hole1] },
    element_04(Spacing_length,Hole1,Hole2), !,
    elements_04(Spacing_length,Hole2,Hole).
elements_04(_Spacing_length,Hole0,Hole) -->
    { 
        Hole0 = [10|Hole1] ,
        Hole = Hole1 
    }.

optional_line_end_04 -->
    (
        "\n", !
    ;
        []
    ).

% Value is a single value
value_04(_Spacing_length,Hole0,Hole) -->
    \+ "<",
    string_without_partial_list("<",Value_codes,Hole1), !,
    {
        Hole0 = Value_codes,
        Hole1 = Hole
    }.
% Value is a group of values
value_04(Spacing_length0,Hole0,Hole) -->
    { Spacing_length is Spacing_length0 + 3 },
    elements_04(Spacing_length,Hole0,Hole1),
    {
        Hole = Hole1
    }.

tag_begin_04(Spacing_length,Hole0,Hole) -->
    \+ "</",
    "<",
    string_without_partial_list(">",Tag_codes,Hole3),
    ">",
    { spacing_difference_list(Spacing_length,Spacing,Hole1) },
    {
        Hole0 = Spacing,
        Hole1 = [0'<|Hole2],
        Hole2 = Tag_codes,
        Hole3 = [0'>|Hole4],
        Hole = Hole4
    }.

tag_end_04(_Spacing_length,Hole0,Hole) -->
    "</",
    string_without_partial_list(">",Tag_codes,Hole2),
    ">",
    {
        Hole0 = [0'<,0'/|Hole1],
        Hole1 = Tag_codes,
        Hole2 = [0'>|Hole3],
        Hole3 = Hole
    }.

Test cases


:- begin_tests(xml_pretty_print).

test(001) :-
    Input = "<note>",
    string_codes(Input,Codes),
    DCG = tag_begin_04(3,Hole0,Hole),
    phrase(DCG,Codes,[]),

    assertion( Hole0 == [32,32,32,60,110,111,116,101,62|Hole] ),
    assertion( var(Hole)  ).

test(002) :-
    Input = "</note>",
    string_codes(Input,Codes),
    DCG = tag_end_04(3,Hole0,Hole),
    % nl,
    phrase(DCG,Codes,[]),

    assertion( Hole0 == [60,47,110,111,116,101,62|Hole] ),
    assertion( var(Hole)  ).

test(003) :-
    Input = "Alice",
    string_codes(Input,Codes),
    DCG = value_04(3,Hole0,Hole),
    % nl,
    phrase(DCG,Codes,[]),

    assertion( Hole0 == [65,108,105,99,101|Hole] ),
    assertion( var(Hole)  ).

test(004) :-
    Input = "<to>Bob</to>",
    string_codes(Input,Codes),
    DCG = element_04(3,Hole0,Hole),
    phrase(DCG,Codes,[]),

    assertion( Hole0 == [32,32,32,60,116,111,62,66,111,98,60,47,116,111,62|Hole] ),
    assertion( var(Hole)  ).

test(005) :-
    Input = "<to>Bob</to><from>Alice</from>",
    string_codes(Input,Codes),
    DCG = elements_04(3,Hole0,Hole),
    % nl,
    phrase(DCG,Codes,[]),

    assertion( Hole0 == [10,32,32,32,60,116,111,62,66,111,98,60,47,116,111,62,10,32,32,32,60,102,114,111,109,62,65,108,105,99,101,60,47,102,114,111,109,62,10|Hole] ),
    assertion( var(Hole)  ).

% Ref: https://www.w3schools.com/xml/note.xml
test(006) :-
    Input = "\c
        <note>\c
          <to>Bob</to>\c
          <from>Alice</from>\c
          <heading>Reminder</heading>\c
          <body>Don't forget me this weekend!</body>\c
        </note>\c
        ",
    string_codes(Input,Codes),
    DCG = xml_pretty_print(Transformed_text),
    phrase(DCG,Codes,[]),

    assertion( Transformed_text == "<note>\n   <to>Bob</to>\n   <from>Alice</from>\n   <heading>Reminder</heading>\n   <body>Don't forget me this weekend!</body>\n</note>" ).

test(007) :-
    Input = "\c
        <note>\n\c
          <to>Bob</to>\n\c
          <from>Alice</from>\n\c
          <heading>Reminder</heading>\n\c
          <body>Don't forget me this weekend!</body>\n\c
        </note>\n\c
        ",
    string_codes(Input,Codes),
    DCG = xml_pretty_print(Transformed_text),
    phrase(DCG,Codes,[]),

    assertion( Transformed_text == "<note>\n   <to>Bob</to>\n   <from>Alice</from>\n   <heading>Reminder</heading>\n   <body>Don't forget me this weekend!</body>\n</note>" ).

:- end_tests(xml_pretty_print).
1 Like