Take and Drop

Splitting a list

take and drop divide a list into two parts at a given index i. Given a list xs = [x₀, ..., xᵢ₋₁, xᵢ, ..., xₙ₋₁], take i xs returns the first i elements while drop i xs returns everything from position i onwards.

Both functions share the same type signature:

int -> 'a list -> 'a list

take

take copies the first i elements into a new list. It is not tail-recursive, but making it iterative would not improve its efficiency: copying i elements inherently requires O(i) time and space.

let rec take i = function
  | [] -> []
  | x::xs ->
      if i > 0 then x :: take (i - 1) xs
      else []

Property	Value
Time complexity	O(i)
Space complexity	O(i)
Tail-recursive?	No

drop

drop simply skips over the first i elements. It is tail-recursive and uses only O(1) space.

let rec drop i = function
  | [] -> []
  | x::xs ->
      if i > 0 then drop (i-1) xs
      else x::xs

Property	Value
Time complexity	O(i)
Space complexity	O(1)
Tail-recursive?	Yes

Although both are O(i) in time, drop is much faster than take in practice because skipping elements is cheaper than copying them: drop has a smaller constant factor.

Applications

take and drop are used throughout the course for divide-and-conquer algorithms. A common pattern: divide a list into two roughly equal halves for recursive processing, as seen in mergesort where the input is split at the midpoint using take and drop.