F中的循環列表＃

Question

它只是我，還是F＃不適合循環列表？

我通過反射器查看FSharpList<T>類，並注意到'結構等於'或長度方法都不檢查週期。我只能猜測2個這樣的原始函數沒有檢查，大多數列表函數也不會這樣做。

如果循環列表不支持，爲什麼？

謝謝

PS：我甚至在看右邊的列表類嗎？

Answer 1

F＃中有許多不同的列表/集合類型。

• F＃list類型。正如克里斯所說，你不能初始化這種類型的遞歸值，因爲類型不是懶惰且不可變（不可變性意味着你必須立即創建它，並且它不是懶惰的意思是你不能使用F＃遞歸值使用let rec）。正如ssp所說，你可以使用Reflection來破解它，但這可能是我們不想討論的情況。

• 另一種類型是seq（實際上是IEnumerable）或LazyList類型來自PowerPack。這些是懶惰的，所以你可以使用let rec創建一個循環值。然而，（據我所知）沒有任何與它們一起工作的函數會考慮循環列表 - 如果你創建一個循環列表，它只是意味着你創建了一個無限列表，所以（eg） map將是一個潛在的無限列表。

這裏是LazyList類型的例子：

#r "FSharp.PowerPack.dll" 

// Valid use of value recursion 
let rec ones = LazyList.consDelayed 1 (fun() -> ones) 
Seq.take 5 l // Gives [1; 1; 1; 1; 1] 

的問題是，什麼樣的數據類型，你可以自己定義。Chris顯示了一個可變列表，如果你編寫修改它的操作，它們將影響整個列表（如果你將它解釋爲無限數據結構）。

您也可以定義一個惰性（可循環）數據類型並實現處理循環的操作，因此當您創建一個循環列表並將其投影到另一個列表中時，它將創建循環列表作爲結果（而不是一個有效的無限的數據結構）。

的類型聲明可能看起來像這樣（我使用的對象類型，這樣我們可以爲週期檢查時使用引用相等）：

type CyclicListValue<'a> = 
    Nil | Cons of 'a * Lazy<CyclicList<'a>> 

and CyclicList<'a>(value:CyclicListValue<'a>) = 
    member x.Value = value 

以下map函數處理週期 - 如果你給它循環列表，它會返回一個新創建的列表以相同的環狀結構：

let map f (cl:CyclicList<_>) = 
    // 'start' is the first element of the list (used for cycle checking) 
    // 'l' is the list we're processing 
    // 'lazyRes' is a function that returns the first cell of the resulting list 
    // (which is not available on the first call, but can be accessed 
    // later, because the list is constructed lazily) 
    let rec mapAux start (l:CyclicList<_>) lazyRes = 
    match l.Value with 
    | Nil -> new CyclicList<_>(Nil) 
    | Cons(v, rest) when rest.Value = start -> lazyRes() 
    | Cons(v, rest) -> 
     let value = Cons(f v, lazy mapAux start rest.Value lazyRes) 
     new CyclicList<_>(value) 
    let rec res = mapAux cl cl (fun() -> res) 
    res 

Answer 2

F＃列表類型本質上是一個鏈表，其中每個節點都有一個「下一個」。理論上這將允許您創建循環。但是，F＃列表是不可變的。所以你永遠不可能通過變異「製造」這個循環，你必須在施工時做到這一點。 （因爲你不能在最後一個節點循環更新繞到前面。）

您可以寫這個去做，但是編譯器專門用來防止它：

let rec x = 1 :: 2 :: 3 :: x;; 

    let rec x = 1 :: 2 :: 3 :: x;; 
    ------------------------^^ 

stdin(1,25): error FS0260: Recursive values cannot appear directly as a construction of the type 'List`1' within a recursive binding. This feature has been removed from the F# language. Consider using a record instead. 

如果你想創建一個週期，你可以做到以下幾點：

> type CustomListNode = { Value : int; mutable Next : CustomListNode option };; 

type CustomListNode = 
    {Value: int; 
    mutable Next: CustomListNode option;} 

> let head = { Value = 1; Next = None };; 

val head : CustomListNode = {Value = 1; 
          Next = null;} 

> let head2 = { Value = 2; Next = Some(head) } ;; 

val head2 : CustomListNode = {Value = 2; 
           Next = Some {Value = 1; 
              Next = null;};} 

> head.Next <- Some(head2);; 
val it : unit =() 
> head;; 
val it : CustomListNode = {Value = 1; 
          Next = Some {Value = 2; 
             Next = Some ...;};} 

Answer 3

答案是與尾調用優化的支持和一流的功能（功能類型）的語言同樣的支持：它很容易模仿環狀結構。

let rec x = seq { yield 1; yield! x};; 

這是通過使用seq的懶惰來模擬該結構的最簡單的方法。 當然，您可以按照here所描述的方式對錶單進行表示。

Answer 4

正如之前所說，在這裏你的問題是，list類型是不可變的，併爲list是循環的ÿ你必須讓它堅持到最後的元素，所以這是行不通的。當然，你可以使用序列。

如果您有現成的list，並希望創造在它上面的無限序列，通過列表的元素週期，這裏是你如何能做到這一點：

let round_robin lst = 
    let rec inner_rr l =   
     seq { 
      match l with 
      | [] -> 
       yield! inner_rr lst    
      | h::t ->     
       yield h     
       yield! inner_rr t    
     }  
    if lst.IsEmpty then Seq.empty else inner_rr [] 


let listcycler_sequence = round_robin [1;2;3;4;5;6]