Комментарии 34
a*b*c*d на строках вида aabbccbbccdd
на такой реализации получаем одну ошибку
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
То есть в обычном языке программирования всегда можно решить задачу разными способами — более простыми, более сложными — в зависимости от навыков программиста.
А в декларативном он будет всегда одинаков, и при этом нужно знать практически все нюансы спецификации языка программирования.
Вот этот «предикат»:
isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!,
test_pattrn(SL,PL),!.На самом деле является эмуляцией императивного программирования на декларативном языке программирования.
Предикаты нужно воспринимать так:
строка соответствует шаблону если строку можно превратить в список атомов и шаблон можно превратить в список атомов и список из строки соответствует правилу соответствия шаблону
Тут речь не про порядок, а коммутативность операции И.
Ответить могу цитатой из известной книги Братко И.:
Но, к сожалению,
декларативный подход не всегда позволяет решить все задачи. По мере дальнейшего
изучения материала этой книги станет очевидно, что процедурные аспекты не могут
полностью игнорироваться программистом по практическим причинам, связанным с
обеспечением вычислительной эффективности, особенно при разработке больших
программ. Тем не менее необходимо стимулировать декларативный стиль мышления
при разработке программ Prolog и игнорировать процедурные аспекты до такой степени,
которая является допустимой с точки зрения практических ограничений.
Отвечу цитатой из книги Ф. Брукса:
Почему заниматься программированием интересно? Какими радостями вознаграждаются те, кто им занимается? Во-первых, это просто радость, получаемая при создании чего-либо своими руками. Как ребенок радуется, делая куличики из песка, так и взрослый получает удовольствие, создавая какие-либо вещи, особенно если сам их и придумал. Я думаю, что этот восторг — отражение восторга Господа, творящего мир, восторга, проявляющегося в индивидуальности и новизне каждого листочка и каждой снежинки.
А не заклинит ли на паттернах вида **a?
%'*' 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).
Вот компилятор хаскелла эти свёртки функций сделал бы на раз! Потому что это важное направление оптимизации.
Но хаскелл сам по себе не умеет в такое сопоставление с откатами, поэтому нужен не хаскелл, а карри. Но карри, кажется, сдох. Либо писать пролог-на-хаскелле (мейби + продолжения), а дальше пусть у компилятора голова болит. И не факт, что выболит...
Занимательный пролог