Циклические списки в F #

Question

Это только я или F # не обслуживает циклические списки?

Я посмотрел на класс FSharpList<T> с помощью рефлектора и заметил, что ни метод «структурное равенство», ни методы длины не проверяют циклы. Я могу только догадываться, если 2 такие примитивные функции не проверяют, что большинство функций списка также не сделают этого.

Если циклические списки не поддерживаются, почему это так?

Спасибо

PS: Я даже смотрю на правильный список класса?

Answer 1

В F # есть много разных списков / типов коллекций.

• F # list type.Как сказал Крис, вы не можете инициализировать рекурсивное значение этого типа, потому что тип не ленивый и не изменяемый (неизменность означает, что вы должны создать его сразу, а тот факт, что он не ленивый, означает, что вы не можете использовать F # рекурсивныйзначения с использованием let rec).Как сказал ssp, вы можете использовать Reflection для взлома, но это, вероятно, случай, который мы не хотим обсуждать.

• Другой тип - seq (который на самом деле IEnumerable) или тип LazyList от PowerPack.Они ленивы, поэтому вы можете использовать let rec для создания циклического значения.Однако (насколько я знаю) ни одна из функций, работающих с ними, не учитывает циклические списки - если вы создаете циклический список, это просто означает, что вы создаете бесконечный список, поэтому результатиз (например) 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]

Вопрос в том, какие данныетипы вы можете определить сами.Крис показывает изменяемый список, и если вы пишете операции, которые его изменяют, они влияют на весь список (если вы интерпретируете его как бесконечную структуру данных).

Вы также можете определить ленивый (потенциально циклический) тип данныхи реализуйте операции, которые обрабатывают циклы, поэтому, когда вы создаете циклический список и проецируете его в другой список, в результате будет создан циклический список (а не потенциально бесконечная структура данных).

Объявление типа может выглядеть следующим образом (я использую тип объекта, поэтому мы можем использовать равенство ссылок при проверке циклов):

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

Ответ одинаков для всех языков с поддержкой оптимизации хвостового вызова и поддержкой первоклассных функций (типов функций): циклические структуры легко эмулировать.

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

Это самый простой способ эмулировать эту структуру, используя лень seq. Конечно, вы можете взломать представление списка, как описано здесь .

Answer 3

Тип списка 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 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]