Вывести строку из списка в Haskell

Question

Я хотел бы проанализировать строку в списке в Haskell, но я понятия не имею, как ее правильно записать. Строка структура:

A [B [], C [D [], E []]] 

и представляет собой структуру

A-+-B 
    | 
    `-C-+-D 
     | 
     `-E 

и идеи? Спасибо!

Answer 1

Ваш лучший выбор, когда парсинг в Haskell почти всегда Parsec. Вот пример.

import Text.ParserCombinators.Parsec 

data Tree a = Tree [Tree a] | Leaf a deriving Show 

parseLeaf :: Parser (Tree Char) 
parseLeaf = noneOf "[]" >>= return.Leaf 

parseNode :: Parser (Tree Char) 
parseNode = do 
    char '[' 
    a <- parseTree 
    char ']' 
    return (Tree a) 

parseTree = many1 (parseLeaf <|> parseNode) 

Тестирование это:

> parseTest parseTree "a[aa]" 
[Leaf 'a',Tree [Leaf 'a',Leaf 'a']] 
> parseTest parseTree "a[aa]aaa" 
[Leaf 'a',Tree [Leaf 'a',Leaf 'a'],Leaf 'a',Leaf 'a',Leaf 'a'] 
> parseTest parseTree "a[aa[aaaaaa]]aaa" 
[Leaf 'a',Tree [Leaf 'a',Leaf 'a',Tree [Leaf 'a',Leaf 'a',Leaf 'a',Leaf 'a',Leaf 'a',Leaf 'a']],Leaf 'a',Leaf 'a',Leaf 'a'] 

Вот как это работает. Парсеры в Parsec являются монадическими и поддерживают обычную нотацию. (Вы можете написать парсеры applicatively, а также, вы можете посмотреть, как сделать это в другом месте.)

Мы начнем с простой структурой данных

data Tree a = Tree [Tree a] | Leaf a deriving Show 

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

Затем нам нужен парсер для каждой возможной части дерева. Лист довольно просто, это просто что-то, что не является кронштейн:

parseLeaf :: Parser (Tree Char) 
parseLeaf = noneOf "[]" >>= return.Leaf 

Обратите внимание, что это могло быть написано в обычном письме, как

parseLeaf = do 
    a <- noneOf "[]" 
    return (Leaf a) 

Затем разобрать разветвление часть из дерева, нам нужно разобрать открывающие и закрывающие скобки. В промежутке между скобками снова может быть цельное дерево.

parseNode :: Parser (Tree Char) 
parseNode = do 
    char '[' 
    a <- parseTree 
    char ']' 
    return (Tree a) 

И что такое parseTree? Это просто многие из парсеров, которые мы написали. Оператор <|> позволяет синтаксическому анализатору выбирать синтаксический анализатор, в зависимости от того, какой из параметров сначала выполняется правильно. Таким образом, у нас есть

parseTree = many1 (parseLeaf <|> parseNode) 

Вы должны уметь адаптировать это для своих целей. Похоже, что ваша структура может быть несколько больше, как это:

data Structure a = Node (Structure a) a a | Leaf a 

Следуя те же принципы, работая, что анализатор необходим для каждой возможности, а затем объединить их, вы должны быть разбор в кратчайших сроках.

UPDATE

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

data Tree = Tree Char [Tree] deriving Show 

parseTree :: Parser Tree 
parseTree = do 
    character <- noneOf "[]" 
    subtree <- parseSubTree 
    return $ Tree character subtree 

parseSubTree :: Parser [Tree] 
parseSubTree = do 
    char '[' 
    trees <- many parseTree 
    char ']' 
    return trees 

И вот версия с запятыми и пробелами, добавленными довольно простым способом.В библиотеке парсеков есть много полезных комбинаторов, которые могли бы упростить и улучшить это, вы должны сами исследовать их. Обратите внимание также на аппликативный стиль, используемый для определения парсера ярлыков symbol. Многие люди предпочитают аппликативный стиль для парсеров, и это может быть намного более кратким, так что об этом тоже стоит узнать.

data Tree = Tree Char [Tree] deriving Show 

symbol :: String -> Parser String 
symbol s = string s <* spaces 

parseTree :: Parser Tree 
parseTree = do 
    character <- noneOf "[]" 
    spaces 
    subtree <- parseSubTree 
    return $ Tree character subtree 

parseSubTree :: Parser [Tree] 
parseSubTree = do 
    symbol "[" 
    trees <- sepBy parseTree (symbol ",") 
    symbol "]" 
    return trees 

Здесь работает:

> parseTest parseTree "A [ A [ B [ ] , C [ ], D [ ] ] ] " 
Tree 'A' [Tree 'A' [Tree 'B' [],Tree 'C' [],Tree 'D' []]]