Как я могу реализовать добавление хвостового рекурсивного списка?

Простая функция append, подобная этой (в F #):

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

будет сбой, когда s станет большим, так как функция не является хвостовой рекурсивной. Я заметил, что стандартная функция добавления F # не сбой с большими списками, поэтому она должна быть реализована по-разному. Поэтому я подумал: как выглядит хвостовое рекурсивное определение append? Я придумал что-то вроде этого:

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

который работает, но выглядит довольно странно. Есть ли более элегантное определение?

Ответы

Ответ 1

Традиционный (не хвостовой рекурсивный)

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

С аккумулятором (хвостовым рекурсивным)

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

С продолжением (хвостовым рекурсивным)

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)

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

Ответ 2

В дополнение к тому, что опубликовала Джульетта:

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

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

Использование изменяемых типов .NET
Дэвид упомянул, что списки F # могут быть мутированы, но ограничены только базовыми библиотеками F # (и эта функция не может использоваться пользователями, поскольку она нарушает функциональные концепции). Вы можете использовать изменяемые типы данных .NET для реализации версии на основе мутаций:

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

Это может быть полезно в некоторых сценариях, но я обычно избегал мутации в коде F #.

Ответ 3

С быстрым взглядом на источники F # кажется, что хвост внутренне изменен. Простым решением было бы обратить вспять первый список, прежде чем включать его элементы во второй список. Это, наряду с реверсированием списка, тривиально для реализации хвоста рекурсивно.