Danh sách tuần hoàn trong F #

Question

Chỉ là tôi, hay F # không phục vụ cho danh sách theo chu kỳ?

Tôi đã xem lớp FSharpList<T> qua phản xạ và nhận thấy rằng không phải phương thức 'cấu trúc bằng' hoặc phương pháp độ dài đều kiểm tra chu kỳ. Tôi chỉ có thể đoán nếu 2 chức năng nguyên thủy như vậy không kiểm tra, rằng hầu hết các chức năng danh sách sẽ không làm điều này.

Nếu danh sách vòng tuần hoàn không được hỗ trợ, tại sao vậy?

Cảm ơn

PS: Tôi thậm chí còn nhìn vào lớp danh sách phù hợp phải không?

Answer 1

Có nhiều danh sách/loại bộ sưu tập khác nhau trong F #.

• Loại F # list. Như Chris đã nói, bạn không thể khởi tạo giá trị đệ quy của kiểu này, vì kiểu không lười và không thể thay đổi được (Tính không thay đổi có nghĩa là bạn phải tạo nó cùng một lúc và thực tế là không lười biếng có nghĩa là bạn không thể sử dụng đệ quy F # giá trị sử dụng let rec). Như ssp đã nói, bạn có thể sử dụng Reflection để hack nó, nhưng đó có thể là một trường hợp mà chúng ta không muốn thảo luận.

• Loại khác là seq (thực tế là IEnumerable) hoặc loại LazyList từ PowerPack. Đây là những lười biếng, vì vậy bạn có thể sử dụng let rec để tạo ra một giá trị tuần hoàn. Tuy nhiên, (theo như tôi biết), không có hàm nào làm việc với chúng đưa danh sách tuần hoàn vào tài khoản - nếu bạn tạo danh sách tuần hoàn, điều đó có nghĩa là bạn đang tạo một danh sách vô hạn, do đó kết quả của (ví dụ) map sẽ là danh sách vô hạn tiềm ẩn.

Dưới đây là một ví dụ cho LazyList loại:

#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] 

Câu hỏi đặt ra là những loại dữ liệu bạn có thể xác định chính mình.Chris hiển thị danh sách có thể thay đổi và nếu bạn viết các hoạt động sửa đổi nó, chúng sẽ ảnh hưởng đến toàn bộ danh sách (nếu bạn diễn giải nó dưới dạng cấu trúc dữ liệu vô hạn). Bạn cũng có thể định nghĩa một kiểu dữ liệu lười biếng (potentionally cyclic) và thực hiện các thao tác xử lý chu kỳ, vì vậy khi bạn tạo một danh sách tuần hoàn và đưa nó vào danh sách khác, nó sẽ tạo ra danh sách tuần hoàn (chứ không phải là một potentionally) cấu trúc dữ liệu vô hạn).

Việc kê khai loại có thể giống như thế này (tôi đang sử dụng loại đối tượng, để chúng ta có thể sử dụng bình đẳng tham khảo khi kiểm tra chu kỳ):

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

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

Chức năng sau map xử lý chu kỳ - nếu bạn cho nó một danh sách theo chu kỳ, nó sẽ trả về một danh sách mới được tạo ra với cùng một cấu trúc cyclic:

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

Loại danh sách F # về cơ bản là danh sách được liên kết, trong đó mỗi nút có 'tiếp theo'. Điều này trong lý thuyết sẽ cho phép bạn tạo chu kỳ. Tuy nhiên, danh sách F # là không thay đổi. Vì vậy, bạn không bao giờ có thể 'làm' chu kỳ này bằng đột biến, bạn sẽ phải làm điều đó vào thời gian xây dựng. (Vì bạn không thể cập nhật nút cuối cùng để lặp xung quanh để phía trước.)

Bạn thể viết này để làm điều đó, tuy nhiên trình biên dịch đặc biệt ngăn không cho nó:

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. 

Nếu bạn muốn để tạo ra một chu kỳ, bạn có thể làm như sau:

> 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

Câu trả lời là như nhau cho tất cả các ngôn ngữ với đuôi gọi hỗ trợ tối ưu hóa và hạng nhất chức năng (loại chức năng) hỗ trợ: nó rất dễ dàng để bắt chước cấu trúc cyclic.

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

Cách đơn giản nhất để mô phỏng cấu trúc đó bằng cách sử dụng độ lười của seq. Tất nhiên bạn có thể hack danh sách đại diện như mô tả here.

Answer 4

Như đã nói trước đây, vấn đề của bạn ở đây là loại list là không thay đổi, và cho một list là cyclic y bạn sẽ phải dán nó vào phần tử cuối cùng của nó, để nó không hoạt động. Bạn có thể sử dụng trình tự, tất nhiên.

Nếu bạn có một hiện list và muốn tạo một chuỗi vô hạn trên đầu trang của nó mà chu kỳ thông qua các yếu tố của danh sách, dưới đây là cách bạn có thể làm điều đó:

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]