Search code examples
prolog

Compound terms and Lists in Prolog

Why are compound terms preferable over lists in terms of performance? For example,

matrix(row(1,2,3),row(1,2,3),row(1,2,3))

is preferable over

[[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
Solution

  • Something that the other (excellent) answer did not mention:

    Access to the member of a list by its position means that you need to traverse the list. Access to the argument of a term should be possible in constant time. So for random access a term should be more efficient.

    Short aside: you can attempt to make the list traversal marginally faster. But the SWI-Prolog implementation of nth0_det/3 almost smells of desperation ;)

    You might be interested in this thread, esp. this summary that talks about lists and terms among other things.

    A few rules of thumb follow.

    Use case:

    • if you know in advance how many things you have, use a term.
    • if you can have 0 or more of the same things, use a list.
    • if you need a look-up table, neither is optimal

    Efficiency:

    • if you want random access, use a term
    • if your algorithm works well on a singly-linked list, a Prolog list is perfectly good choice.

    From the last point follows: try to find algorithms that use linked lists, not random-access arrays. It is not always possible, but for many problems you have a choice. The classical example would be a quick sort vs. a merge sort: in Prolog, a merge sort is definitely quicker.

    Either way, first make sure you get it right, then worry about efficiency. And make sure you measure the performance bottlenecks before starting to optimize.

    Choosing an optimal algorithm and data structure means, of course, that you need to know both your problem and the available tools. Not relevant to your problem, but the beauty of what used to be the "Standard Template Library" for C++ is that for both algorithms and data structures, time complexity ("big O notation") is an inherent property, not an implementation detail.