In Ocaml, is there a way to implement the function pop of a stack?

Instead of using the module Stack, I want to build a pop function by myself.

The function I implemented is:

let pop (stack_lst:stack) = match stack_lst with
  | [] -> None
  | [x] -> x
  | hd::tl -> hd

Soon I realize that my function only gives the top frame, however, my function does not remove the top frame from the stack. In such a sense, the frame still remains. Since OCaml gives me immutable data structure, what should I do?

In addition to my question, my data type is defined as:

location = Obj of int | Null
and
environment = (var * location) list
and
frame = Decl of environment | Call of environment * stack 
and 
stack = frame list

>Solution :

You’d just have to return a new stack without the popped element as well. Additionally, you’re returning an option if the stack is empty, but not in the other branches, which I’ve also fixed here:

let pop (stack_lst: stack) = match stack_lst with
  | [] -> (None, [])
  | [x] -> (Some x, [])
  | hd::tl -> (Some hd, tl)

or

let pop (stack_lst: stack) = match stack_lst with
  | [] -> None
  | [x] -> Some (x, [])
  | hd::tl -> Some (hd, tl)