Pull to refresh

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 эмулировать пролог на питоне.
Браво,
это были попытки с неглубокими знаниями питона им пользоваться.

Тут демонстрация нацелена на переход от поиска в глубину на поиск в ширину — это и дало эффект. Правда в Прологе это теряет его «универсальность» обход в ширину уже просто не сгенерирует цепочек.

Мой «инженерный» подход еще не почувствовал пользы монад, все пытаюсь найти их в знакомом Лиспе, но почему-то абстракции Хаскела на других теориях,
спасибо, буду вникать…
Sign up to leave a comment.

Articles