Comments 34
Подозреваю, что будут проваливаться паттерны вида a*b*c*d на строках вида aabbccbbccdd
Очень рад, что кто-то напомнил, что есть такой замечательный язык Пролог… Сам-то я периодически пишу на нем — когда не очень понимаю задачу :).
Что касается вашей задачи — вот текст для swi-prolog
run(X,Y):-
  atom_chars(X,XX),
  atom_chars(Y,YY),
  !,match(XX,YY).
  
match([],[ * ]).
match([],[]).
match([H|T],[A|P]) :-
 (A = ? ; A = H), match(T,P).
match([H|T],[ * | P]):- match(T,[ * |P]); match(T,P).

Ну здесь run просто драйвер. Надеюсь, что правильно понял исходную задачу…
Спасибо, протестировал,
на такой реализации получаем одну ошибку
isMatch(aa, a)->ok
isMatch(aa, *)->ok
isMatch(cb, ?a)->ok
isMatch(adceb, *a*b)->failed:expected-true
isMatch(acdcb, a*c?b)->ok
isMatch(aab, c*a*b)->ok
isMatch(mississippi, m??*ss*?i*pi)->ok
isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok
isMatch(zacabz, *a?b*)->ok
isMatch(leetcode, *e*t?d*)->ok
isMatch(aaaa, ***a)->ok
isMatch(b, *?*?*)->ok
isMatch(aabbccbbccdd, a*b*c*d)->ok
true


Точно! у меня пропущен еще один вариант проверки:
match([H|T],[ * | P]):- match(T,[ * |P]);match([H|T],P); match(T,P).
выше я привел код предиката match — он дает false на вашем примере — это действительно так. К сожалению, у автора немного не верный предикат…
Тут надо смотреть тест, в нем проверка на false
:-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false).
А сообщение о правильном прохождении.
Да, не посмотрел… Тогда, по уму, надо делать так, чтобы выводило isNotMatch(...)->ok для таких случаев.
Ну, это был намек на unit testing ),
функции типа Assert.AreEqual(expected, actual)
тест зеленый — ok, иначе выведет сообщение…
Не считаю, что декларативность это противоположность императивности. Это альтернативные подходы. И основная проблема в том, что декларативность сперва должна быть запрограммирована императивностью.

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

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

Именно про это я говорил, когда имел ввиду «все нюансы».
Даже в вашем маленьком примере видно, что чисто декларативный подход не работает в реальном мире.
Вот этот «предикат»:
isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!,
    test_pattrn(SL,PL),!.

На самом деле является эмуляцией императивного программирования на декларативном языке программирования.

Предикаты нужно воспринимать так:
строка соответствует шаблону если строку можно превратить в список атомов и шаблон можно превратить в список атомов и список из строки соответствует правилу соответствия шаблону

В декларативном подходе порядок выполнения условий неважен, попробуйте поменять порядок выполнения условий в этом «предикате».

Тут речь не про порядок, а коммутативность операции И.
Ответить могу цитатой из известной книги Братко И.:


Но, к сожалению,
декларативный подход не всегда позволяет решить все задачи. По мере дальнейшего
изучения материала этой книги станет очевидно, что процедурные аспекты не могут
полностью игнорироваться программистом по практическим причинам, связанным с
обеспечением вычислительной эффективности, особенно при разработке больших
программ. Тем не менее необходимо стимулировать декларативный стиль мышления
при разработке программ Prolog и игнорировать процедурные аспекты до такой степени,
которая является допустимой с точки зрения практических ограничений.
имхо. что бы впечатлить кого то на хабре, надо привести пример какой то крутой системы которая на prolog написана, а приводить веселый пример людям которые в большинстве «ниасилили» декларативное программирование, это как то странно
это пример про занимательность решения задач, про удобство программирования на пролог, далее выбираем следующую задачу из leetcode.com и быстро решаем ))

Отвечу цитатой из книги Ф. Брукса:


Почему заниматься программированием интересно? Какими радостями вознаграждаются те, кто им занимается? Во-первых, это просто радость, получаемая при создании чего-либо своими руками. Как ребенок радуется, делая куличики из песка, так и взрослый получает удовольствие, создавая какие-либо вещи, особенно если сам их и придумал. Я думаю, что этот восторг — отражение восторга Господа, творящего мир, восторга, проявляющегося в индивидуальности и новизне каждого листочка и каждой снежинки.
Очень жаль, а то уже второй день бьюсь над задачкой.
Сейчас вот думаю, продолжать или нет.

А у вас собственно получилось или еще есть баги?
Я не знаю пролог, и потому не могу оценить ваше решение.

Пока не могу утверждать что все получилось,
к этой задаче 1800 тестов на сайте, откуда она взята.
Думаю написать продолжение, реализовать тоже на питоне, подставить решение и увидеть оставшиеся тесты, а потом уже подставить их в реализацию на Прологе, но это тема для новой войны статьи...

Нет, звездочка или отбросит один символ из входной строки или сама отбросится, вот тут:
%'*' Matches any sequence of characters (including the empty sequence).
test_pattrn([Ch|UnpTail],['*'|PatTail]):-  is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]).
test_pattrn(Str,['*'|PatTail]):-  test_pattrn(Str,PatTail).

В комментариях была ссылка на реализацию swish.swi-prolog.org/p/Wildcard%20Matching.pl

Заклинит — я имею в виду, на откатах.


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


В любом случае, обломавшись на последней звёздочке в серии звёздочек, откатываемся назад и повторяем все попытки заново. На одну звёздочку меньше, но по-прежнему со звёздочками.
(Но мы же уже знаем, что та попытка была неудачной?...)


Очевидный способ улучшить — это явно сокращать:


test_pattern(Chars, ['*','*'|Pattern]) :- test_pattern(Chars, ['*'|Pattern]).

