Data structures in Prolog - Where to start
4 min read
Defining the structures that represent the information of your program should be one of the first steps for its design. For that same reason, after learning the basics of a language, the immediate step should be learning how to represent and use the most common data structures.
The difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Linus Torvalds
Cover photo by Fred Zegveld from Pexels.
This post doesn't aim to cover the basics of Prolog, so it's understood that you are familiar with terms, variables, atoms, facts and predicates. If that's not the case and you want to learn, go check the awesome-prolog repository, where you can find great resources for that.
Purpose of this post
As I said in my post about algebra in Python, we should use built-in functionalities of high-level languages when possible. This makes our code more legible, idiomatic and, usually, faster, because it's probable that the underlying logic is better tested than ours.
When I started to plan this post, I wanted to make a comprehensive guide on different data structures in Prolog. Nonetheless, researching built-in structures, I found out that:
There are small differences between implementations.
There is better content about this topic out there, that takes into account much more things than I did initially.
So instead of making a huge post of a series just by rephrasing all my references, I decided to gather the resources here. It took me some time to find these, so maybe I can spare some time for other people looking for the same information.
I have split the post into two parts:
A collection of references for general and specific data structures.
Some considerations for writing your own data structures.
Links of interest for existing data-structures
Right now I'm working with SWI-Prolog, so part of the links will be to their modules, which may be different in other implementations. However, I might come back to add links from other implementations if I get to work with them.
The SWI-Prolog library - library(lists): List manipulation (Second half)
The SWI-Prolog library - library(ordsets): Ordered st manipulation
Key-value pairs & Association lists
The Power of prolog - Prolog Data Structures - Association lists
SWI-Prolog library - library(pairs): Operations on key-value lists
Data structures and logic programming. Describe relations, not operations
Before starting, it's important to note something. We are used to defining data structures by the relationship between the data they contain and the operations you can perform on them. However, in Prolog, all of this might be defined all at once in many cases.
The same predicate can be used for different tasks because the same definition explains many behaviors. After all, we are talking about a language where you can use
append to split a list:
% Append L1 and L2 into L3 ?- L1 = [1,3,5], L2 = [2,4,6], append(L1,L2,L3). L1 = [1, 3, 5], L2 = [2, 4, 6], L3 = [1, 3, 5, 2, 4, 6]. % Remove L1 from the beginning of L3 to get L2 ?- L1 = [1,3,5], L3 = [1,3,5,2,4,6], append(L1,L2,L3). L1 = [1, 3, 5], L3 = [1, 3, 5, 2, 4, 6], L2 = [2, 4, 6].
The most straightforward example to illustrate this is with a custom data structure is a stack. Instead of implementing the
pop operations, we are just going to define one predicate that describes both operations at the same time.
% push_pop(Stack1, Element, Stack2) push_pop([X|S], X, S). % Use it to pop ?- push_pop([10,20,30], X, S). X = 10 S = [20, 30] % Use it to push ?- push_pop(S, 0, [10, 20, 30]). S = [0, 10, 20, 30]
Here are some interesting topics to also have in mind for your design:
Logical purity, to prevent side effects, facilitate reasoning about your own program and enable automatic optimizations.
Clean vs Defaulty representations to optimize choice points out and keep semantic coherence.
If you've got this far, you must be a Prolog beginner, as I am. I hope you found this useful and if you have more Prolog data structures related resources, feel free to put the link in the comments and I will add it to the list.