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

Такая простая функция добавления (в 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

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


f# append tail-recursion
person martingw    schedule 19.05.2010    source источник

Ответы (3)


arrow_upward
26
arrow_downward

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

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)

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

person Juliet    schedule 19.05.2010
comment
В первом примере какой смысл выполнять сопоставление с образцом на b, если оно одинаково для всех образцов? Вы можете просто использовать b - person Rubys; 19.05.2010
comment
Вы уверены, что это работает? Я получаю ›append2 [1; 2] [3; 4] ;; val it: int list = [2; 3; 4] и ›append3 [1; 2] [3; 4] ;; val it: int list = [1; 3; 4] Хотя я не вижу ошибки, append2 мне кажется нормальным. - person martingw; 20.05.2010
comment
Очень странно. Ваш код в порядке, он работает с fsc. Однако не работает в пределах fsi. Не первая проблема с fsi на моно. - person martingw; 20.05.2010
comment
Последнее замечание: разница между append2 и append3 не только в удобочитаемости: append2 [1..10000000] [] работает, а append3 [1..10000000] [] приводит к переполнению стека. - person martingw; 20.05.2010
comment
@martingw: append2 и append3 верны, нет никаких причин, по которым вы получите неправильный результат. Кроме того, append3 является хвостовым рекурсивным, но вы все равно можете переполнить стек, если запустите код в режиме отладки, поскольку хвостовые вызовы по умолчанию отключены (см. stackoverflow.com/questions/1416415/). - person Juliet; 20.05.2010
comment
Я не верю, что mono поддерживает хвостовую рекурсию, поэтому вы получите stackoverflow с помощью append3. - person justin; 20.05.2010
comment
@ Джульетта: Да, извините, что сомневаюсь в вашем коде :-)! Прекрасно работает с fsi на .NET, поэтому то, что я обнаружил, определенно было монофонической проблемой. Также нет переполнения стека с помощью append3 для больших списков в .NET, так что, возможно, это тоже была какая-то моно вещь. @justin: append2 работал с большими списками в моно, поэтому я думаю, что какой-то tco должен быть реализован в моно. - person martingw; 20.05.2010
comment
append3 эффективнее append2? - person day; 12.06.2013
comment
Есть ли способ реализовать хвостовую рекурсивную версию с аккумулятором без изменения первого списка? - person Derek Mahar; 10.10.2015

arrow_upward
15
arrow_downward

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

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

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

person Tomas Petricek    schedule 19.05.2010

arrow_upward
1
arrow_downward

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

person Daniel    schedule 19.05.2010