Как рекурсивно распарсить скобки?

Question

[Даниил Колесниченко]

Пытаюсь разложить строку вида "(+ 12 (* 3 4))" на список лексем вида ["(", "+", "12", "(", "*", "3", "4", ")", ")"]
Написал что-то на Haskell:

import Data.Char
import Data.List.Split
import Data.Maybe
import Text.Read

sep :: String -> [String]
sep s = concat $ map sepBr (splitOn " " s) where
    sepBr :: String -> [String]
    sepBr ""  = []
    sepBr " " = []
    sepBr (x:xs)
        | x `elem` ['(', ')'] = ([x] : sepBr xs)
        | otherwise           = ([x] : [xs])

Работает почти правильно :)
Вместо ожидаемого результата возвращает ["(","+","","1","2","(","*","","3","","4","))"]. Пустые строки можно было бы вычистить с помощью filter, а вот что делать со склеившимися скобочками и расклеившимся числом не знаю.

P. S. Только начинаю пытаться осилить фп, haskell, рекурсию и всё вот это, пока путаюсь ещё, тапками сильно не кидайтесь)

UPD:
Вот вроде переписал, по идее должно работать, а он на типы ругается:

import           Data.Char
import           Data.List.Split
import           Data.Maybe
import           Text.Read


sep :: String -> [String]
sep s = concat $ map sepBr (splitOn " " s) where
    sepBr :: String -> [String]
    sepBr ""  = []
    sepBr " " = []
    sepBr word
        | a `elem` brackets = [[a]] ++ sepBr bc
        | c `elem` brackets = sepBr ab ++ [[c]]
        | otherwise         = ([a : bc])
        where a        = if word == [] then [] else head word
              b        = if word == [] then [] else init $ tail word
              c        = if word == [] then [] else last word
              ab       = [a] ++ b
              bc       = b ++ [c]
              brackets = ['(', ')']

Ошибка:

src/Main.hs@13:20-13:28 Couldn't match type Char with [t1]
Expected type: [[t1]]
  Actual type: [Char] …
src/Main.hs@13:33-13:34 Couldn't match expected type Char with actual type [t2] …
src/Main.hs@14:20-14:28 Couldn't match type Char with [t3]
Expected type: [[t3]]
  Actual type: [Char] …
src/Main.hs@14:37-14:39 Couldn't match type [t4] with Char
Expected type: String
  Actual type: [[t4]] …
src/Main.hs@14:45-14:46 Couldn't match expected type Char with actual type [t5] …
src/Main.hs@15:33-15:34 Couldn't match expected type Char with actual type [t6] …
src/Main.hs@16:58-16:62 Couldn't match type Char with [t]
Expected type: [[t]]
  Actual type: String
Relevant bindings include
  a :: [t]
    (bound at /home/app/isolation-runner-work/projects/119295/session.207/src/src/Main.hs:16:15) …
src/Main.hs@18:58-18:62 Couldn't match type Char with [t]
Expected type: [[t]]
  Actual type: String
Relevant bindings include
  c :: [t]
    (bound at /home/app/isolation-runner-work/projects/119295/session.207/src/src/Main.hs:18:15) …
src/Main.hs@19:33-19:34 Couldn't match type Char with [t]
Expected type: [[t]]
  Actual type: [Char]
Relevant bindings include
  ab :: [[t]]
    (bound at /home/app/isolation-runner-work/projects/119295/session.207/src/src/Main.hs:19:15) …
src/Main.hs@20:32-20:33 Couldn't match expected type Char with actual type [t0] …

Не понимаю, откуда берётся [[t]], если тип функции last :: [a] -> a. То же и с остальными функциями, почему a не может быть символом (Char)?

Answer 1

[Александр Ручкин]

Во-первых, заменим splitOn " " на words, который съест все пробелы. Далее, concat $ map ... - это то же, что и concatMap .... Рассмотрим sepBr. Он берёт строку без пробелов и делит её на куски, если там есть операторы, числа или скобки. Если строка уже пустая, результат - пустой список. Если строка непустая, то возможны варианты. Если первый её символ - какая-то скобка, отделяем эту скобку, а остальное делим опять при помощи sepBr. Иначе делаем так: разделим строку, чтобы сначала шли только цифры: span isDigit и посмотрим, что получилось. Если цифры есть - отделяем их, а остальное опять делим sepBr. Если цифр нет, то просто отделяем первый символ. Вот, что получилось:

