Comments 2
Откаты на питоне, имхо, по-другому должны выглядеть.
Прежде всего, заметим, питон поддерживает монаду List из коробки. А на ней можно легко сделать всё остальное. Собственно, yield — оно самое.
Но начнём разбор полётов.
def test(st,pat):
if st=="" and pat=="": yield True
if pat>"" and pat[0]=='*':yield test(st,pat[1:])
if st>"" and pat>"":
if st[0]==pat[0] or pat[0]=='?': yield test(st[1:],pat[1:])
if pat[0]=='*':yield test(st[1:],pat)
yield False
Что здесь не так?
Функция возвращает генератор. yield test(...)
испускает не значение, а генератор значений, тогда как yield True
/ yield False
— испускает конечное значение.
Мы получили гетерогенную функцию, это неправильно.
Для гомогенности нужно использовать конструкцию yield from test(...)
, или, во втором питоне, её рукодельный эквивалент for x in test(...): yield x
(До кучи замечу, что проверка пустоты/непустоты строк — это тупо not s
/ bool(s)
, а не странное s>""
).
Однако, глупо делать монаду списка над монадой мейби. Список из одного значения — сам по себе отличное мейби. Чтобы сделать fail, достаточно выйти из генератора, не испустив вообще ничего. Тем более, что именно это соответствует поведению пролога.
def test(S,P):
if not S and not P:
yield True
# и пойдём дальше, хоть это и глупо.
# Но вдруг мы потом захотим сделать порождающие...
if S and P and S[0]==P[0]:
# звёздочки и вопросики тоже сожрали, а почему бы и нет.
yield from test(S[1:],P[1:])
if S and P and P[0]=='?':
yield from test(S[1:],P[1:])
if P and P[0]=='*':
yield from test(S,P[1:])
if S and P and P[0]=='*':
yield from test(S[1:],P)
# всё! ничего не вернём, если облом
def run_test(S,P):
# можно так
for t in test(S,P): return True # хоть одно значение получили, уже счастливы
return False
# можно так:
return any(test(S,P)) # хоть одно истинное значение (а там все будут такие)
# можно так:
return next(test(S,P), False) # первое значение либо False, если ничего
# можно так:
return next((True for t in test(S,P)), False) # эквивалент первого варианта с for
Что интересно, — поскольку мы мейби-ничего реализовали в монаде списка, то это список-ничего, — то есть, мы можем испускать не True, а произвольный мусор. Например, None.
Только в этом случае any(test...) и next(test...) перестанут работать корректно. Но next(True...) — в лучшем виде.
Или же, поскольку в нашей задаче исключительно концевая рекурсия, то можем нагородить чистое мейби-ничего, то есть, bool.
def test(S, P):
if not S and not P:
return True # других вариантов быть не может
elif P and P[0]=='?':
return S and test(S[1:],P[1:])
elif P and P[0]=='*':
return (S and test(S[1:],P)) or test(S,P[1:])
elif P:
return S[:1]==P[:1] and test(S[1:],P[1:])
Собирать списки внутри функции, чтоб потом взять самый первый элемент… Это энергичная (и поэтому крайне странная) версия монады списка.
Вообще, пролог довольно просто ложится поверх питона. Нельзя сказать, что мега-эффективно, но...
- конъюнкция выражений — это декартово произведение (генераторов) списков
- даже конструкции синтаксические для этого есть: вложенные for, в том числе, в генераторных выражениях
- дизъюнкция — это конкатенация
- отсечки — надо подумать… как поизящнее сделать; неизящно — это вот так примерно
# goal1(), ( goal2a(), !; goal2b() ) for _ in goal1(): for _ in goal2a(): yield True return # отсечка: взяли первое удачное решение goal2a и всё for _ in goal2b(): yield True .....
- позднее связывание переменных и выходные параметры — ну, завернуть каждое значение в одноклеточный мутабельный контейнер… с нужным набором операторов...
- списки — в питоне это массивы, и делать позднее связывание довольно трудно, поэтому придётся пожертвовать памятью и сделать настоящие конс-списки (впрочем, в сви-прологе строки и атомы тоже не списки, и для обработки их расшивают).
Хотя было бы интересно сделать тип данных "ленивый список с поздним связыванием фрагментов" поверх массива — в том случае, если стоит задача полноценно, а не ad hoc & just for fun эмулировать пролог на питоне.
это были попытки с неглубокими знаниями питона им пользоваться.
Тут демонстрация нацелена на переход от поиска в глубину на поиск в ширину — это и дало эффект. Правда в Прологе это теряет его «универсальность» обход в ширину уже просто не сгенерирует цепочек.
Мой «инженерный» подход еще не почувствовал пользы монад, все пытаюсь найти их в знакомом Лиспе, но почему-то абстракции Хаскела на других теориях,
спасибо, буду вникать…
Занимательный пролог #2