2

次から問題が与えられます。

http://arunrocks.com/treeify_-_converting_tree_data_structures/

趣味のプロジェクトで、ツリーのフラットな表現をネストされたデータ構造に変換するという興味深い問題に直面しました。ツリーの平面表現は次のようになります。

0 0 1 1 2 3 2 1

各番号は、ツリー内のネスト レベルを表します。ネストされた構造に変換すると、次のようになります (角括弧はリストの Python 構文です)。

[ 0, 0, [ 1, 1, [ 2, [ 3 ], 2], 1]]

Haskellでこれを行うにはどうすればよいですか?

4

1 に答える 1

14

Haskell では、リストのすべての要素が同じ型である必要があります。したがって、1 つの要素が整数で、別の要素がリストであるリストを作成することはできません。したがって[1, [2, 3]]、Haskell では型エラーが発生します。

したがって、このように任意にネストされた構造を表現したい場合は、独自の型を定義する必要があります。それは次のようになります。

data Tree a =
    Leaf a
  | Branch [Tree a]

その型の値は次のようになります。

Branch [
  Leaf 0, Leaf 0,
  Branch [
    Leaf 1, Leaf 1, Branch [
      Leaf 2, Branch [
        Leaf 3],
      Leaf 2],
    Leaf 1]]
于 2013-06-15T10:40:24.310 に答える