Click HERE to return to our International home page
Концепты Заметки МЕТА Флэнг Онлайн Модули Библио Форум



Главная >  Флэнг > Описание > Списки 
 





• Факториал
• Арифметика
• Пример логической программы
• Структуры и термы
• Атомы
• Списки во Флэнге
• XML- документы
• Векторы
• Таблицы
• Перечисления
• XML-документы (продолжение)



Описание встроенных функций

 


Списки (lists.fln)

Во Флэнге предусмотрены несколько встроенных структур. Например, специальные структуры предусмотрены для работы с XML- и HTML-документами. Среди встроенных структур наиболее универсальным является список. Список - двухаргументная структура. Список настолько важен, что для него предусмотрен специальный формат записи, отличающийся от стандартного вида name(Field1,..., Fieldk). Пример списка: 
  [1,2,3,4,5]
есть список пяти чисел. Список является двухаргументной структурой. Первый аргумент называется головой списка, а второй - хвостом. Голова списка - это его первый элемент, а хвост - список остальных элементов без головы. Для представления головы и хвоста принята следующая запись 
  [Head | Tail]
Таким образом, 
  [1,2,3,4,5]
     = [1 | [2,3,4,5]]
        = [1,2 | [3,4,5]]
           = [1 | [2 | [3,4,5]]]
              = [1 | [2 | [3 | [4 | [5 | []]]]]]

Строительство списка начинается с пустого списка [], к которому один за другим в качестве головы добавляются элементы. Элементами списка могут быть любые объекты, в частности, другие списки: 
  [[1, john], "string", [[2.5],[]]]
Этот список может быть представлен в виде дерева следующим образом:

Жирными точками обозначена операция присоединения головы списка к его хвосту. Рассмотрим несколько примеров функций, работающих со списками. Функция sum суммирует элементы списка. 
  sum([]) :- 0;
  sum([X|Y]) :- X + sum(Y);
Следующая функция - append - объединяет списки. Если имеем два списка [1,2,3] и [4,5,6], мы не можем объединить эти списки простым добавлением первого списка во второй в качестве головы, поскольку в этом случае получим список [[1,2,3],4,5,6] вместо [1,2,3,4,5,6]. Функция append объединяет списки, поэлементно присоединяя элементы первого списка ко второму: 
  append([], Z) :- Z;
  append([X|Y], Z) :- [X | append(Y, Z)];
Следующая функция - reverse - выстраивает элементы списка в обраотном порядке. Опять же, поскольку мы имеем доступ к списку только с его головы ("слева-направо"), то напрямую добраться к элементам, находящимся в хвосте не можем. Идея следующего определения основана на использовании функции append: 
  reverse([]) :- [];
  reverse([X|Y]) :- append(reverse(Y), [X]);
- отрываем у списка голову и присоединяем список, состоящий из одной головы к перевернутому хвосту. Данное определение reverse называется наивным, поскольку оно весьма неэффективно. Флэнг позволяет определить функцию таким образом, что число шагов вычислений будет равно длине списка: 
fastrev(X) :- fastrev1(X, []);

fastrev1([], X) :- X;
fastrev1([X|Y], Z) :- fastrev1(Y, [X|Z]);
Второй аргумент функции fastrev1 используется для "накопления" элементов списка в обратном порядке. Как список закончится, во втором аргументе будет находиться его обращенный вариант.

Следующая функция - sublist - проверяет, является ли второй аргумент подсписком первого. Если да, то возвращает позицию вхождения подсписка в список. Например, sublist([2,1], [3,2,1,0]) = 2. 

  prefix([], X);
  prefix([X|Y], [X|Z]) :- prefix(Y, Z);

  sublist(List1, List2) :- prefix(List1, List2), 1;
  sublist(List1, [_|List2]) :- 1+sublist(List1, List2);
Для проверки используется отношение prefix, истинное, когда первый аргумент является префиксом второго, например [1,2] в [1,2,3,4].

Наконец, определим функцию сортировки списка "вставками". Функция сортирует список-аргумент, добавляя в результирующий список элемент за элементом, и ставя их на нужное место (это делает функция insert). 

  insert(N, []) :- [N];
  insert(N, [M | Rest]) :- N <= M, [N, M | Rest];
  insert(N, [M | Rest]) :- [M| insert(N, Rest)];

  sort([]) :- [];
  sort([N|Rest]) :- insert(N, sort(Rest));

Программа на Флэнге (lists.fln):

 
sum([]) :- 0;
sum([X|Y]) :- X + sum(Y);

append([], Z) :- Z;
append([X|Y], Z) :- [X | append(Y, Z)];



reverse([]) :- [];
reverse([X|Y]) :- append(reverse(Y), [X]);

fastrev(X) :- fastrev1(X, []);

fastrev1([], X) :- X;
fastrev1([X|Y], Z) :- fastrev1(Y, [X|Z]);



prefix([], X);
prefix([X|Y], [X|Z]) :- prefix(Y, Z);

