4

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

所以我有一些这样的列表：

 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]

是否有任何教科书示例或算法可以帮助我解决这个问题？似乎可以优雅地解决它，但我所有的尝试看起来都非常可怕！

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

谢谢！

4

4 回答 4

5

我解决这个问题的方法是使用 aForest来表示您的类型，然后制作 a Foresta Monoid，其中mappending 两个Forests 一起加入它们的共同祖先。剩下的只是想出一个合适的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
于 2013-07-26T22:48:46.550 回答
3

我想出了一个与 Gabriel 非常相似的解决方案，但我的数据表示使用 aMap以便我可以将大部分工作加载到Data.Map.unionWith.

import Data.Map (Map, empty, singleton, unionWith, assocs)
import Data.Monoid

type Path a = [a]
data Tree a = Tree {leaf :: Bool, childs :: Map a (Tree a)} deriving Show

树中的布尔标志标记该节点是否可以是路径的末端。这些a值隐藏在childs地图中。为了热身，让我们定义如何将单个路径转换为树。

root :: Tree a
root = Tree True empty

cons :: a -> Tree a -> Tree a
cons node tree = Tree False (singleton node tree)

follow :: Path a -> Tree a
follow = foldr cons root

该follow函数fromList在 Gabriel 的代码中被调用。我们还可以枚举树中包含的所有路径。

paths :: Tree a -> [Path a]
paths (Tree leaf childs) =
  (if leaf then [[]] else []) ++
  [ node : path | (node, tree) <- assocs childs, path <- paths tree ]

这些问题本质上是要求这个paths函数的倒数。使用unionWith，我们可以很容易地定义树的幺半群结构。

instance Ord a => Monoid (Tree a) where
  mempty = Tree False empty
  mappend (Tree leaf1 childs1) (Tree leaf2 childs2) = Tree leaf childs where
    leaf = leaf1 || leaf2
    childs = unionWith mappend childs1 childs2

现在要将路径列表转换为树，我们只需使用mconcatand follow。

unpaths :: Ord a => [Path a] -> Tree a
unpaths = mconcat . map follow

这是一个使用问题路径的测试用例。

a, b, c, d :: Path String

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

-- test is True
test = (paths . unpaths) [a, b, c, d] == [b, d, a, c]

我们得到与存储在树中相同的路径，但作为有序列表。

于 2013-07-26T23:21:30.277 回答
1 
type TreeNode<'T> = 
  | Node of 'T * Tree<'T>
and Tree<'T> = TreeNode<'T> list

module Tree =
  let rec ofList = function
    | [] -> []
    | x::xs -> [Node(x, ofList xs)]

  let rec merge xs tree =
    match (tree, xs) with
    | _, [] -> tree
    | [], _ -> ofList xs
    | nodes, x::xs ->
      let matching, nonMatching = nodes |> List.partition (fun (Node(y, _)) -> y = x)
      match matching with
      | [Node(_, subtree)] -> Node(x, merge xs subtree) :: nonMatching
      | _ -> Node(x, ofList xs)::nodes

Tree.ofList ["foo"; "bar"; "qux"]
|> Tree.merge ["foo"; "bar"; "baz"]
|> Tree.merge ["qux"; "bar"; "qux"]

> val it : TreeNode<string> list =
  [Node ("qux",[Node ("bar",[Node ("qux",[])])]);
   Node ("foo",[Node ("bar",[Node ("baz",[]); Node ("qux",[])])])]
于 2013-07-26T23:37:19.157 回答
0

使用哈希图的 clojure 版本：

(defn merge-to-tree
  [& vecs]
  (let [layer (group-by first vecs)]
    (into {} (map (fn [[k v]]
                    (when k
                      [k (apply merge-to-tree (map rest v))]))
                  layer))))

在这里，我使用 group-by 来查看多个向量元素何时应由输出结构中的单个项目表示。(into {} (map (fn [[k v]] ...) m))是用于解构散列条目、执行一些操作，然后从结果重建散列的标准习语。对值的递归调用在(apply merge-to-tree (map rest v))树结构的该层下方构造了各种分支（map rest，因为完整的输入由 group-by 保存，并且第一个元素已经用作查找键）。

我欢迎其他建议/改进。示例用法：

user> (merge-to-tree ["foo" "bar" "qux"])
{"foo" {"bar" {"qux" {}}}}

user> (merge-to-tree ["foo" "bar" "qux"] ["foo" "bar" "baz"] ["qux" "bar" "qux"])
{"foo" {"bar" {"qux" {}, "baz" {}}}, "qux" {"bar" {"qux" {}}}}

user> (merge-to-tree ["foo" "bar" "qux"] ["foo" "bar" "baz" "quux"])
{"foo" {"bar" {"qux" {}, "baz" {"quux" {}}}}}
于 2013-07-27T04:54:04.003 回答