AI, machine learning and deep learning · Intermediate

Structured terms

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

Structured terms in Prolog use functors to name complex, hierarchical data objects rather than compute values, enabling the representation of variable-length sequences like routes. These terms are visualized as trees where the functor is the root and arguments are branches, allowing for recursive definitions that handle arbitrary data lengths. Prolog supports both custom structured terms and built-in lists, which use the dot functor and empty list terminator for flexible tree and linear notations.

Intuition

Think of a structured term not as a calculation, but as a labeled container. Just as a mathematical function computes a value, a Prolog functor names a structure composed of simpler parts. This is crucial for handling data of unknown or variable length, such as a route with an arbitrary number of stops. By defining a term recursively—where the structure contains another instance of itself—you can build complex, nested objects like a route containing a sub-route. This tree-like organization allows Prolog to store and retrieve detailed paths without needing separate rules for every possible route length, bridging the gap between abstract logic and concrete data representation.

Key equations

reachable(X,Y,noroute):−connected(X,Y,L).
(1)

Base case: if X is directly connected to Y, the route is empty (noroute).

reachable(X,Y,route(Z,R)):−connected(X,Z,L),reachable(Z,Y,R).
(2)

Recursive case: X connects to Z, and Z reaches Y via route R, forming route(Z,R).

route(tottenhamcourtroad,route(leicestersquare,noroute))
(3)

Example of a structured term representing a route with two intermediate stations.

[a,b,c]
(4)

Linear notation for a list, equivalent to the tree structure.(a,.(b,.(c,[]))).

Derivation

  1. Functors name structures rather than evaluating to values, distinguishing them from mathematical functions.
  2. Structured terms enable variable-length data representation by avoiding fixed-argument predicates.
  3. Recursive definitions allow a functor (e.g., route) to contain itself, creating nested hierarchies.
  4. The structure is visualized as a tree with the functor as the root and arguments as branches.
  5. Built-in lists use the dot functor and empty list terminator [] for both tree and linear notation.
  6. Queries retrieve these structures, returning detailed paths rather than just boolean results.

Worked example

Problem

Represent a route from Oxford Circus to Charing Cross via Tottenham Court Road and Leicester Square using structured terms.

  1. Identify the connections: Oxford Circus connects to Tottenham Court Road, which connects to Leicester Square, which connects to Charing Cross.
  2. Apply the recursive rule: reachable(X,Y,route(Z,R)) where Z is the next station and R is the remaining route.
  3. Base case: The final leg from Leicester Square to Charing Cross is a direct connection, resulting in noroute.
  4. Construct the term: route(tottenham_court_road, route(leicester_square, noroute)).

Answer route(tottenham_court_road,route(leicester_square,noroute))

Common mistakes

  • Confusing functors with mathematical functions: functors name a structure, they do not evaluate to a value.
  • Thinking that relations with the same name but different numbers of arguments are the same relation: they are actually different relations.
  • Assuming user-defined functors have a standard linear notation: only built-in datatypes like lists have this.
  • Forgetting that the second argument of the route functor in the recursive definition is itself a route or terminator.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

This is a text lesson: it has no animation code yet.

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.