如何在（功能性）F＃中創建遞歸數據結構值？

如何類型的值：如何在（功能性）F＃中創建遞歸數據結構值？

type Tree = 
    | Node of int * Tree list

有引用自身的功能性的方式所產生的價值呢？

所得值應等於在以下Python碼x，對於樹的合適定義：

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

編輯：顯然更多的解釋是必要的。我正在嘗試學習F＃和函數式編程，所以我選擇實現我以前編寫過的其他語言的cover tree。這裏的相關內容是每個關卡的關鍵點都是以下關卡的一個子集。這個結構在概念上走向了層次無窮。

在命令式語言中，節點有一個包含自身的子節點列表。我知道這可以在F＃中做到。不，它不會在給定封面樹算法的情況下產生無限循環。

來源

2010-06-21 Muhammad Alkarouri

你能對這個問題展開，對於那些不會說太多Python的人呢？你的類型定義看起來很好，但是請注意F＃不允許直接構造一個判別聯合類型（例如樹）......只能構造聯合值;例如Node，如「let x = Node（0，[]）」或「let y = Node（1，[x]）」，其中[]是空列表。 – 2010-06-21 16:43:31

@詹姆斯：他想創建一個屬於自己孩子的節點。像'let rec x = Node（東西，[x]）'（除了不起作用）。 – sepp2k 2010-06-21 16:47:38

@ sepp2k：這通常會爲列表中的任何代碼創建一個無限循環，儘管...非常不可取的:-)我已經看到在其他語言中完成標記列表的結束，但爲了這個目的，idomatic F＃會使用另一個DU值，例如「None」。 – 2010-06-21 16:51:08

Tomas的答案提出了兩種可能的方式來在F＃中創建遞歸數據結構。第三種可能性是利用記錄字段支持直接遞歸的事實（當在與定義記錄相同的程序集中使用時）。例如，下面的代碼工作沒有任何問題：

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-21 19:23:49 kvb

有趣。從概念上來說，「從某種意義上說，它是否等同於懶惰的列表？ – 2010-06-21 21:15:09

@穆罕默德 - 不，「'一個'不懶惰，所以它就像內置列表。它通過一條記錄的事實允許你創建自引用數據結構，但是你不能用這種類型來做一些事情，比如創建一個所有偶數的流，就像你可以用一個懶惰的列表一樣。 – kvb 2010-06-21 23:21:25

+1好戲，我不知道這是可能的！ – 2010-06-22 00:03:02

如果遞歸引用沒有延遲（例如包裝在函數或惰性值中），則不能直接執行此操作。我認爲動機是，沒有辦法立即引用「立即」創造價值，因此從理論角度來看，這將是尷尬的。但是，F＃支持遞歸值 - 如果遞歸引用被延遲（F＃編譯器將生成一些初始化數據結構並填充遞歸引用的代碼），則可以使用這些值。最簡單的方法就是換一個懶惰的值內refernece（功能將工作太）：

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-21 16:50:42

很好的答案。謝謝。從效率的角度來看，一個比另一個更好？（不知怎的，我覺得我會後悔的） – 2010-06-21 20:47:00

'懶惰'比'ref'嚴格得複雜（它必須跟蹤它是否被評估過），所以'ref'應該更有效率，但我懷疑沒有實際的區別。 – 2010-08-06 12:59:13

如何在（功能性）F＃中創建遞歸數據結構值？

回答

相關問題