Encoding Lists as FDs

A list of FD l = (fd1, fd2 ... fdn) is not a legal FD according to the definition of FDs. The main reason why such a form is not accepted in the syntax of FUF is that defining what should be the unification of two lists (fd11, fd12 ... fd1n) and (fd21, fd22, ... fd2p) is not clear (should it be the union of the 2 lists, its intersection using unification as an equality test, the pairwise unification of the elements one by one, or the product of the unifications, what happens when one unification of the elements fails...) and it is not clear how to extend the notion of path to allow access within a list.

Instead of adding lists as a primitive type of FDs, it is possible to encode lists as regular FDs. This is the approach used and supported in FUF.⁸

Quite simply, lists are represented as FDs with two features, CAR and CDR (with names ala Lisp).    

          
The list (a b c) is represented by the FD:


((car a)
 (cdr ((car b)
       (cdr ((car c)
             (cdr none))))))


The list (a (b c)) is represented by the FD:


((car a)
 (cdr ((car ((car b)
             (cdr ((car c)
                   (cdr none)))))
       (cdr none))))
          
          

When using this encoding for lists, the path notation can be used to access any element of the list (using a sequence of car and cdr), and the unification method to use when dealing with lists can be defined declaratively in the grammar. FUF includes tools to make the reference to list elements and the development of list-related grammars easier.