Проблемы с рекурсией в Haskell

Question

У меня есть эта функция compile, которая должна взять строку, а затем дать выражение.

Это как Expression было определено:

data Expression = Name Char | Lambda Char Expression | Apply Expression Expression 
     deriving Show 

Допустим, что строка, что функция «компилировать» занимает:

"\\x.\\y.yx" 

Так, в конце функция compile предполагается это окончательное выражение:

Lambda 'x' (Lambda 'y' (Name 'y') (Name 'x')) 

Это является compile функция:

compile :: [Char] -> Expression 
compile (x:xs) = if [x] == "\\" then Lambda (head xs) (compile (tail xs)) 
        else if [x] == "." then compile xs 
        else if null xs then Name x 
        else Name x 

В настоящее время эта функция устраняет последнюю часть выражения ((Name 'x')). Я задал вопрос:

Как эта функция может продолжать двигаться дальше с более Name s, если один раз я получу Name Я не могу продолжать переходить к той же функции с остальной частью выражения? Так как Expression был определен таким образом, если Expression является Name, он просто имеет Name и не более, на нем не осталось никакого выражения.

Я имею в виду, как я могу взять каждый Name что в Expression, «говоря» Haskell, что я хочу, чтобы продолжать поиски Name с и не только остановить, когда один Name найден.

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

Как это сделать?

Answer 1

Непосредственно использование рекурсии на String для синтаксического анализа, хотя выполнимо, сложно. В языке лямбда-исчисления, например, для обработки (вложенных) скобок требуется некоторая осторожность.

Если вы хотите попробовать, по крайней мере, вам следует изучить, как работает LL parsers: как написать грамматику LL, как обрабатывать символ взгляда, а также основы теории формального языка в целом.

Если вы предпочитаете изучать эти «делания», попробуйте поиграть с библиотекой синтаксического анализатора, например Parsec.

В качестве незначительного предложения: в то время как большинство статей об исчислении лямбда используют только однобуквенные переменные и, например, записывают, например, «xy» для приложения, в реализации вам действительно нужны более длинные имена для переменных, даже если это происходит за счет потребности в пространствах между применяемыми терминами (например, «x y»). Это делает парсер немного сложнее писать, но стоит усилий.