Существует ли функция OCaml для определения того, находится ли каждый элемент целочисленного списка в последовательном порядке?

Question

Например, я хотел бы вернуть true со списком [1; 2; 3; 4], но не [1; 3; 4; 5].

Я пробовал это до сих пор. Я считаю, что это работает на основе моих тестовых случаев до сих пор ... но если у кого-то есть отзывы или советы, это было бы здорово. По сути, я не уверен, как реализовать это с помощью встроенной библиотеки списков, которая, как я знаю, работает более эффективно, чем жестко закодированные действия. Может ли это быть реализовано с помощью fold_left или fold_right?

let is_seq elt1 elt2 =
  if elt2 - elt1 = 1 then true else false

let next_elem lst = 
  match lst with 
  | [] -> failwith "this should not happen"
  | h :: t -> h

(**[is_sequential lst] returns true if the list is sequential and 
   false if it is not *)
let rec is_sequential lst =
  match lst with
  | [] -> true
  | h :: [] -> true
  | h :: t -> if is_seq h (next_elem t) then is_sequential t else false

Answer 1

Таким образом, мое предложение для fold_left будет иметь аккумулятор, который содержит ранее встреченное целое число:

let is_sequential l = 
  match l with 
  | [] -> true 
  | x::xs -> 
     List.fold_left (fun (is_seq,prev_e) e -> (e = prev_x + 1 && is_seq,e)) (true,x) xs

Вы также можете использовать исключения для остановки, когда is_seq становится ложным ...

Answer 2

Я не уверен, как вы справляетесь с переполнением int ..

let rec is_seq lst =
  match lst with
  | [] -> true
  | hd::[] -> true
  | hd1::hd2::tl when hd1 = Int.max_int -> failwith "Int too large to continue"
  | hd1::hd2::tl when (succ hd1) = hd2 -> is_sorted (hd2::tl)
  | _ -> false