sep ∷ String → [String]
sep = concatMap sepBr . words where
	sepBr ∷ String → [String]
	sepBr "" = [] -- нечего делить
	sepBr s'@(x:xs)
		| x `elem` "()" = [x] : sepBr xs -- скобка
		| otherwise = case span isDigit s' of -- возьмём цифры
			("", t:tl) → [t] : sepBr tl -- нет цифр, берём первый символ остатка
			(n, tl) → n : sepBr tl -- есть цифры, их отдельно

По поводу вашего второго варианта.
if word == [] then [] else head word - т.е. a либо пустой список, либо символ, типы не совпадают. Но в вашем случае word не может быть пустым, ведь выше уже был паттерн sepBr "", так что можно просто оставить a = head word
Далее, что такое ab? Это [a] ++ b, т.е. [head word] ++ init (tail word), т.е. это то же, что и просто init word. Аналогично bc = tail word. Вместо того, чтобы брать отдельно head и отдельно tail, можно воспользоваться паттерн-матчингом и записать (a : bc) = word.
С учётом этого ваш вариант переписывается в

sep2 ∷ String → [String]
sep2 = concatMap sepBr . words where
	sepBr ∷ String → [String]
	sepBr ""  = []
	sepBr " " = []
	sepBr word
		| a `elem` brackets = [[a]] ++ sepBr bc
		| c `elem` brackets = sepBr ab ++ [[c]]
		| otherwise = ([a : bc])
		where
			(a : bc) = word
			c = last word
			ab = init word
			brackets = ['(', ')']

И он вполне работает.

Comments

[Даниил Колесниченко]

Спасибо огромное, великолепное объяснение :)

Answer 2

[art_of_press]

Вы, почему-то, не используете одну из самых мощных фич Хаскелла - типы. Программа гораздо легче пишется, когда вы её сначала написали на уровне типов. Функции после этого пишутся гораздо легче.

Переходя к вашей задаче: я бы разделил её на два этапа.

1. Лексический разбор строки на список токенов.

2. Парсинг списка токенов в выражение.

Какие у вас могут быть токены? Числа, операторы, левая и правая скобки. Вот их и кодируйте в типе Token:

data Token = NumToken Double | OpToken Operator | LeftParenToken | RightParenToken

data Operator = Plus | Minus | Mult | Div

В типе Token конструктору данных NumToken я передал Double, т.к. если у вас будет деление, с Int или Integer вы не сможете его произвести без дополнительной конвертации.

Дальше вы должны превратить вашу строку в список токенов. Это отлично делается рекурсией:

strToToken :: String -> [Token]
strToToken [] = []
strToToken (c:cs)
    -- Токенизируем голову списка и вызываем токенизацию на его хвосте
    | c == '(' = LeftParenToken : strToToken cs
    | c == ')' = RightParenToken : strToToken cs
    -- Если встречается пробел - откидываем его и токенизируем строку дальше
    | isSpace c = strToToken cs
    -- если встречается число, вызываем функцию-хелпер number
    | isDigit c = number c cs
    -- не забываем о случаях, когда строку не удалось распарсить полностью
    | otherwise = error $ "Не могу распарсить " ++ [c]

Функция strToToken и вспомогательная функция number являются взаимно рекурсивными. Из функции strToToken мы вызываем функцию number, а из функции number мы вызываем функцию strToToken:

number :: Char -> String -> [Token]
number c cs =
    -- разбиваем строку на цифровые символы, идущие друг за другом, 
    -- и на остаток строки при помощи функции span
    let (digits,rest) = span isDigit cs
    -- сразу переводим полученные цифровые символы в число 
    -- при помощи функции read и токенизируем остаток строки
    in NumToken (read $ c:digits) : strToToken rest

Вот вы и сконвертировали строку в список лексем. Следующая задача - парсинг лексем в выражения. Советую точно так же создать тип, содержащий все возможные выражения. Подсказка: этот тип у вас получится рекурсивным, т.к. выражение может состоять из нескольких выражений, разделённых операторами.

Comments

[Даниил Колесниченко]

Когда я вопрос задавал (а это было в июне), я только начинал пробовать осилить Haskell. Типы нормально не использовал, потому что в качестве первого нехелловорлда я выбрал переписывание кода, написанного ранее на коленке на Python, а там алгебраических типов и вообще статической типизации нет. Так что и переписал я почти так же, как писал на Python, только без циклов.
Сейчас я так уже не пишу :)

[art_of_press]

Это понятно, что для вас, скорее всего, этот ответ уже не актуален, однако его могут увидеть и другие. А я часто замечаю, что начинающие изучать Хаскель осваивают синтаксис и концентрируются именно на нём, игнорируя такой мощный инструмент, как типы, с которого и надо начинать строить каркас программы.