haskell - 嵌套序列到分支/树数据结构

我不确定这是否是一个容易解决的问题，只是我遗漏了一些明显的问题，但是一段时间以来，我一直在努力应对。我正在尝试使用列表表达树的分歧。这样一来，我可以轻松地使用简单的原语轻松地内联指定我的数据集，而不必担心顺序，并稍后从分散的列表集中构建树。

所以我有一些这样的清单:

 a = ["foo", "bar", "qux"]
 b = ["foo", "bar", "baz"]
 c = ["qux", "bar", "qux"]

我想要一个函数，它将采用这些列表的序列并像这样表达一棵树:

myfunc :: [[a]] -> MyTree a

(root) -> foo -> bar -> [baz, qux]
       -> qux -> bar -> qux

理想的解决方案将能够采用不同长度的序列，即:

a = ["foo"; "bar"; "qux"]
b = ["foo"; "bar"; "baz"; "quux"]
==
(root) -> foo -> bar -> [qux, baz -> quux]

是否有任何教科书示例或算法可以帮助我解决这一问题？似乎可以很好地解决它，但是我对它的一切刺探都绝对可怕!

请随时以任何功能语言发布解决方案，我将酌情进行翻译。

谢谢!

最佳答案

我解决此问题的方法是使用Forest表示您的类型，然后将Forest设置为Monoid，其中将两个mappend在一起的Forest将它们的共同祖先连接在一起。其余的只是想出一个合适的Show实例:

import Data.List (sort, groupBy)
import Data.Ord (comparing)
import Data.Foldable (foldMap)
import Data.Function (on)
import Data.Monoid

data Tree a = Node
    { value :: a
    , children :: Forest a
    } deriving (Eq, Ord)

instance (Show a) => Show (Tree a) where
    show (Node a f@(Forest ts0)) = case ts0 of
        []  -> show a
        [t] -> show a ++ " -> " ++ show t
        _   -> show a ++ " -> " ++ show f

data Forest a = Forest [Tree a] deriving (Eq, Ord)

instance (Show a) => Show (Forest a) where
    show (Forest ts0) = case ts0 of
        []  -> "[]"
        [t] -> show t
        ts  -> show ts

instance (Ord a) => Monoid (Forest a) where
    mempty = Forest []
    mappend (Forest tsL) (Forest tsR) =
          Forest
        . map (\ts -> Node (value $ head ts) (foldMap children ts))
        . groupBy ((==) `on` value)
        . sort
        $ tsL ++ tsR

fromList :: [a] -> Forest a
fromList = foldr cons nil
  where
    cons a as = Forest [Node a as]
    nil = Forest []

这是一些用法示例:

>>> let a = fromList ["foo", "bar", "qux"]
>>> let b = fromList ["foo", "bar", "baz", "quux"]
>>> a
"foo" -> "bar" -> "qux"
>>> b
"foo" -> "bar" -> "baz" -> "quux"
>>> a <> b
"foo" -> "bar" -> ["baz" -> "quux","qux"]
>>> a <> a
"foo" -> "bar" -> "qux"

因此，您的myFunc将变为:

myFunc :: [[a]] -> Forest a
myFunc = foldMap fromList