Пролог программирование - путь к решению

Question

Я изучаю пролог в университете и сталкиваюсь с некоторыми проблемами. То, что я уже выяснил, это просто решение проблемы. Однако меня больше интересует способ мышления, то есть как получить такое решение.

Может кто-нибудь дать мне совет в этой области. Буду очень признателен за вашу помощь.

Я привожу пример, с которым я справляюсь, а также нашел здесь решение для stackru, но я ищу, как он это делает, как он находит ответ:)

Напишите предикат flatten(List,Flat), который сгладит список, например, flatten([a,b,[c,d],[[1,2]],foo],X) даст X=[a,b, в, г,1,2, Foo].

Это ответ, который я нашел на stackru:

flatten(List, Flattened):-
   flatten(List, [], Flattened).

flatten([], Flattened, Flattened).
flatten([Item|Tail], L, Flattened):-
  flatten(Item, L1, Flattened),
  flatten(Tail, L, L1).
flatten(Item, Flattened, [Item|Flattened]):-
  \+ is_list(Item).

этот ответ принадлежит пользователю gusbro и задан пользователем Parhs. Я попытался найти способ связаться с пользователем gusbro, чтобы спросить его, как он может получить такой ответ, но я не могу.

Большое спасибо.

Answer 1

Ну, все, что я могу сказать, это то, что способ решения проблемы во многом зависит от самой проблемы. Существует ряд проблем, которые можно решить с помощью рекурсии, где Prolog хорошо подходит для их решения.

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

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

Другой класс - это "рекурсивные случаи", где мы разбиваем входные данные на части, решаем их отдельно, а затем "объединяем" результаты, чтобы найти решение для этого более крупного ввода.

В примере для flatten/2 мы хотим взять в качестве входных данных список элементов, где каждый элемент также может быть списком, а результатом должен быть список, содержащий все элементы из входных данных. Поэтому мы разбиваем проблему на ее случаи. Мы будем использовать вспомогательный аргумент для хранения промежуточного уплощенного списка, и именно поэтому мы реализуем flatten/3.

Поэтому наш предикат flatten/2 просто вызовет flatten / 3, используя пустой список в качестве начального промежуточного плоского списка:

flatten(List, Flattened):-
   flatten(List, [], Flattened).

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

flatten([], Flattened, Flattened).

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

flatten([Item|Tail], L, Flattened):-
  flatten(Item, L1, Flattened),
  flatten(Tail, L, L1).

Итак, вызов flatten(Item, L1, Flatlined) выравнивает первый элемент, но передает в качестве промежуточного списка несвязанную переменную L1. Это всего лишь хитрость, так что при возврате предиката переменная L1 все еще остается неограниченной, и Flatlined будет иметь форму [...|L1], где... - сплющенные элементы Item.

Следующий шаг, который вызывает flatten(Tail, L, L1), выравнивает остальную часть входного списка, и результат ограничивается L1.

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

flatten(Item, Flattened, [Item|Flattened]):-
  \+ is_list(Item).

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

Answer 2

Сначала я покажу вам свой подход к проблеме, затем у меня появятся ресурсы для обучения рекурсивному мышлению.

Вот мое решение проблемы "сгладить список списков (списков...)". Я аннотировал это, чтобы показать, как я туда попал:

• Во-первых, давайте определим открытый интерфейс для нашего решения. Мы определяем flatten/2, Его тело состоит из вызова внутренней реализации flatten/3, которая принимает аккумулятор, который отображается как пустой список.

  flatten ( X , R ) :-
    flatten ( X , [] , R ) ,
    .
  

  Это было просто.