sublist(List1, List2) :- prefix(List1, List2), 1;
sublist(List1, [_|List2]) :- 1+sublist(List1, List2);



insert(N, []) :- [N];
insert(N, [M | Rest]) :- N <= M, [N, M | Rest];
insert(N, [M | Rest]) :- [M| insert(N, Rest)];

sort([]) :- [];
sort([N|Rest]) :- insert(N, sort(Rest));


Примечания

Обратите внимание на использование пустой переменной '_' во втором правиле sublist. Это означает, что значение данного элемента нас не интересует. Использование пустой переменной улучшает читабельность программ и повышает эффективность их выполнения.


Работа в интерпретаторе:

 
(1)?- load(lists);

 true

(2)?- sum([1,2,3,4,5]);

 15

(3)?- sum(["петров ", "иванов ", "сидоров "]);

 "петров иванов сидоров 0"

(4)?- sum([[1],[2]]);

*** RunError: 1st argument of '+' must be integer, float or string

(5)?- append([1,2,3], [4,5,6]);

 [1, 2, 3, 4, 5, 6]

(6)?- append(["петров ", "иванов ", "сидоров "], [1,[2],3]);

 ["петров ", "иванов ", "сидоров ", 1, [2], 3]

(7)?- reverse(["петров ", "иванов ", "сидоров "]);

 ["сидоров ", "иванов ", "петров "]

(8)?- reverse([[1, [2]], 3]);

 [3, [1, [2]]]

(9)?- fastrev([1,2,3,4,5,6,7,8,9,0]);

 [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]

(10)?- prefix([[1,[2]],3, "петров"], [[1,[2]],3, "петров",6,7]);

 true

(11)?- prefix([2,3], [1,2,3,4]);

 fail

(12)?- sublist([2,3], [1,2,3,4]);

 2

(13)?- sublist([3,2], [1,2,3,4]);

 fail

(14)?- insert(3, [1,2,7,9]);

 [1, 2, 3, 7, 9]

(15)?- sort([5,2,3,1,4,6,7,9,8,0]);

 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

(16)?- sort(["петров ", "иванов ", "сидоров "]);

 ["иванов ", "петров ", "сидоров "]

(17)?- sort(["петров ", 1, "иванов ", 2, "сидоров ", 3]);

 [1, 2, 3, "иванов ", "петров ", "сидоров "]


Что делалось

  1. Загружаем программу lists.fln
  2. Пример нахождения суммы элементов списка
  3. Можно суммировать не только числа, но и строки. В этом случае операция сложения работает как конкатенация. Обратите внимание на присутствие нуля в строке.
  4. Функция sum суммирует только элементы "плоских" списков.
  5. Пример использования функции append
  6. append безразличен к содержимому элементов списка
  7. Вызов "наивного" reverse.
  8. reverse переставляет элементы только на верхнем уровне списка
  9. fastrev делает то же, что и reverse, но намного быстрее. Обращение списка [1,2,3,4,5,6,7,8,9,0] требует от fastrev только 12 шагов, в то время, как наивный reverse затрачивает 66.
  10. Функции prefix также безразлично содержимое элементов.
  11. Пример неудачи в проверке prefix
  12. Пример работы функции sublist, находящей позицию подсписка в списке
  13. Пример неудачи в вычислении sublist.
  14. Функция insert вставляет элемент в список, не нарушая упорядоченности списка
  15. Функция sort упорядочивает список
  16. sort может упорядочивать и список строк, поскольку предикат $lt;= работает и на строках (лексикографический порядок без учета регистра).
  17. sort может упорядочивать и смешанные списки.






Контакты
664003 Иркутск, ул. К. Маркса, 1, Иркутский государственный университет, Центр новых информационных технологий

email

 
Заметки*
• Открытая система
• Пакетирование
• XML
• Тексты
• Естественнонаучные ресурсы
• Ресурсы как модели
• Форматы ресурсов
• Информационные уровни
• Трудности
• Учебные объекты
• "Опыт человечества"
• Коммуникативные системы
• О пользе RSS
• Проблема интернета
• Осмысленный интернет
• Идентификация ресуров
• Метаданные и будущее
• Дублинское ядро
• Метаданные и знания
• Онтологии
*Набор кратких заметок и высказываний, посвященных различным аспектам информатизации образования. Что называется - "заметок по поводу...".

Онлайн-сервисы**
• Сайт кафедры математического анализа
• Форум с поддержкой математических формул.
• Flang-online
• TeX->MathML->GIF.
• MathML->GIF.
• Flang-Meta.
• QTI-тестирование с поддержкой математических формул.
• Meta-ZIP
• UDC
• Font-Test
**список эксперементальных сервисов, на которых апробировались реализуемые группой технологии. Сервисы созданы на основе базовых модулей.
Библиотека***
• Онтологии и метаописания
• Учебные объекты
• Языки программирования и логика
• eLearning and Knowledge
• Digital Libraries and Repositories
• Книжки и учебники
***Коллекция публикаций по тематике, собранная из открытых интернет-источников.

.



Copyright ® 2002-2005, TeaCODE.com