Простое объяснение работы со списками

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 год, 6 месяцев назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #5271
      @admin
      StudLance.ru

      В этой теме несколько часто используемых предикатов работы со списками описаны более простым языком и с большим числом примеров.

      Тут не будут описаны принципы логического программирования. Вы должны знать, что функция пролога (предикат) может завершится успешно, а может — нет. Должны знать, что с заглавной буквы начинаются имена переменных и т.п. Должны понимать что будет получено при выполнении следующего кода:

        фрукт(яблоко).
        фрукт(апельсин).
        фрукт(персик).
      goal 
        фрукт(Фрукт).

      Если вдруг вам нужно разобраться со списками, а этой «базы» у вас нет — прочитайте введение в логическое программирование.

      Содержание

      1. входит_в — поиск элемента в списке
      2. построение списка решений — findall
      3. без_повторов — проверка отсутствия в списке одинаковых элементов
      4. Оставить только уникальные элемента списка (убрать повторы)

      Поиск элемента в списке — входит_в

      Предикат member (встроенный в swi prolog) при реализации на Visual Prolog иногда называют входит_в, реализуется он следующим образом:

        входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
        входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
          	входит_в(Элемент, ОстальныеЭлементы).

      На вход функции подается два аргумента — значение искомого элемента и список. Возможны два варианта:

      • Если оба аргумента имеют значение — выполняется проверка наличия элемента в списке. Например:
        входит_в(3, [1,2,3,4]), write(true); write(false).
        выведет на экран true.

        В таком случае функция отрабатывает следующим образом:
        1) первое правило
        входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
        выполняет сравнение искомого элемента с первым элементом списка. Список для этого разделяется на ПервыйЭлемент и Остальные при помощи оператора |. Если сравнение проходит успешно — то функция завершится успешно (т.к. искомый элемент входит в список).
        2) если первое правило не выполнилось, то управление переходит на второе правило предиката.

        входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
            	входит_в(Элемент, ОстальныеЭлементы).

        При этом список точно также разделяется на Первый элемент и Остальные. Вызывается рекурсивный поиск Элемента среди Остальных.

        Так, если мы будем выполнять такую операцию:
        входит_в(3, [1,2,3,4])
        то сначала выполнится сравнение 3 и 1, т.к. они не равны — переходим на второе правило, «выкидываем» единицу из списка и рекурсивно обрабатываем то, что осталось: входит_в(3, [2,3,4])
        теперь сравнивается 2 и 3 — процесс повторяется…
        входит_в(3, [3,4])
        тут сравнение пройдет успешно, функция вернет true. Что будет происходить дальше более подробно описано ниже…

      • Если в качестве первого аргумента передана переменная — функция вернет в качестве решений последовательно все элементы списка.
        входит_в(X, [1,2,3,4]), write(X); write(" кончилось").
        В данном случае на экране будет напечатано «1234 кончилось».

        Работает это точно также как в первом случае, но первое правило вместо сравнения выполняет присваивание и всегда завершается успешно. Т.е. Элемент получает значение первого элемента обрабатываемой части списка и возвращается в качестве результата, затем процесс повторяется.

      Использование входит_в

      Что можно сделать с помощью этого предиката?
      Во-первых, можно выполнить генерацию чего-либо. Например, решаете вы задачу, в которой нужно установить «кто что любит»:

      генерация(Любят):-
        Фрукты = [яблоко, апельсин, персик],
        %Люди = [петя, коля, толя],
      
        входит_в(Фрукт_Пети, Фрукты),
        входит_в(Фрукт_Коли, Фрукты),
        входит_в(Фрукт_Толи, Фрукты),
      
        Любят = [
          любит(петя, Фрукт_Пети),
          любит(коля, Фрукт_Коли),
          любит(толя, Фрукт_Толи)
        ].

      Такая простая программа сгенерирует все возможные варианты распределения фруктов между участниками:

      Любят = [любит(петя, яблоко), любит(коля, яблоко), любит(толя, яблоко)]; % первое решение
      Любят = [любит(петя, яблоко), любит(коля, яблоко), любит(толя, апельсин)]; % второе решение
      % ... еще много решений
      Любят = [любит(петя, персик), любит(коля, персик), любит(толя, персик)]. % последнее решение

      Во-вторых, предикат можно использовать для проверки наличия элементов. Так, например, если все в той же задаче о фруктах потребовалось бы оставить только те варианты, где Петя любит апельсин, мы написали бы так:

      генерация(Любят), входит_в(любит(петя, апельсин), Любят).

      Построение списка решений — findall

      С помощью встроенного предиката findall можно собрать все решения (результаты работы другого предиката) в список.

      Так, например, если у нас есть такой предикат:

      животное(собака).
      животное(кошка).
      животное(енот).

      То запрос животное(Х). даст 3 варианта решения:

      Х = собака;
      Х = кошка;
      Х = енот.

      Но если нам надо собрать все решения этого предиката в список — можно написать так:
      findall(Х, животное(Х), СписокЖивотных).

      Вторым аргументом findall принимает «цель» (предикат), решения которой нужно собрать. Первым аргументом передается имя одной из переменных, использованных в цели. Третий аргумент — результат работы, является списком. В данном случае мы просим его собрать все имена животных и получим СписокЖивотных = [собака, кошка, енот].

      Другой пример:

      Список = [1,2,3],
      findall(Элемент, входит_в(Элемент, Список), Элементы).

      После выполнения получим все Элементы = [1,2,3].

      Проверка отсутствия одинаковых элементов — без_повторов

      Предикат принимает на вход список и проверяет чтобы в нем не было двух одинаковых элементов.

      без_повторов([]).
      без_повторов([Первый|Остальные]):-
        NOT(входит_в(Первый, Остальные)),
        без_повторов(Остальные).

      Первое правило говорит о том, что в пустом списке нет повторяющихся элементов.
      Второе — отделяет от исходного списка Первый элемент и ищет его среди Остальных. Если поиск завершается успешно — то правило завершает работу неудачей (значит в списке есть повторы). Если же поиск проваливается (оператор NOT завершится успешно) — то проверка продолжается рекурсивно для Остальных элементов. Рассмотрим на примерах:

      • ->без_повторов([1,2,3,2,4]).
        Список не пустой, поэтому разделяется на Элемент = 1 и Остальные = [2,3,2,4]. Найти Элемент среди Остальных не получается, поэтому выполняется рекурсивный вызов:
        ->->без_повторов([2,3,2,4]).
        Список опять не пустой, поэтому еще раз выполняется разделение на Первый = 2 и Остальные = [3,2,4]. На этот раз входит_в(2, [3,2,4]) завершится успешно, поэтому выполнение нашего предиката завершится — мы получим fail (т.е. в исходном списке есть повторы).
      • без_повторов([1,2,3]).. Вызовы будут выполняться по той же схеме, что и примере выше, в следующем порядке:
        -> без_повторов([1,2,3]).
        ->-> без_повторов([2,3]).
        ->->-> без_повторов([3]).
        ->->->-> без_повторов([]).

        На последнем шаге сработает первое правило и выполнение предиката завершится успешно, т.е. в исходном списке нет повторов.

      Например, с помощью такого правила мы можем модифицировать рассмотренный выше пример с генерацией фруктов следующим образом:

      генерация_без_повторов(Любят):-
        генерация(Любят),
        findall(Фрукт, входит_в(любит(_Имя, Фрукт), Любят), Фрукты),
        без_повторов(Фрукты).
      

      При этом генерация будет выдавать все варианты (как и раньше), вызов findall выделяет из списка структур только Фрукты (без имен их владельцев). Функция без_повторов завершится успешно только для тех списков, в которых нет одинаковых элементов. Таким образом на выходе предиката генерация_без_повторов окажутся только варианты, в которых все люди любят разные фрукты, например:

      Любят = [любит(петя, яблоко), любит(коля, апельсин), любит(толя, персик)]; % первое решение
      Любят = [любит(петя, яблоко), любит(коля, персик), любит(толя, апельсин)]; % второе решение
      % ...
      Любят = [любит(петя, персик), любит(коля, апельсин), любит(толя, яблоко)]; % последнее решение
      

      Оставить только уникальные элемента списка (убрать повторы)

      убрать_повторы([], Буфер, БезПовторов):-
        БезПовторов = Буфер.
      убрать_повторы([ПервыйЭлемент|ОстальныеЭлементы], Буфер, БезПовторов):-
        входит_в(ПервыйЭлемент, Буфер), 
        убрать_повторы(ОстальныеЭлементы, Буфер, БезПовторов).
      убрать_повторы([ПервыйЭлемент|ОстальныеЭлементы], Буфер, БезПовторов):-
        NOT(входит_в(ПервыйЭлемент, Буфер)),
        убрать_повторы(ОстальныеЭлементы, [ПервыйЭлемент|Буфер], БезПовторов).

      Приведенное решение использует метод накапливающего параметра. Несколько других вариантов решения можно найти тут: «преобразовать список во множество«. Итак, как это работает?

      На вход первым аргументом подается исходный список, их него постепенно отделяются элементы и:
      1) если такого элемента еще не было — добавляются в Буфер;
      2) если такой элемент уже был — пропускаются (не добавляются никуда).

      Если исходный список закончился — значит в буфере собрались все элементы без повторов. В этом случае Содержимое буфера копируется в БезПовторов (третий аргумент списка). Начальным содержимым буфера должен быть пустой список.

      Предикат состоит из трех правил, каждое из которых обрабатывает один из случаев:
      1) когда исходный список пуст;
      2) когда первый элемент является новым (еще не встречался и подлежит добавлению в буфер);
      3) когда первый элемент уже встречался.

      Разберем на примере, пусть дан список [1,3,1,4,3], будут произведены следующие вызовы:

      -> убрать_повторы([1,3,1,4,3], [], Результат).
      -> {сработает второе правило, т.к. «1» еще не встречался}
      ->-> убрать_повторы([3,1,4,3], [1], Результат).
      ->-> {сработает второе правило …}
      ->->-> убрать_повторы([1,4,3], [3,1], Результат).
      ->->-> {сработает третье правило, т.к. «1» входит_в [3,1], элемент будет пропущен}
      ->->->-> убрать_повторы([3], [4,3,1], Результат).
      ->->->-> {сработает третье правило …}
      ->->->->-> убрать_повторы([], [4,3,1], Результат).
      ->->->->-> {сработает первое правило, т.к. входной список пуст}
      ->->->->-> Результат = [4,3,1]
      ->->->->-> { дальше значение результата передается «назад»}
      ->->->-> Результат = [4,3,1]
      ->->-> Результат = [4,3,1]
      ->-> Результат = [4,3,1]
      -> Результат = [4,3,1]

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×