• Внутренний предикат flatten/3 немного сложнее, но не очень.

  • Во-первых, у нас есть граничное условие: пустой список. Это означает конец того, что нам нужно сделать, поэтому мы объединяем аккумулятор с результатом:

    flatten( [] , X , X ).
    

  • Следующий (и единственный) другой случай - непустой список. Для этого мы рассмотрим заголовок списка. Наше правило заключается в том, что его нужно сгладить и добавить к результату. Хорошим правилом программирования является написание описательного кода, а Пролог сам по себе является описательным, а не процедурным языком: один описывает решение проблемы и позволяет механизму логического вывода разобраться.

    Итак... давайте опишем, что должно произойти сейчас, и рассмотрим механизм выравнивания заголовка списка:

    flatten( [X|Xs] , T , Y ) :-
      flatten_head(X,X1)     ,
      append( T,X1,T1)       ,
      flatten( Xs , T1 , Y )
      .
    

    Это тоже было легко.

Это суть всего решения, прямо там. Мы разбили нашу проблему на 3 части:

• особый случай (пустой список)
• нормальный случай (непустой список)
• что делать с каждым элементом в списке (еще не определено).

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

• Во-первых, элемент списка может быть несвязанной переменной. Мы не хотим нежелательного поведения, такого как неограниченная рекурсия, поэтому давайте позаботимся об этом сразу, запретив не связанные термины (пока). Если элемент связан, мы пытаемся сгладить его, вызвав наш открытый интерфейс, flatten\2 снова (оооооооо... больше рекурсии!)

  Это выполняет две вещи

  • Во-первых, он говорит нам, есть ли у нас список или нет: flatten/2 терпит неудачу, если вручил что-то кроме списка.
  • Во-вторых, когда это удается, работа flatten_head/2 готово.

  
  Вот код:

  flatten-head( X , Y   ) :-     
    nonvar(X) ,
    flatten( X , Y )
    .
  

• Наконец, последний случай, который мы должны рассмотреть, это случай элементов списка, которые не являются списками (несвязанные переменные, атомы или какой-либо другой термин пролога). Они уже "плоские"... все, что нам нужно сделать, это обернуть их в один список элементов, чтобы вызывающийflatten\3) получает согласованную семантику для своего "возвращаемого значения":

  flatten-head( X , [X] ).
  

Вот полный код:

flatten ( X , R ) :-
  flatten ( X , [] , R )
  .

flatten( [] , X , X ) .
flatten( [X|Xs] , T , Y ) :-
  flatten_head(X,X1)      ,
  append( T,X1,T1)        ,
  flatten( Xs , T1 , Y )
  .

flatten-head( X , Y   ) :-
  nonvar(X)             ,
  flatten( X , Y )
  .
flatten-head( X , [X] ) .

Каждый отдельный шаг прост. Трудно определить кусочки и сплести их вместе (хотя иногда выяснить, как остановить рекурсию, может быть менее чем очевидно).

Некоторые учебные ресурсы

Чтобы понять рекурсию, вы должны сначала понять рекурсию - анонимно

Эрик Робертс " Мышление рекурсивно" (1986), вероятно, является лучшей (только?) Книгой, посвященной разработке рекурсивного программного обеспечения для разработки WRT с точки зрения. Есть обновленная версия Thur Recursively With Java, 20th Anniversary Edition (2006), хотя я ее не видел.

Обе книги, конечно, доступны в обычных местах: Пауэлл, Амазонка и т. Д.

• http://www.amazon.com/Thinking-Recursively-Eric-S-Roberts/dp/0471816523
• http://www.amazon.com/Thinking-Recursively-Java-Eric-Roberts/dp/0471701467
• http://www.powells.com/biblio/61-9780471816522-2
• http://www.powells.com/biblio/72-9780471701460-0

Вы также можете прочитать классическую книгу Дугласа Хофштадтлера " Гедель, Эшер, Бах: вечная золотая оплетка". Некоторые считают эту книгу лучшей из когда-либо написанных. YMMV.

Также доступный от Обычных Подозреваемых:

• http://www.powells.com/biblio/62-9780140289206-1
• http://www.amazon.com/Godel-Escher-Bach-Eternal-Golden/dp/0465026567

Майкл Корбаллис " Рекурсивный разум: истоки человеческого языка, мышления и цивилизации", хотя и не является прямой книгой о рекурсивной теории, но может быть полезен, хотя я и не видел ее (она получила хорошие отзывы).