¿Cómo puedo implementar una lista recursiva de cola?

Question

una simple función de agregación como esto (en C#):

let rec app s t = 
    match s with 
     | [] -> t 
     | (x::ss) -> x :: (app ss t) 

se bloqueará cuando s se convierte en grande, ya que la función no es recursiva cola. Me di cuenta de que la función de anexión estándar de F # no falla con las listas grandes, por lo que debe implementarse de manera diferente. Entonces me pregunté: ¿Cómo se ve una definición recursiva de cola? Se me ocurrió algo como esto:

let rec comb s t = 
    match s with 
     | [] -> t 
     | (x::ss) -> comb ss (x::t) 
let app2 s t = comb (List.rev s) t 

que funciona, pero parece bastante extraño. ¿Hay una definición más elegante?

Answer 1

tradicional (no recursiva de cola)

let rec append a b = 
    match a, b with 
    | [], ys -> ys 
    | x::xs, ys -> x::append xs ys 

Con un acumulador (tail-recursivo)

let append2 a b = 
    let rec loop acc = function 
     | [] -> acc 
     | x::xs -> loop (x::acc) xs 
    loop b (List.rev a) 

Con continuaciones (tail-recursivo)

let append3 a b = 
    let rec append = function 
     | cont, [], ys -> cont ys 
     | cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys) 
    append(id, a, b) 

Es bastante sencillo convertir cualquier función recursiva no cola en recursiva con continuaciones, pero personalmente prefiero los acumuladores para una legibilidad directa.

Answer 2

De un vistazo rápido a las fuentes F #, parece que la cola es internamente mutable. Una solución simple sería invertir la primera lista antes de considerar sus elementos en la segunda lista. Eso, junto con revertir la lista, es trivial para implementar la cola recursivamente.

Answer 3

Además de lo que Julieta colocado:

El uso de expresiones de secuencia
Internamente, las expresiones de secuencia generar código recursiva de cola, por lo que este funciona bien.

let append xs ys = 
    [ yield! xs 
    yield! ys ] 

Uso de tipos de .NET mutables
David mencionaron que F listas # pueden mutarse - eso es sin embargo limitado únicamente a las bibliotecas # núcleo F (y la función no puede ser utilizado por los usuarios, ya que rompe los conceptos funcionales) . Puede utilizar los tipos de datos .NET mutables para implementar una versión basada en mutación:

let append (xs:'a[]) (ys:'a[]) = 
    let ra = new ResizeArray<_>(xs) 
    for y in ys do ra.Add(y) 
    ra |> List.ofSeq 

Esto puede ser útil en algunos casos, pero en general, volvería a evitar mutación en F # código.