Функция для объединения последовательностей без использования добавления

Question

Я хочу написать функцию, которая разбивает последовательность пар на пару последовательностей, вот код:

let uncombine s = 
  let rec ayx s1 s2 sr = 
    match s () with 
    | Nil -> s1, s2
    | Cons(((e1, e2), sr) ->  aux  (append s1 (singleton e1)) (append s2 (s(singleton e2)) sr 
  in aux nil nil

Я хочу сделать это без использования append (не рекурсивная терминальная функция) из-за сложности.

Answer 1

Я думаю, что вы хотите сделать следующее:

let uncombine s =
  let rec aux sr =
    match sr with
    | Nil -> Nil, Nil
    | Cons ((e1, e2), sr) ->
      let s1, s2 = aux sr in
      Cons (e1, s1), Cons (e2, s2)
  in
  aux (s ())

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