1

この種のデータ構造はHaskellライブラリに存在しますか？いくつか検索しましたが、役立つものが見つかりませんでした。自分で定義するのではなく、既存のタイプを使用したいのですが、そこにあるべきもののようです。

data MyTree e n = Node { rootLabel :: n
                       , subForest :: Map e (MyTree e n)
                       }

考え方は、Data.Treeと非常に似ていますが、エッジはノードだけでなく情報も保持できるということです。

（タイプ[e]の）ツリーを通るパスがある場合、O（log（n））に（タイプnの）rootLabelを見つけることができます。私の知る限り、Data.Treeでこれを行うことはできません。これは、ノードの各子をスキャンして、パスが進むノードであるかどうかを確認する必要があるためです。これは、Data.TreeのsubForestのタイプが[Treea]であるためです。

特に、次のような型の関数を公開する実装に興味があります。

getNextLevel :: e -> MyTree e n -> MyTree e n

トラバースするエッジが与えられると、ツリーの1レベル深く潜ります。

4

2 に答える 2

4

このデータ型は、Hackage で利用可能な多くのパッケージがあるトライによく似ています。

于 2012-04-07T23:53:28.870 に答える
-1

グラフライブラリはいつでも使用でき、ツリーとして保持していることを確認してください。

于 2012-04-07T23:09:39.627 に答える