在Haskell中将分层数据结构转换为平面数据结构

Question

我正在从如下组织的文本文档中提取一些数据:

- "day 1"
    - "Person 1"
        - "Bill 1"
    - "Person 2"
        - "Bill 2"

我可以将其读入一个看起来像这样的元组列表:

[(0,["day 1"]),(1,["Person 1"]),(2,["Bill 1"]),(1,["Person 2"]),(2,["Bill 2"])]

每个元组的第一项表示标题级别,第二项表示与每个标题相关的信息.

我的问题是,如何获得如下所示的项目列表:

[["day 1","Person 1","Bill 1"],["day 1","Person 2","Bill 2"]]

即每个最深嵌套项目的一个列表,包含来自其上方标题的所有信息.我得到的最接近的是:

f [] = []
f (x:xs) = row:f rest where
leaves = takeWhile (\i -> fst i > fst x) xs
rest = dropWhile (\i -> fst i > fst x) xs
row = concat $ map (\i -> (snd x):[snd i]) leaves

这给了我这个:

[[["day 1"],["Intro 1"],["day 1"],["Bill 1"],["day 1"],["Intro 2"],["day 1"],["Bill 2"]]]

我希望该解决方案能够适用于任何级别.

Ps我是Haskell的新手.我有一种感觉,我可以/应该使用树来存储数据,但我无法绕过它.我也想不出一个更好的头衔.

Answer 1

树

你是对的,你应该使用树来存储数据.我会复制Data.Tree它是怎么回事:

data Tree a = Node a (Forest a) deriving (Show)

type Forest a = [Tree a]

建树

现在我们想要获取弱类型的元组列表并将其转换为(略微)更强Tree的Strings.任何时候您需要转换弱类型值并在转换为更强类型之前验证它,您使用Parser:

type YourData = [(Int, [String])]

type Parser a = YourData -> Maybe (a, YourData)

该YourData类型的同义词代表您解析弱类型.该a类型的变量是你从剖析检索值.我们的Parser类型返回a Maybe因为Parser可能会失败.要查看原因,以下输入不对应有效Tree,因为它缺少树的第1级:

[(0, ["val1"]), (2, ["val2"])]

如果Parser 确实成功,它还会返回未使用的输入,以便后续的解析阶段可以使用它.

现在,奇怪的是,上述Parser类型与众所周知的monad变换器堆栈完全匹配:

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类型是免费的.这使得定义解析器变得非常容易!

首先,我们必须定义一个使用树的单个节点的原始解析器:

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

这是我们必须编写的唯一非常重要的代码片段,因为它是total,它处理以下所有角落情况:

• 该列表为空
• 您的节点中有多个值
• 元组中的数字与预期深度不匹配

接下来的部分是事情变得非常优雅.然后我们可以定义两个相互递归的解析器,一个用于解析a Tree,另一个用于解析a 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的Monad实例,而不是,给代码是为命令式编程更易读:

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,我们获得了一个Alternative免费的实例,因此我们可以使用该many函数将解析单个Tree(即parseTree)的内容转换为解析Forest(即parseForest)的内容.

要使用我们的Parser,我们只需重命名现有StateT函数以明确其目的:

runParser :: Parser a - > [(Int,[String])] - >也许是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

完善!

展平树

要回答第二个问题,我们再次使用相互递归函数解决问题:

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)