// implementation of queue using two lists
type queue <T> = { front:list< T >, back:list< T > }
function from_list <T> (front: list< T >): queue< T > { { front:front, back:#[] } }
function is_empty <T> (q: queue< T >): bool {
match q {
| {front:#[] , back:#[]} => true
| _ => false
}
}
function list_rev <T> (xs: list< T >): list< T > {
fn go (acc, xs: list< T >) {
match xs {
| #[] => acc
| #[x, ...rest] => go(#[x, ...acc], rest)
}
}
go(#[], xs)
}
function norm <T> (q: queue< T >): queue< T > {
match q {
| {front:#[] , back:b} => { front:list_rev(b), back:#[] }
| q => q
}
}
function enqueue <T> (q: queue< T >, x: T): queue< T > {
match q {
| {front:f , back:b} => norm({ front:f, back:#[x, ...b] })
}
}
function peek <T> (q: queue< T >): option< T > {
match q {
| {front:#[] , back:_} => None
| {front:#[x, ..._] , back:_} => Some(x)
}
}
function dequeue <T> (q: queue< T >): option< queue< T > > {
match q {
| {front:#[] , back:_} => None
| {front:#[_, ...f] , back:b} => Some({ front:f, back:b })
}
}
function init {
let q1 = from_list(#[1, 2, 3]);
match peek(q1) {
| Some(x) => output_int(x)
| None => output_string("error")
};
let Some(q2) = dequeue(q1);
match peek(q2) {
| Some(x) => output_int(x)
| None => output_string("error")
}
}