Как я могу реализовать рекурсивный хвостом список, добавляют?
Простое добавляет функцию как это (в F#):
let rec app s t =
match s with
| [] -> t
| (x::ss) -> x :: (app ss t)
откажет, когда s становится большим, так как функция не является рекурсивным хвостом. Я заметил, что стандарт F# добавляет функцию, не отказывает с большими списками, таким образом, это должно быть реализовано по-другому. Таким образом, я задался вопросом: Как делает хвост, который добавляет рекурсивное определение, похожи? Я придумал что-то вроде этого:
let rec comb s t =
match s with
| [] -> t
| (x::ss) -> comb ss (x::t)
let app2 s t = comb (List.rev s) t
который работает, но выглядит довольно нечетным. Существует ли более изящное определение?
3 ответа
Традиционный (не хвост-рекурсивный)
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)
Довольно прямолинейно преобразовать любую нехвостую рекурсивную функцию в рекурсивную с продолжениями, но лично я предпочитаю аккумуляторы для прямолинейной читаемости.
В дополнение к тому, что написала Джульетта:
Использование выражений последовательности
Внутренне выражения последовательности генерируют хвостовой рекурсивный код, так что это прекрасно работает.
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 #.
При беглом взгляде на исходники F # кажется, что хвост внутренне изменяемый. Простым решением было бы перевернуть первый список перед включением его элементов во второй список. Это, наряду с реверсированием списка, тривиально для рекурсивной реализации tail.