как получить подсписок из списка в ocaml

Question

Я смотрю на список документации. Кажется, библиотека не предоставляет функцию sublist.

Я пытаюсь получить список элементов от i до j . Теперь я должен написать это как:

let rec sublist list i j =
  if i > j then
    []
  else
    (List.nth list i) :: (sublist list (i+1) j)

, что довольно кратко, но я подвергаю сомнению эффективность List.nth, потому что, если это O (n) , я бы предпочел написать его менее лаконичным образом.

Мне интересно, почему они не предоставили List.sublist func, если List.nth не O (1) , потому что это довольно распространенная операция ..

Answer 1

let rec sublist b e l = 
  match l with
    [] -> failwith "sublist"
  | h :: t -> 
     let tail = if e=0 then [] else sublist (b-1) (e-1) t in
     if b>0 then tail else h :: tail
;;

sublist 3 5 [1;2;3;4;5;6;7;8;9] ;;
- : int list = [4; 5; 6]

Вышесказанное является более или менее вырубленной версией решения newacct. Решение newacct выделяет промежуточный список (drop i list), который может быть оптимизирован компилятором в Haskell, но намного сложнее в ML. Поэтому его версия идеально подходит для функции Хаскелла и несколько неоптимальна для функции ML. Разница между ними только постоянный фактор: оба O (e). Версия zrr - O (length (l)), поскольку List.filteri не знает, что f возвращает только false через некоторое время, она вызывает его для всех элементов в l.

Я не очень рад, что b становится отрицательным, но версия, где это не так, более сложна.

Один из многих примеров обезлесения, если вы заинтересованы: http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

Answer 2

Попробуйте сначала написать функции take (первые n элементов) и drop (все, кроме первых n элементов) (как в Haskell). Тогда sublist i j lst это просто take (j-i) (drop i lst)

Answer 3

Это немного сложнее, чем должно быть со стандартной библиотекой OCaml - стандартная библиотека немного разрежена. Если вы используете одну из расширенных стандартных библиотек, это станет проще. Например, в Core вы можете написать:

let sublist list low high =
   List.filteri l ~f:(fun i _ -> i >= low && pos < high)

Я думаю, что нечто подобное возможно с extlib / battery.

Answer 4

Хотя в ответе, представленном Паскалем, реализован хороший кандидат на List.sublist, правильный ответ заключается в том, что вам, вероятно, лучше использовать массив списка. Модули Array реализуют функцию Array.sub, которую вы можете использовать.

Хотя во многих императивных языках, таких как C ++ или Perl, по существу нет различий между списками и массивами, это не то же самое в OCaml, где:

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

• Массивы лучше подходят для произвольного доступа, изменения структуры (например, сортировки) или для численных расчетов.