Differenzlisten

Eine Liste kann nicht nur im Format [a, b, c, ...] repräsentiert werden (wobei sie mittels Listenreststrich kürzer dargestellt werden kann), sondern auch als Differenzliste. Diese besteht aus zwei Listen, die als Differenz notiert werden. Dabei wird ein beliebig langer Teil einer Liste als Subtrahend an die eigentliche Liste angefügt mit der Bedingung, dass der Subtrahend Suffix der gesamten Liste ist (z.B. [a, b, c] – [b, c]). Oftmals bietet es sich an, einen Listenrest abzuziehen, der als Variable wiedergegeben ist ([a, b|X] – X).
Diese Differenzlisten-Notation ermöglicht es, durch Unifikation auf innere Elemente einer Liste zuzugreifen, ohne die vorangehenden Elemente zuerst abarbeiten zu müssen. Dies ist beispielsweise bei der Verkettung von Listen ein viel effizienteres Verfahren als ein rekursives append-Programm, da Unifikation genügt.