木
おそらくツリーを使用してデータを格納する必要があるというあなたの意見は正しかったです。私はData.Treeそれがどのように行うかをコピーします：
data Tree a = Node a (Forest a) deriving (Show)
type Forest a = [Tree a]
ツリーの構築
ここで、弱く型付けされたタプルのリストを取得して、(わずかに) 強いsTreeに変換します。String弱く型付けされた値を変換し、より強力な型に変換する前に検証する必要がある場合はいつでも、次を使用しますParser。
type YourData = [(Int, [String])]
type Parser a = YourData -> Maybe (a, YourData)
YourData型シノニムは、解析している弱い型を表します。型変数は、a解析から取得する値です。が失敗する可能性があるため、このParser型は a を返します。理由を確認するために、次の入力は、ツリーのレベル 1 がないため、有効な に対応していません。MaybeParserTree
[(0, ["val1"]), (2, ["val2"])]
Parser が成功した場合は、未使用の入力も返されるため、後続の解析段階で使用できます。
さて、不思議なことに、上記のParser型はよく知られているモナド変換スタックと完全に一致します:
StateT s Maybe a
の基礎となる実装StateTを展開すると、これを見ることができます。
StateT s Maybe a ~ s -> Maybe (a, s)
これは、次のように定義できることを意味します。
import Control.Monad.Trans.State.Strict
type Parser a = StateT [(Int, [String])] Maybe a
これを行うと、型のMonad,ApplicativeおよびAlternativeインスタンスParserが無料で取得されます。これにより、パーサーの定義が非常に簡単になります!
まず、ツリーの 1 つのノードを消費するプリミティブ パーサーを定義する必要があります。
parseElement :: Int -> Parser String
parseElement level = StateT $ \list -> case list of
[] -> Nothing
(level', strs):rest -> case strs of
[str] ->
if (level' == level)
then Just (str, rest)
else Nothing
_ -> Nothing
これは、私たちが書かなければならない唯一の重要なコードです。これは合計であるため、次のすべてのコーナーケースを処理します。
- リストが空です
- ノードには複数の値があります
- タプルの数値が予想される深度と一致しません
次の部分は、物事が本当にエレガントになるところです。次に、相互に再帰的な 2 つのパーサーを定義できます。1 つは a を解析するためのもので、もう 1 つは aTreeを解析するためのものForestです。
import Control.Applicative
parseTree :: Int -> Parser (Tree String)
parseTree level = Node <$> parseElement level <*> parseForest (level + 1)
parseForest :: Int -> Parser (Forest String)
parseForest level = many (parseTree level)
最初のパーサーはApplicativeスタイルを使用します。インスタンスを無料で提供しStateTてくれるからです。Applicativeただし、代わりにStateT'sMonadインスタンスを使用して、命令型プログラマーにとってより読みやすいコードを提供することもできます。
parseTree :: Int -> Parser (Tree String)
parseTree level = do
str <- parseElement level
forest <- parseForest (level + 1)
return $ Node str forest
しかし、many機能はどうですか？あれは何をしているの？そのタイプを見てみましょう：
many :: (Alternative f) => f a -> f [a]
値を返すものは何でも取り、実装Applicativeし、代わりにそれを繰り返し呼び出して、代わりに値のリストを返します。Parserの観点から型を定義したとき、無料でインスタンスStateを取得したため、この関数を使用して、単一を解析するもの(つまり ) を解析するもの(つまり)に変換できます。AlternativemanyTreeparseTreeForestparseForest
を使用するParserには、目的を明確にするために既存のStateT関数の名前を変更するだけです。
runParser :: パーサー a -> [(Int, [String])] -> おそらく a runParser = evalStateT
あとは実行するだけです！
>>> runParser (parseForest 0) [(0,["day 1"]),(1,["Person 1"]),(2,["Bill 1"]),(1,["Person 2"]),(2,["Bill 2"])]
Just [Node "day 1" [Node "Person 1" [Node "Bill 1" []],Node "Person 2" [Node "Bill 2" []]]]
それはただの魔法です！無効な入力を与えるとどうなるか見てみましょう:
>>> runParser (parseForest 0) [(0, ["val1"]), (2, ["val2"])]
Just [Node "val1" []]
入力の一部で成功します! 実際には、入力の最後に一致するパーサーを定義することで、入力全体を消費する必要があることを指定できます。
eof :: Parser ()
eof = StateT $ \list -> case list of
[] -> Just ((), [])
_ -> Nothing
それでは試してみましょう：
>>> runParser (parseForest 0 >> eof) [(0, ["val1"]), (2, ["val2"])]
Nothing
完全！
ツリーの平坦化
2 番目の質問に答えるために、相互再帰関数を使用して問題を解決します。
flattenForest :: Forest a -> [[a]]
flattenForest forest = concatMap flattenTree forest
flattenTree :: Tree a -> [[a]]
flattenTree (Node a forest) = case forest of
[] -> [[a]]
_ -> map (a:) (flattenForest forest)
試してみよう！
>>> flattenForest [Node "day 1" [Node "Person 1" [Node "Bill 1" []],Node "Person 2" [Node "Bill 2" []]]]
[["day 1","Person 1","Bill 1"],["day 1","Person 2","Bill 2"]]
さて、技術的には、相互再帰関数を使用する必要はありませんでした。単一の再帰関数を実行できたはずです。Treeの型の定義に従っていただけですData.Tree。
結論
Treeしたがって、理論的には、中間型をスキップしてフラット化された結果を直接解析するだけで、コードをさらに短縮できたはずですがTree、他の目的で に基づく表現を使用することをお勧めします。
これからの重要なポイントは次のとおりです。
- Haskell の抽象化を学んでコードを簡素化する
- 常に合計関数を書く
- 再帰を効果的に使用する方法を学ぶ
これらを実行すると、問題に正確に一致する堅牢でエレガントなコードを記述できます。
付録
私が言ったことをすべて組み込んだ最終的なコードは次のとおりです。
import Control.Applicative
import Control.Monad.Trans.State.Strict
import Data.Tree
type YourType = [(Int, [String])]
type Parser a = StateT [(Int, [String])] Maybe a
runParser :: Parser a -> [(Int, [String])] -> Maybe a
runParser = evalStateT
parseElement :: Int -> Parser String
parseElement level = StateT $ \list -> case list of
[] -> Nothing
(level', strs):rest -> case strs of
[str] ->
if (level' == level)
then Just (str, rest)
else Nothing
_ -> Nothing
parseTree :: Int -> Parser (Tree String)
parseTree level = Node <$> parseElement level <*> parseForest (level + 1)
parseForest :: Int -> Parser (Forest String)
parseForest level = many (parseTree level)
eof :: Parser ()
eof = StateT $ \list -> case list of
[] -> Just ((), [])
_ -> Nothing
flattenForest :: Forest a -> [[a]]
flattenForest forest = concatMap flattenTree forest
flattenTree :: Tree a -> [[a]]
flattenTree (Node a forest) = case forest of
[] -> [[a]]
_ -> map (a:) (flattenForest forest)