Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Stack Data Type from Purely Function Data Structures.
module type Stack =
sig
type 'a t
val empty : 'a t
val isEmpty : 'a t -> bool
val cons : 'a -> 'a t -> 'a t
val head : 'a t -> 'a
val tail : 'a t -> 'a t
end
module MyStack : Stack = struct
type 'a t = 'a list
exception Empty
let empty = []
let isEmpty l =
match l with
| [] -> true
| _ -> false
let cons x l = x :: l
let head l =
match l with
| h :: _ -> h
| [] -> raise Empty
let tail l =
match l with
| _ :: r -> r
| [] -> raise Empty
end
(*
How do I create a usable Stack of say int from this definition?
I'm thinking something similar to module StringSet = Set.Make(String)
*)
@a-nikolaev

This comment has been minimized.

Copy link

commented May 19, 2014

I think, you don't need a functor here. This code should work just fine creating "stacks" of elements of any type.

Set.Make is a functor because set elements require a function to compare them, so you have to provide a parameter module: Set.Make(Ord). Here, Ord is a simple module that provides the function compare.

A simple example with functors: https://gist.github.com/a-nikolaev/b7aa74c20538e3350c15
It creates sorted lists, the module resembles Set.Make from the standard library.

@tmcgilchrist

This comment has been minimized.

Copy link
Owner Author

commented May 19, 2014

You're right I don't need a functor at all. I was searching for how to bind 'a and didn't know how to specify the type.
Basically I can just go:

# let x = MyStack.cons 3 MyStack.empty;;
val x : int MyStack.t = <abstr>                                                 
# MyStack.head x;;
- : int = 3                                                                  

Thanks for that simple example, finding good OCaml examples is tricky.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.