# random-access-list.api
# Random Access Lists (due to Chris Okasaki)
#
# -- Allen Leung
# Compiled by:
# src/lib/std/standard.lib# Implemented in:
# src/lib/src/binary-random-access-list.pkg# Random access lists combine list-style head/tail
# access with the ability to efficiently access any
# list element by number.
api Random_Access_List {
Random_Access_List(X);
# O (1) operations
my empty: Random_Access_List(X);
my length: Random_Access_List(X) -> Int;
my null: Random_Access_List(X) -> Bool;
my cons: (X, Random_Access_List(X)) -> Random_Access_List(X);
my head: Random_Access_List(X) -> X;
my tail: Random_Access_List(X) -> Random_Access_List(X);
# O (log n) operations
my get: (Random_Access_List(X), Int) -> X;
my set: (Random_Access_List(X), Int, X) -> Random_Access_List(X);
# O (n) operations
my from_list: List(X) -> Random_Access_List(X);
my to_list: Random_Access_List(X) -> List(X);
# O (n) operations
my map: (X -> Y ) -> Random_Access_List(X) -> Random_Access_List(Y);
my apply: (X -> Void) -> Random_Access_List(X) -> Void;
my fold_forward: ((X, Y) -> Y) -> Y -> Random_Access_List(X) -> Y;
my fold_backward: ((X, Y) -> Y) -> Y -> Random_Access_List(X) -> Y;
};