Является ли эта функция почтового хвоста рекурсивной?

Question

Я реализовал это используя продолжение. Я думаю, что это хвостовая рекурсия, но мне сказали, что это не так. Почему хвост не рекурсивный?

let rec zip_tr fc sc l1 l2 = match l1, l2 with
  | [], [] -> sc []
  | [], _ -> fc (List.length l2)
  | _, [] -> fc (List.length l1)
  | h1::t1, h2::t2 -> 
    zip_tr fc (fun l -> sc ((h1, h2) :: l)) t1 t2

Разве этот хвост не рекурсивный? Влияет ли продолжение неудачи / успеха на рекурсивность хвоста?

Answer 1

В вашем коде только один рекурсивный вызов, и он находится в хвостовой позиции. Поэтому я бы сказал, что ваша функция хвостовая рекурсивная.

Она создает довольно большие вычисления в аргументе sc. Тем не менее, вызов sc также находится в хвостовой позиции. В моих тестах функция работала для очень больших списков без исчерпания пространства стека.

Если я опробую вашу функцию на двух копиях очень длинного списка (100 000 000 элементов), она успешно завершится (после довольно долгоговремя). Это наводит меня на мысль, что это действительно хвостовая рекурсия.

Вот сеанс с длинным списком:

# let rec zip_tr fc sc l1 l2 =  . . . ;;
val zip_tr :
  (int -> 'a) -> (('b * 'c) list -> 'a) -> 'b list ->
      'c list -> 'a = <fun>
# let rec mklong accum k =
      if k <= 0 then accum
      else mklong (k :: accum) (k - 1);;
val mklong : int list -> int -> int list = <fun>
# let long = mklong [] 100_000_000;;
val long : int list =
  [1; 2; 3; 4; 5; ...]
# let long_pairs =
    zip_tr (fun _ -> failwith "length mismatch")
           (fun x -> x) long long;;
val long_pairs : (int * int) list =
  [(1, 1); (2, 2); (3, 3); (4, 4); (5, 5); ...]
# List.length long_pairs;;
- : int = 100000000

Если вы измените свой код так, чтобы вызов sc не былхвостовой вызов:

zip_tr fc (fun l -> (h1, h2): sc l) t1 t2

Он генерирует результат в обратном порядке, но также не работает для длинных списков:

# zip_tr (fun _ -> failwith "length mismatch")
         (fun x -> x) [1;2] [3;4];;
- : (int * int) list = [(2, 4); (1, 3)]

# zip_tr (fun _ -> failwith "length mismatch")
         (fun x -> x) long long;;
Stack overflow during evaluation (looping recursion?).

Я недостаточно знаю о генерации кода OCamlчтобы объяснить это подробно, но это предполагает, что ваш код действительно является рекурсивным. Однако возможно, что это зависит от реализации замыканий. Для другой реализации, возможно, сгенерированные вычисления для sc будут занимать большой объем стека. Может быть, это то, что вам говорят.

Answer 2

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

К счастью, ваши продолжения также хвост-рекурсивны, поскольку результат одного вызова sc напрямую дает результат анонимного закрытия. Это объясняет, почему у вас нет переполнения стека при тестировании.

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

Преимущество этого подхода состоит в том, что продолжение успеха вызывается только тогда, когда известно, что оба ваших списка имеют одинаковый размер;в целом, компиляция кода в продолжения - это то, что интересно знать при работе с языками (поэтому ваши усилия не будут потрачены впустую).

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