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

Question

我不确定这是否是一个容易解决的问题,我只是遗漏了一些明显的东西,但是我一直在反对它.我试图用列表表达树分歧.这样我就可以使用简单的原语轻松地内联指定我的数据集,而不用担心顺序,并在以后从一组不同的列表中构建树.

所以我有一些像这样的列表:

 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]

是否有任何教科书示例或算法可以帮助我解决这个问题？看起来它可以优雅地解决,但我对它的所有刺痛看起来都非常可怕!

请随意发布任何功能语言的解决方案,我会酌情翻译.

谢谢!

Answer 1

我解决这个问题的方法是使用a Forest来表示你的类型,然后创建一个Foresta 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