На этом шаге мы приведем общие сведения о списках.

    Пусть A - конечное множество элементов одинакового типа.

Определение (индуктивное) [1, с.102, 103-104].

Список над элементами типа A (обозначается List(A)) определяется так:

   (1) [] ∈ List(A);
   (2) x ∈ A & y ∈ List(A) => (x:y) ∈ List(A).

    Пусть {a₁, a₂,...,a_n} - множество элементов одного типа A.

    Другими словами, список над элементами типа A - это пара, первый элемент которой является атомарным значением, а второй - списком:

    (a1:(a2:(... :(an:[])...)))

    Самым простым способом конструирования списка является перечисление элементов списка: элементы заключают в квадратные скобки и разделяют запятыми. Элементами списка могут быть как константы, так и выражения, например:

   (1) x = 10                       (2) p = True; q = False; a = 3
       y:: [Int]                        z:: [Bool]
       y = [1+2,3*x,length [1,2]]       z = [3<4,a==5,p && q]

    Ограничений на длину списка нет, он может содержать, например, один элемент (такой список называется синглетоном).

    Например, список [[1,2,3]] является синглетоном, т.к. он содержит один элемент, являющийся списком.

    На следующем шаге мы рассмотрим конструкторы типа данных "список".

Предыдущий шаг Содержание Следующий шаг