Listas cíclicas en F #

Question

¿Soy solo yo o F no cumple con las listas cíclicas?

Miré la clase FSharpList<T> mediante un reflector, y me di cuenta de que ni el 'estructural es igual' ni los métodos de longitud comprueban los ciclos. Solo puedo adivinar si 2 de estas funciones primitivas no comprueban, que la mayoría de las funciones de lista tampoco lo harían.

Si las listas cíclicas no son compatibles, ¿por qué?

Gracias

PS: ¿Estoy siquiera mirar a la clase de lista de la derecha?

Answer 1

Hay muchas listas/tipos de colecciones diferentes en F #.

• F # list tipo. Como dijo Chris, no puede inicializar un valor recursivo de este tipo, porque el tipo no es flojo ni mutable (la inmutabilidad significa que debe crearlo de inmediato y el hecho de que no sea flojo significa que no puede usar F # recursivo valores usando let rec). Como dijo ssp, podrías usar Reflection para hackearlo, pero ese es probablemente un caso del que no queremos hablar.

• Otro tipo es seq (que en realidad es IEnumerable) o el tipo de PowerPack LazyList. Estos son flojos, por lo que puede usar let rec para crear un valor cíclico. Sin embargo, (hasta donde yo sé) ninguna de las funciones que trabajan con ellos tiene en cuenta las listas cíclicas. Si crea una lista cíclica, simplemente significa que está creando una lista infinita, por lo que el resultado de (por ejemplo) map será una lista potencialmente infinita.

Aquí es un ejemplo para LazyList Tipo:

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

La cuestión es qué tipos de datos se definiría usted mismo.Chris muestra una lista mutable y si escribe operaciones que la modifiquen, afectarán a toda la lista (si la interpreta como una estructura de datos infinita).

También puede definir un tipo de datos perezoso (potencialmente cíclico) e implementar operaciones que manejan ciclos, por lo que cuando crea una lista cíclica y la proyecta en otra lista, creará una lista cíclica como resultado (y no potencialmente estructura de datos infinita).

La declaración de tipo puede tener este aspecto (estoy usando el tipo de objeto, de manera que podemos utilizar la igualdad de referencia en la comprobación de ciclos):

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

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

El map siguiente función se encarga de ciclos - si le das una lista cíclica, devolverá una lista recién creada con la misma estructura cíclica:

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

El tipo de lista F # es esencialmente una lista vinculada, donde cada nodo tiene un 'siguiente'. Esto en teoría te permitiría crear ciclos. Sin embargo, las listas F # son inmutables. Entonces nunca podrías 'hacer' este ciclo por mutación, tendrías que hacerlo en el momento de la construcción. (Puesto que no se ha podido actualizar el último nodo de bucle alrededor de la parte delantera.)

Usted podría escribir esto para hacerlo, sin embargo, el compilador específicamente evita que:

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. 

Si desea para crear un ciclo, se puede hacer lo siguiente:

> 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

la respuesta es la misma para todos los idiomas con localización de optimización de llamada y la primera clase de funciones (tipos de función) de apoyo: es tan fácil de imitar estructuras cíclicas.

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

Es manera más simple de emular esa estructura mediante el uso de la pereza de la SEC. Por supuesto, puede hackear la representación de la lista como se describe here.

Answer 4

Como se dijo antes, el problema aquí es que el tipo list es inmutable, y por un list a ser y cíclica tendrías que tenerlo pegado en su último elemento, entonces eso no funciona. Puedes usar secuencias, por supuesto.

Si usted tiene una ya existente list y desea crear una secuencia infinita en la parte superior de la misma que se desplaza por los elementos de la lista, así es como podría hacerlo:

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]