Список списка с определенной длиной в OCaml

Question

Мне интересно, как я могу написать функцию: 'a list*int -> 'a list*list, которая преобразует данный список в список списков с заданной максимальной длиной.

Например: segments( [1;2;3;4;5;6;7;8;9], 2 ) => [ [1;2]; [3;4]; [5;6]; [7;8]; [9] ]

Answer 1

Вот хвосто-рекурсивное решение:

let segments xs n = 
    let rec loop n xs (count, elem) acc = 
        match xs with
        | x::xs' when count < n -> loop n xs' (count+1, x::elem) acc
        | x::xs' -> loop n xs' (1, [x]) ((List.rev elem)::acc)
        | [] -> List.rev ((List.rev elem)::acc) in
    loop n xs (0, []) []

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

Answer 2

Улучшенная версия предыдущего правильного ответа (по пэду):

let segments (xs,n) = 
    let rec loop xs (count, elem) acc = 
        match xs with
        | x::xs' when count < n -> loop xs' (count+1, x::elem) acc
        | x::xs' -> loop xs' (1, [x]) ((List.rev elem)::acc)
        | [] -> List.rev ((List.rev elem)::acc) in
    loop xs (0, []) [];;

Answer 3

Я не согласен с тем, что для этого следует использовать BatList. Конечно, это здорово, если вы программируете с людьми, которые привыкли использовать эти библиотеки (возможно, тогда, пожалуйста, игнорируйте это!). Но в «классическом» случае это гораздо более естественно сделать с помощью достаточно простой хвостовой рекурсивной функции. (Вы можете перебрать аппенд, чтобы получить что-то мертвое, тривиальное, но на практике это работает не очень хорошо, и есть гораздо лучшее решение на основе аккумулятора, которое допускает простую реализацию на основе хвостового вызова.)

Answer 4

Это просто: BatList.split_at:

let rec segments list n = 
  try let head, tail = BatList.split_at n list in 
      head :: segments tail n 
  with Invalid_index _ -> [ list ] 

Если у вас нет доступа к батареям, реализовать split_at довольно просто.