Structures, Lists, Difference Lists (Part 3)

Posted on | Post modified | In ,

Structures

  • If f is an identifier and t1, t2, …, tn are terms, then f(t1, t2, …, tn) is a term.
  • In the above, f is called a functor and ti is an argument.
  • Structures are used to group related data items together (in some ways similar to struct in C and objects in Java).
  • Structures are used to construct trees (and, as a special case, lists).

Trees

  • Example: expression trees:

    plus(minus (num(3), num(1)), star(num(4), num(2)))

  • Data structures may have variables. And the same variable may occur multiple times in a data structure.

Matching

  • TODO

Accessing arguments of a structure

Lists

  • Prolog uses a special syntax to represent and manipulate lists (syntacic sugar = internally, it uses structures):

    • [1, 2, 3, 4]: represents a list with 1, 2, 3, and 4, respectively.

    • This can also be written as [1 | [2, 3, 4]]: a list with 1 as the head (first element) and [2, 3, 4] as its tail (the list of remaining elements).

      • If X = 1 and Y = [2, 3, 4] then [X | Y] is same as [1, 2, 3, 4].

    • The empty list is represented by [] or nil.

    • The symbol “|” (pipe) and is used to separate the beginning elements of a list from its tail.

      • For example:

        [1, 2, 3, 4] = [1 | [2, 3, 4]] = [1| [2 | [3, 4]]] = [1, 2 | [3, 4]] = [1, 2, 3 |[4]] = [1 | [2| [3| [4| []]]]]

    • Lists are special cases of trees

      • For instance, the list [1, 2, 3, 4] is represented by the following structure:

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
          .
         / \
        1   .
           / \
          2   .
             / \
            3   .
               / \
              4  []
        1
        2
        3
        4

        * where the function symbol ./2 is the list constructor.

        * [1, 2, 3, 4] is same as . (1, . (2, . (3, . (4, p[]))))

    • Strings: A sequence of characters surrounded by double quotes is equivalent to a list of (numeric) character codes: “abc”, “John Smith”, “to be, or not to be”.

      • ?- X= “abc”.

        X = [97, 98, 99]

Programming with Lists

member/2

to find if a given element occurs in a list

append/3

concatenate two lists to form the third list

  • Is the predicate a function?
    • No. We are not applying arguments to get a result. Instead, we are proving that a theorem holds. Therefore, we can leave other variables unbound.
len/2

finds the length of a list (first argument).

Arithmetic