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]