или даже выполнить препроцессинг — выкинуть из образца все повторные звёздочки.

Да-да, удалять повторения звездочек это разумно,
в комментариях к продолжению статьи это появилось.
Как первое решение, тут показано простое понимание задачи, далее было эффективное решение…

Кстати, интересная встречная задачка: как написать универсальный предикат, способный не только проверять, но и порождать строки, соответствующие образцу.


Тут сложность в том, чтобы не зацикливаться и перебирать строки в более-менее приемлемом порядке.
Скажем, если у нас есть алфавит a,b,c,...,z, то test_pattern(S,['*']) может выдавать


  • [], [_1], [_1,_2], [_1,_2,_3],… — списки ещё несопоставленных значений
  • [], [a], [a,a], [a,a,a],… — сперва перебор всех строк из буквы "a", а потом… потом не будет, потому что это бесконечно
  • [], [a], [b], [c], ..., [z], [a,a], [a,b], ..., [a,z], [b,a], ..., [z,z], [a,a,a] ...

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


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

Схематично может выглядеть так:
проверку is_letter(X):-X@>=a, X@=<z.
наделим возможностью «генератора»:
is_letter(X):-member(X,[a,b,c,d, %%тут все буквы%%,z]).
%а далее можно вызывать
:-length(Str,66), test_pattrn(Str,'*a*b').

Это найдет все варианты списка указанной длины, например, 66.
length(Список, Длина) — возвратит список с неизвестными переменными значениями, это та же унификация, вход-выход почти не важен ))

Неее, ну если длину указывать, — это каждый сможет.
Либо можно сделать такой трюк: сперва генерировать списки всех размеров, а потом их матчить с образцом.
Типа такого


match_to_pattern(S,P) :- length(S,_), test_pattern(S,P).
pattern_to_match(S,P) :- length(P,_), test_pattern(S,P).

А вот чтобы и строки, и образцы генерировать консервативно… И при этом чтобы проверка была без лишних трат на перебор…
Понятно, что


match_both(S,P) :- length(S,_), length(P,_), test_pattern(S,P).

уйдёт в забег по образцам, подходящим для пустой строки, — это будут серии звёздочек до самого края вселенной.
Если переставить length местами, то наоборот: первым будет пустой образец и пустая строка, затем однобуквенные образцы и строки, затем одна звёздочка и дальше все строки на свете.

Даа,
если воспринимать генерацию цепочек/шаблонов как ответ на конкретную цель, типа проверка выдвинутой гипотезы, то бесконечность(все возможные) выглядит странно,
а вот так будет ниче:
match_both(S,P,High) :- length(S,LenS), LenS<High,length(P,LenP), LenP<High, test_pattern(S,P).

А как Хаскел может выразить генерацию и проверку одним выражением?
В Лиспе, Эрланге — не вижу способа.

Этот код — плох тем, что требует явно задавать величину отсечки.
А если добавить перебор по величине отсечек,


iota(N).
% порождает числа от 0 до бесконечности
% (ну или проверяет, является ли N неотрицательным)
% TODO: реализовать предикат, чтобы он работал быстро!

match_both(S,P) :- iota(Limit), match_both(S,P,Limit).

то мы получим сперва все ответы для #S<0, #P<0, (никакие)
затем все ответы для #S<1, #P<1, (единственный вариант — [], [])
затем все ответы для #S<2, #P<2, включая предыдущий,
затем все ответы для #S<3, #P<3, включая предыдущие, и т.д.


То есть, будут повторы.
Пролог не тот, чем он кажется ;)


Правильный способ — перебирать кортежи длин на грани симплекса или гранях гиперкуба.
Ну, применительно к двумерному пространству, — на диагоналях или сторонах квадрата.


% манхеттенская метрика
two_iotas_simplex(N1, N2) :-
  iota(Sum),
  between(0, Sum, N1), N2 is Sum - N1.

% чебышевская метрика
two_iotas_flat(N1, N2) :-
  iota(Max),
  between(0,Max,N1),
  ( N1 < Max, N2 is Max;
    N1 == Max, between(0,Max,N2) ). 

Кстати, для четвёрок (4 — достаточно большая размерность, чтобы увидеть регулярный подход), это будет выглядеть вот так


four_iotas_simplex(A,B,C,D) :-
    iota(SumABCD),
    between(0, SumABCD, A), SumBCD is SumABCD-A,
    between(0, SumBCD, B), SumCD is SumBCD-B,
    between(0, SumCD, C), SumD is SumCD-D,
    D is SumCD.

four_iotas_flat(A,B,C,D) :-
    iota(Max),
    between(0,Max,A),
    between(0,Max,B),
    between(0,Max,C),
    between(0,Max,D),
    ( A<Max, B<Max, C<Max, D is Max;
      not((A<Max, B<Max, C<Max)), between(0,Max,D) ).

Для произвольной размерности сами придумайте код :)


После чего


match_both(S, P) :- two_iotas(SL, PL), length(S,SL), length(P,PL), test_pattern(S,P).

Конечно, тут мы резко теряем эффективность, когда списки уже сформированы перед обращением.
В этом случае надо выполнить слияние арифметики над числами и арифметики над длинами, объединив три цели в одну.
Либо же сделать ветвление по var/nonvar (S) и (P).


Вот компилятор хаскелла эти свёртки функций сделал бы на раз! Потому что это важное направление оптимизации.
Но хаскелл сам по себе не умеет в такое сопоставление с откатами, поэтому нужен не хаскелл, а карри. Но карри, кажется, сдох. Либо писать пролог-на-хаскелле (мейби + продолжения), а дальше пусть у компилятора голова болит. И не факт, что выболит...

Only those users with full accounts are able to leave comments. Log in, please.