I am learning Prolog and I know there is a data structure already implemented to handle Lists, but I was wondering and if for some reason I want to implement my own data structure, how can I do that? I am not expecting an implementation as an answer, but some ideas would be great.
Thanks.
Lists in Prolog are compound terms with some syntactic sugar. You can reveal the canonical syntax using queries such as:
| ?- write_canonical([]).
[]
yes
| ?- write_canonical([1,2,3]).
'.'(1,'.'(2,'.'(3,[])))
yes
If you compare the query results with the abstract definition of the list data structure, you can see that the empty list is represented by the atom [] and that a non-empty list is a '.'/2 compound term where the first argument is a list element and the second element is a list.
You can define your own "data structures" by defining a suitable compound term. A good place to start would be a simple binary tree. You will need a representation for the empty tree, say, the atom nil, and a compound term with three arguments for the nodes: the node element, the left tree, and the right tree. For example: tree(a, tree(c,nil,nil), tree(f,nil,tree(z,nil,nil))). From this example, can you write predicates that e.g. do tree traversals and call some predicate on the node elements? E.g. writing them to the standard output?