4

我正在从这样组织的文本文档中提取一些数据：

- "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的新手。我有一种感觉，我可以/应该使用一棵树来存储数据，但我无法绕过它。我也想不出更好的标题。

4

2 回答 2

5

树木

你是对的，你应该使用树来存储数据。我将复制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类型返回 aMaybe因为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

这是我们必须编写的唯一一段重要的代码，因为它是完整的，它可以处理以下所有极端情况：

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

下一部分是事情变得非常优雅的地方。然后我们可以定义两个相互递归的解析器，一个用于解析 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(ie parseTree) 的内容转换为解析 a Forest(ie 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)
于 2012-10-21T19:51:26.877 回答
3

我似乎已经解决了。

group :: [(Integer, [String])] -> [[String]]
group ((n, str):ls) = let
      (children, rest) = span (\(m, _) -> m > n) ls
      subgroups = map (str ++) $ group children
   in if null children then [str] ++ group rest
      else subgroups ++ group rest
group [] = []

虽然我没有测试太多。

这个想法是要注意递归模式。此函数获取列表的第一个元素 (N, S)，然后将更高级别的所有条目收集到级别 N 的另一个元素，到列表“子项”中。如果没有孩子，我们就在顶层，S 形成输出。如果有一些，则将 S 附加到所有这些。

至于为什么你的算法不起作用，问题主要在row. 请注意，您不是递归下降。

树也可以用。

data Tree a = Node a [Tree a] deriving Show

listToTree :: [(Integer, [String])] -> [Tree [String]]
listToTree ((n, str):ls) = let
      (children, rest) = span (\(m, _) -> m > n) ls
      subtrees = listToTree children
   in Node str subtrees : listToTree rest
listToTree [] = []

treeToList :: [Tree [String]] -> [[String]]
treeToList (Node s ns:ts) = children ++ treeToList ts where
   children = if null ns then [s] else map (s++) (treeToList ns)
treeToList [] = []

算法本质上是一样的。前半部分用于第一个功能，后半部分用于第二个功能。

于 2012-10-21T17:15:11.890 回答