We've implemented stacks and queues with lists now! The only difference in our data structures themselves is our use of exceptions and options.
module ListStack = struct
type 'a stack = 'a list
let empty = []
let push x s = x :: s
let peek = function
| [] -> failwith "Empty"
| x :: _ -> x
let pop = function
| [] -> failwith "Empty"
| _ :: s -> s
end
module ListQueue = struct
type 'a queue = 'a list
let empty = []
(* use the append operator to put it at the end of the list *)
(* linear time :'( *)
let enqueue x q = q @ [x]
let dequeue = function
| [] -> None
| _ :: t -> Some t
let peek = function
| [] -> None
| h :: _ -> Some h
end
module ListStack :
sig
type 'a stack = 'a list
val empty : 'a list
val push : 'a -> 'a list -> 'a list
val peek : 'a list -> 'a
val pop : 'a list -> 'a list
end
module ListQueue :
sig
type 'a queue = 'a list
val empty : 'a list
val enqueue : 'a -> 'a list -> 'a list
val dequeue : 'a list -> 'a list option
val peek : 'a list -> 'a option
end
Exceptions make it easy to pipeline operators! You can just keep adding operations as you go.
ListStack.(empty |> push 42 |> pop |> push 43)
- : int list = [43]
Options make that a bit trickier.
ListQueue.(empty |> enqueue 42 |> dequeue |> enqueue 43)
File "[3]", line 1, characters 45-55:
1 | ListQueue.(empty |> enqueue 42 |> dequeue |> enqueue 43)
^^^^^^^^^^
Error: This expression has type int list -> int list
but an expression was expected of type int list option -> 'a
Type int list is not compatible with type int list option
Uh oh... We get a type checking error because dequeue returned an option, while enqueue expected an int list, not an int list option.
One way to fix this would be to write a new pipeline operator to deal with this. Recall the definition of the pipeline operator:
let ( |> ) x f = f x
let ( >>| ) opt f =
match opt with
| None -> None
| Some x -> Some (f x)
val ( >>| ) : 'a option -> ('a -> 'b) -> 'b option = <fun>
This is under the standard library as Option.map.
ListQueue.(empty |> enqueue 42 |> dequeue >>| enqueue 43)
- : int list option = Some [43]
What if we wanted to dequeue after that?
ListQueue.(empty |> enqueue 42 |> dequeue >>| enqueue 43 |> dequeue)
File "[6]", line 1, characters 60-67:
1 | ListQueue.(empty |> enqueue 42 |> dequeue >>| enqueue 43 |> dequeue)
^^^^^^^
Error: This expression has type 'a list -> 'a list option
but an expression was expected of type int list option -> 'b
Type 'a list is not compatible with type int list option
ListQueue.(empty |> enqueue 42 |> dequeue >>| enqueue 43 >>| dequeue)
- : int list option option = Some (Some [])
Well now we have a double option. That's not right, let's write a new pipeline operator to fix it.
(* Option.bind *)
let ( >>= ) opt f =
match opt with
| None -> None
| Some x -> f x
val ( >>= ) : 'a option -> ('a -> 'b option) -> 'b option = <fun>
ListQueue.(empty |> enqueue 42 |> dequeue >>| enqueue 43 >>= dequeue)
- : int list option = Some []