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

Question

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

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

Я пытаюсь получить список элементов от меня до 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), потому что это - такая довольно общая операция..

10

list ocaml

задан Michael Le Barbier Grünewald 11 March 2016 в 18:14

3 ответа

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

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

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

2

ответ дан 3 December 2019 в 20:40

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

6

ответ дан 3 December 2019 в 20:40

Другие вопросы по тегам:

list ocaml

Похожие вопросы:

score 10 · Accepted Answer

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