8

タイプの値はどのようにできますか：

type Tree =
    | Node of int * Tree list

機能的な方法で生成されたそれ自体を参照する値がありますか？

Treeを適切に定義するには、次のPythonコードで結果の値がxに等しくなる必要があります。

x = Tree()
x.tlist = [x]

編集：明らかにもっと説明が必要です。私はF＃と関数型プログラミングを学ぼうとしているので、以前にプログラミングしたカバーツリーを他の言語で実装することにしました。ここで重要なのは、各レベルのポイントが下のレベルのポイントのサブセットであるということです。構造は概念的にレベル無限大になります。

命令型言語では、ノードにはそれ自体を含む子のリストがあります。これはF＃で必須に実行できることを私は知っています。いいえ、カバーツリーアルゴリズムが与えられた場合、無限ループは作成されません。

4

2 に答える 2

9

Tomas の回答は、F# で再帰的なデータ構造を作成する 2 つの方法を示唆しています。3 番目の可能性は、レコード フィールドが直接再帰をサポートするという事実を利用することです (レコードが定義されているのと同じアセンブリで使用される場合)。たとえば、次のコードは問題なく動作します。

type 'a lst = Nil | NonEmpty of 'a nelst
and 'a nelst = { head : 'a; tail : 'a lst }

let rec infList = NonEmpty { head = 1; tail = infList }

組み込みのリスト タイプの代わりにこのリスト タイプを使用すると、コードを機能させることができます。

type Tree = Node of int * Tree lst
let rec x = Node(1, NonEmpty { head = x; tail = Nil })
于 2010-06-21T19:23:49.387 に答える
7

再帰参照が遅延していない場合 (たとえば、関数または遅延値でラップされている場合)、これを直接行うことはできません。「一気に」すぐに参照して値を作成する方法がないというのが動機だと思うので、これは理論的な観点からは厄介です。

ただし、F# は再帰値をサポートしています。再帰参照が遅延している場合は、それらを使用できます (F# コンパイラは、データ構造を初期化し、再帰参照を埋めるコードを生成します)。最も簡単な方法は、参照を遅延値でラップすることです (関数も機能します)。

type Tree = 
    | Node of int * Lazy<Tree list>

// Note you need 'let rec' here!        
let rec t = Node(0, lazy [t; t;])

別のオプションは、ミューテーションを使用してこれを記述することです。次に、データ構造を変更可能にする必要もあります。たとえば、次ref<Tree>の代わりに保存できTreeます。

type Tree = 
    | Node of int * ref<Tree> list

// empty node that is used only for initializataion
let empty = Node(0, [])
// create two references that will be mutated after creation    
let a, b = ref empty, ref empty

// create a new node
let t = Node(0, [a; b])
// replace empty node with recursive reference
a := t; b := t

ジェームズが述べたように、これを行うことが許可されていない場合は、データ構造をウォークするプログラムが終了するなど、いくつかの優れたプロパティを持つことができます (データ構造は制限されており、再帰できないため)。したがって、再帰的な値にはもう少し注意する必要があります:-)

于 2010-06-21T16:50:42.673 に答える