Как получить дополнительный список из списка в 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. Поэтому его версия отлично подходит для функции Haskell и незначительно неоптимальна для 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

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

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

Я предполагаю, что что-то подобное возможно с помощью удлинителей/батарей.

Answer 3

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

Answer 4

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

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

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

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