Specifikacija in abstrakcija

Naloga: sklad

V jeziku OCaml želimo definirati podatkovno strukturo sklad.

Podnaloga: Definirajte signaturo STACK, ki obsega tipe elementov, sklada in naslednjih vrednosti:

• prazen sklad empty;
• funkcijo push, ki sprejme element in sklad ter vrne nov sklad z dodanim elementom;
• funkcijo pop, ki sprejme sklad in vrne par (nazadnje dodani element, preostanek sklada).

Podnaloga: Definirajte funktor ListStack, ki sprejme tip t in vrne implementacija sklada, ki elemente tipa t hrani v seznamu.

Rešitev

module type STACK =
sig
    type element
    type stack
    val empty : stack
    val push : element -> stack -> stack
    val pop : stack -> element option * stack
end

module ListStack(M : sig type t end) : STACK =
struct
    type element = M.t
    type stack = element list
    let empty = []
    let push x s = x::s
    let pop = function [] -> None, [] | x::s -> Some x, s
end