How do we combine drop n elements from a list and take n elements from a list?-CodePudding

We can create function that take n elements from a list, and drop n elements from a list, as the following:

   let rec take n l = 
       if n = 0 then [] else 
          match l with 
              h::t -> h::take(n-1) t

Similarily,

   let rec drop n l = 
       if n = 0 then l else 
          match l with 
              h::t -> drop(n-1) t

But how do we combine take and drop function such that it returns a pair with the result of dropping n elements and adding n elements from a list l?

CodePudding user response：

   let rec add_drop n l = 
       if n = 0 then ([],l) else 
          match l with 
              h::t -> let (a,b) = add_drop (n-1) t in 
              (h::a, b)

CodePudding user response：

This is also available in ocaml-containers as take_drop:

val take_drop : int -> 'a t -> 'a t * 'a t

And in Jane Street's Base as split_n

val split_n : 'a t -> int -> 'a t * 'a t

CodePudding user response：

I'd use a tail-recursive approach, with a helper function that builds up the first N elements in an extra argument, originally in reverse order, and then reversing that list before returning it. That way it takes the same stack space no matter how big N is.

let split n lst =
  let rec helper n lst head =
    if n = 0 then
      head, lst
    else
      match lst with
      | car :: cdr -> helper (n - 1) cdr (car :: head)
      | [] -> head, [] (* List is shorter than n *) in
  let head, tail = helper n lst [] in
  List.rev head, tail