Haskell проверка вложенных данных

Question

Я новичок в Haskell, и мне нужно проверить, содержит ли регулярное выражение Empty. Некоторые из условий я уже определил, но я не знаю, что делать, если регулярное выражение вложено, как в приведенном ниже примере «test». Если я запустил isEmpty test, он вернет False, поскольку ни один из указанных выше случаев не является True. Но поскольку он содержит оператор «Star», он также должен содержать «Empty». Я предполагаю, что потребуется некоторая рекурсивная проверка выражения, но на данный момент я не знаю, как go об этом. Буду признателен за любую помощь.

data RegExpr = Empty | Symbol Char | Star RegExpr | And RegExpr RegExpr | Or RegExpr RegExpr

isEmpty (Empty) = True
isEmpty (Star Empty) = True
isEmpty (Or _ Empty) = True
isEmpty (Or Empty _) = True
isEmpty (And Empty Empty) = True
isEmpty _ = False

test = Or (Symbol 'a') (Star (And (Symbol 'a') (Symbol 'a')))

Answer 1

Вы совершенно правы: эту задачу нужно решать рекурсивно. Фактически, вы должны иметь возможность писать isEmpty, используя одну строку для каждого конструктора (то есть 5 строк для каждого из Empty, Symbol, Star, And и Or) с рекурсивными вызовами обычно используется везде, где в определении конструктора появляется RegExpr. Таким образом, строка, обрабатывающая Symbol, не будет рекурсивной, но строка для Or будет включать два рекурсивных вызова.

Ключ не должен совпадать со значениями c в подвыражениях из, скажем, конструктора Or. То есть вместо того, чтобы пытаться сопоставить Or _ Empty и всевозможные другие варианты Or, используйте общее сопоставление Or, которое связывает две альтернативы с подвыражениями, а затем рекурсивно работайте с этими подвыражениями. Например, с такой строкой, как:

isEmpty (Or r1 r2) = ... isEmpty r1 ... isEmpty r2 ...

, вы рекурсивно получите доступный результат isEmpty r1, который сообщает вам, может ли r1 соответствовать пустому входу, и аналогично результат isEmpty r2, который сообщает вам, может ли r2 соответствовать пустому вводу.

Каждая строка должна быть Haskell переводом логического оператора о связанном конструкторе, где isEmpty r означает, что регулярное выражение r может соответствовать пустой строке. Итак, когда у нас будет isEmpty (Or r1 r2) (т.е. когда Or r1 r2 соответствует пустой строке)? Ну, это точно, когда либо isEmpty r1, либо isEmpty r2, а определение - это просто Haskell перевод этого logi c:

-- `Or` matches empty if either alternative matches empty
isEmpty (Or r1 r2) = isEmpty r1 || isEmpty r2