Разделение списка в OCaml

Question

Мне интересно, есть ли возможность разбить список пополам (или вообще на указанный элемент).

Если быть точным, я хотел бы сделать что-то вроде этого: Наличие списка (целых чисел) например):

let ml = [1;2;3;4;5]

Я хотел бы сделать из него два списка с длинами, указанными в аргументе первого списка.

Это будет выглядеть примерно так:

let msl1, msl2 = split_at_point ml 3
(* msl1 = [1;2;3], msl2=[4;5] *)

Если честно, мне все равно, происходит ли разделение в указанной точке c включительно или нет. Все, что меня волнует, - это быстро и экономит память (без копирования было бы здорово). И я знаю, что с точки зрения эффективности лучше всего что-то вроде O (n), где n длина первого списка (результатов).

Answer 1

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

Вторая половина списка не требует копирования, потому что хвост списка - это список .

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

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

В вашем случае у вас есть что-то вроде этого:

let rec split_at_point l n =
    if n = 0 then
        (* Answer is obvious *)
    else
        match l with
        | [] -> (* Answer is obvious *)
        | head :: tail ->
            (* Call split_at_point on the tail and
             * construct your answer
             *)