# Difference List

**URL:** <https://swi-prolog.discourse.group/t/difference-list/959>\
**Category:** Wiki\
**Created:** [July 16, 2019, 9:40am UTC](https://swi-prolog.discourse.group/t/difference-list/959 "2019-07-16T09:40:05Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Wiki](https://avatars.discourse-cdn.com/v4/letter/w/e8c25b/32.png) [@Wiki](https://swi-prolog.discourse.group/u/Wiki)\
**Post date:** [July 16, 2019, 9:40am UTC](https://swi-prolog.discourse.group/t/difference-list/959/1 "2019-07-16T09:40:05Z")

</div>

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](https://swi-prolog.discourse.group/t/wiki-discussion-difference-list/960)

> 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](https://swi-prolog.discourse.group/t/wiki-discussion-difference-list/960)

> Note: This is a wiki and if you have [Trust level](https://blog.discourse.org/2018/06/understanding-discourse-trust-levels/): [Basic](https://swi-prolog.discourse.group/badges/1/basic) you can edit this by clicking on the pencil icon in the lower right. ![Capture](https://global.discourse-cdn.com/free1/uploads/swiprolog/original/1X/bfd4c3b77dc7f3f98ece3d5ae3202fcccb0fb8b3.png)  
> These topics also have history so they can be rolled-back if needed.

References:

“The Craft of Prolog” by Richard A. O`Keefe ([WorldCat](http://www.worldcat.org/oclc/1024831685)) Section 1.5 - Difference Lists

[Difference lists in Prolog](https://pdfs.semanticscholar.org/080b/8ff48a5069ea2d69f12e0ea397ed4c7e1482.pdf) by Attila Csenki  
[Difference Lists](https://www.cs.cmu.edu/~fp/courses/lp/lectures/11-diff.pdf) by Frank Pfenning  
[Open Lists and Difference Lists](https://web.archive.org/web/20180923230230/http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html) by Paul Brna

Learn Prolog Now! Chapter 7 Definite Clause Grammars by Patrick Blackburn, Johan Bos and Kristina Striegnitz  
[Common version](http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlch7)  
[Testing version](http://lpn.swi-prolog.org/lpnpage.php?pagetype=html&pageid=lpn-htmlch7) - using SWISH  
[Early version](http://cs.union.edu/~striegnk/learn-prolog-now/html/node54.html)

Amzi - [Difference List](http://www.amzi.com/manuals/amzi/pro/ref_dcg.htm)  
Wikipedia [DCG](https://en.wikipedia.org/wiki/Definite_clause_grammar)  
[WikiBooks](https://en.wikibooks.org/wiki/Prolog/Difference_Lists)

Difference list in other programming languages

Mercury - [DCG](https://www.mercurylang.org/information/doc-release/mercury_ref/DCG_002dgoals.html#DCG_002dgoals)  
F# - [DList](https://fsprojects.github.io/FSharpx.Collections/reference/fsharpx-collections-dlist.html)  
Haskell - [Difference list](https://wiki.haskell.org/Difference_list)  
OCaml - [DList](https://drup.github.io/2016/08/02/difflists/)

* * *

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_.

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](https://swi-prolog.discourse.group/t/using-phrase-from-file/1880/9)).

_Concrete list_ is probably a _closed list_ but it is not well defined. ([ref](https://swi-prolog.discourse.group/t/using-phrase-from-file/1880/9))

* * *

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_.

```prolog
:- 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.

```prolog
:- 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).

```

* * *

```prolog
% 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.

```prolog

:- 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

```prolog
spacing_difference_list(0,Hole,Hole)

```

uses a variable `Hole` and not `[]`

```prolog
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`

```prolog
:- 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](https://www.swi-prolog.org/pldoc/man?predicate=string_without//2) form the DCG/basics library ([source](https://github.com/SWI-Prolog/swipl-devel/blob/master/library/dcg/basics.pl))

```prolog
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

```prolog
:- 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](https://en.wikipedia.org/wiki/Whitespace_character).

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.

```prolog

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

```prolog

:- 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).

```