Search code examples
listprologempty-listdifference-lists

Is it possible to write an empty list as a difference list in Prolog?


Empty lists are ... strange, to a Prolog beginner like myself. I would say that it isn't possible to write an empty list [] as a difference list T1-T2 just as it isn't possible to write an atom as a difference list. However, I would guess that to use recursion, there must be a way to use [] in a difference list setting. I have Google'd for this but I cannot find an answer, and Bratko (Prolog Programming for AI) only briefly touches the subject.

So, is it possible to write an empty list as a difference list in Prolog, if so how and when would it be useful?


Solution

  • Problems with understanding this topic are typically due to using misleading terminology.

    As recommended in tutorial.pdf and especially pap95.pdf, use for example list difference or simply difference.

    Section 5 of Teaching beginners Prolog contains relevant reasons for this.

    The empty list is uniquely denoted by the atom [].

    Note that a list difference always means reasoning about two lists, and due to this categorical difference between a single and multiple lists, you can at best find some correspondence or analogy, but not identity between the empty list and a list difference.

    I completely support the view expressed in the paper above that you should focus on using DCGs, at least at first. Reasoning about differences explicitly will come naturally later to you.