Списъци в Пролог
Във функционални и логически езици списъците се използват изключително често, те ви позволяват да съхранявате набор от данни с произволна дължина. Тази статия показва много примери за обработка на списъци на език Prolog. Повечето от примерите са написани на динамично въведени диалекти (SWI/GNU/Arity Prolog), но с незначителни промени ще работят добре при силно типизирани реализации (Turbo/Visual Prolog).
Списъци. Теория
Като цяло списъкът е абстрактен тип данни, който дефинира набор от стойности. В тази статия списък означава "свързан списък", който е една от възможните реализации на абстрактни списъци.
Свързаният списък е структура от данни, състояща се от възли. Възелът съдържа данни и връзка (указател, връзка) към един или два съседни възла. Прологовите списъци са просто свързани, т.е. всеки възел съдържа само една връзка.
Когато работите с единично свързани списъци, е необходимо да изберете първия възел (наречен главата на списъка), останалите възли (съставляващи опашката на списъка) могат да бъдат получени чрез придвижване по указателите до последния възел. Опашката на списъка е същият като оригинала, така че се обработва по същия начин (рекурсивно).
Списъци в Пролог. Синтаксис
Когато използвате статично напечатан диалект, трябва да декларирате типа на списъка (например в Turbo Prolog това се прави в раздела домейни):
Горният пример показва рекурсивния характер на списъците - след като главата (първият елемент) бъде премахната, опашката остава, което също е списък. Операцията разделяне на глава и опашка може да се използва за формиране на нов списък. Езикът има обозначение за празен списък и той постоянно се използва в рекурсивни функции за фиксиране на края на обработката.
Рекурсивна обработка на списъка. Примери за
sum_list (Списък, сума) - изчисляване на сумата на елементите от списъка
Елементите на празен списък се сумират до нула. Ако списъкът не е празен, ние го разделяме на първия елемент и опашката. Обработваме опашката рекурсивно, в резултат на което получаваме сумата от елементите на частта от списъка, с изключение на първия елемент. Добавете първия елемент, за да получите крайния резултат.
nth0 (индекс, списък, елемент) - функцията за получаване на елемента от списъка с дадения индекс. Индексирането започва от нула. Ако необходимият елемент не присъства, функцията се проваля.
Функцията завършва своя собствена и успешно връща първия елемент от списъка, ако индексът е нула и е възможно да се отдели първият елемент от списъка. Функцията се проваля, ако Idex е по-малко от нула или остава по-голямо от нула, ако списъкът е празен. Ако списъкът не е празен (първият елемент е успешно отделен от него) и индексът е по-голям от нула, опашката на списъка се обработва рекурсивно и индексът се намалява с един (в крайна сметка списъкът е намалял с един елемент).
член (Elem, Списък) - търси стойност в списъка. Завършва късмет, ако елементът бъде намерен.
Ако стойността на първия елемент от списъка съвпада със стойността на необходимия елемент, правилото незабавно завършва с успех. В противен случай първият елемент се изхвърля и търсенето продължава в опашката. Веднага щом разделянето на списъка на глава и опашка стане невъзможно, правилото ще се провали.
Важното е, че предикатът може да върне няколко решения (предикатът е недетермиран), така че първото правило не съдържа изрязване. Това поведение е особено важно, ако функцията-член се използва за итерация по всички елементи на списък (просто предайте анонимна променлива вместо Elem).