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

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

我解决这个问题的方法是使用 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