f# - recursivos - recursividad programacion

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

Question

Una función de adición simple como esta (en F #):

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

se bloqueará cuando s se convierta en grande, ya que la función no es recursiva de cola. Noté que la función de anexión estándar de F # no falla con 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

Además de lo que Juliet publicó:

Usando expresiones de secuencia
Internamente, las expresiones de secuencia generan un código recursivo de cola, así que esto funciona bien.

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

Usar tipos de .NET mutables
David mencionó que las listas F # pueden ser mutadas; sin embargo, eso solo está limitado a las bibliotecas F # core (y la función no puede ser utilizada por los usuarios porque rompe los conceptos funcionales). Puede usar tipos de datos mutables de .NET para implementar una versión basada en mutaciones:

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 escenarios, pero generalmente evitaría la mutación en el código F #.

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

Tradicional (no recursivo de la cola)

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

Con un acumulador (recursivo de la cola)

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

Con continuaciones (recursivo de cola)

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 simple convertir cualquier función recursiva no cola en recursiva con continuaciones, pero personalmente prefiero los acumuladores para una legibilidad directa.