adamc@794: datatype t = datatype Basis.list
adamc@794:
adamc@826: val show = fn [a] (_ : show a) =>
adamc@826: let
adamc@826: fun show' (ls : list a) =
adamc@826: case ls of
adamc@826: [] => "[]"
adamc@826: | x :: ls => show x ^ " :: " ^ show' ls
adamc@826: in
adamc@826: mkShow show'
adamc@826: end
adamc@794:
adamc@846: val eq = fn [a] (_ : eq a) =>
adamc@846: let
adamc@846: fun eq' (ls1 : list a) ls2 =
adamc@846: case (ls1, ls2) of
adamc@846: ([], []) => True
adamc@846: | (x1 :: ls1, x2 :: ls2) => x1 = x2 && eq' ls1 ls2
adamc@846: | _ => False
adamc@846: in
adamc@846: mkEq eq'
adamc@846: end
adamc@846:
adamc@845: fun foldl [a] [b] f =
adamc@845: let
adamc@845: fun foldl' acc ls =
adamc@845: case ls of
adamc@845: [] => acc
adamc@845: | x :: ls => foldl' (f x acc) ls
adamc@845: in
adamc@845: foldl'
adamc@845: end
adamc@845:
adamc@850: fun foldlAbort [a] [b] f =
adamc@846: let
adamc@850: fun foldlAbort' acc ls =
adamc@846: case ls of
adamc@846: [] => Some acc
adamc@846: | x :: ls =>
adamc@846: case f x acc of
adamc@846: None => None
adamc@850: | Some acc' => foldlAbort' acc' ls
adamc@846: in
adamc@850: foldlAbort'
adamc@846: end
adamc@846:
adamc@826: val rev = fn [a] =>
adamc@826: let
adamc@826: fun rev' acc (ls : list a) =
adamc@826: case ls of
adamc@826: [] => acc
adamc@826: | x :: ls => rev' (x :: acc) ls
adamc@826: in
adamc@826: rev' []
adamc@826: end
adamc@794:
adamc@850: fun foldlMapAbort [a] [b] [c] f =
adamc@850: let
adamc@850: fun foldlMapAbort' ls' acc ls =
adamc@850: case ls of
adamc@850: [] => Some (rev ls', acc)
adamc@850: | x :: ls =>
adamc@850: case f x acc of
adamc@850: None => None
adamc@850: | Some (x', acc') => foldlMapAbort' (x' :: ls') acc' ls
adamc@850: in
adamc@850: foldlMapAbort' []
adamc@850: end
adamc@850:
adamc@826: val revAppend = fn [a] =>
adamc@826: let
adamc@826: fun ra (ls : list a) acc =
adamc@826: case ls of
adamc@826: [] => acc
adamc@826: | x :: ls => ra ls (x :: acc)
adamc@826: in
adamc@826: ra
adamc@826: end
adamc@821:
adamc@826: fun append [a] (ls1 : t a) (ls2 : t a) = revAppend (rev ls1) ls2
adamc@821:
adamc@826: fun mp [a] [b] f =
adamc@794: let
adamc@794: fun mp' acc ls =
adamc@794: case ls of
adamc@794: [] => rev acc
adamc@794: | x :: ls => mp' (f x :: acc) ls
adamc@794: in
adamc@794: mp' []
adamc@794: end
adamc@796:
adamc@826: fun mapPartial [a] [b] f =
adamc@821: let
adamc@821: fun mp' acc ls =
adamc@821: case ls of
adamc@821: [] => rev acc
adamc@821: | x :: ls => mp' (case f x of
adamc@821: None => acc
adamc@821: | Some y => y :: acc) ls
adamc@821: in
adamc@821: mp' []
adamc@821: end
adamc@821:
adamc@826: fun mapX [a] [ctx ::: {Unit}] f =
adamc@796: let
adamc@796: fun mapX' ls =
adamc@796: case ls of
adamc@796: [] =>
adamc@796: | x :: ls => {f x}{mapX' ls}
adamc@796: in
adamc@796: mapX'
adamc@796: end
adamc@800:
adamc@826: fun mapM [m ::: (Type -> Type)] (_ : monad m) [a] [b] f =
adamc@800: let
adamc@800: fun mapM' acc ls =
adamc@800: case ls of
adamc@818: [] => return (rev acc)
adamc@818: | x :: ls => x' <- f x; mapM' (x' :: acc) ls
adamc@800: in
adamc@818: mapM' []
adamc@800: end
adamc@821:
adamc@830: fun mapXM [m ::: (Type -> Type)] (_ : monad m) [a] [ctx ::: {Unit}] f =
adamc@830: let
adamc@830: fun mapXM' ls =
adamc@830: case ls of
adamc@830: [] => return
adamc@830: | x :: ls =>
adamc@830: this <- f x;
adamc@830: rest <- mapXM' ls;
adamc@830: return {this}{rest}
adamc@830: in
adamc@830: mapXM'
adamc@830: end
adamc@830:
adamc@826: fun filter [a] f =
adamc@821: let
adamc@821: fun fil acc ls =
adamc@821: case ls of
adamc@821: [] => rev acc
adamc@821: | x :: ls => fil (if f x then x :: acc else acc) ls
adamc@821: in
adamc@821: fil []
adamc@821: end
adamc@822:
adamc@826: fun exists [a] f =
adamc@822: let
adamc@822: fun ex ls =
adamc@822: case ls of
adamc@822: [] => False
adamc@822: | x :: ls =>
adamc@822: if f x then
adamc@822: True
adamc@822: else
adamc@822: ex ls
adamc@822: in
adamc@822: ex
adamc@822: end
adamc@822:
adamc@826: fun foldlMap [a] [b] [c] f =
adamc@822: let
adamc@822: fun fold ls' st ls =
adamc@822: case ls of
adamc@822: [] => (rev ls', st)
adamc@822: | x :: ls =>
adamc@822: case f x st of
adamc@822: (y, st) => fold (y :: ls') st ls
adamc@822: in
adamc@822: fold []
adamc@822: end
adamc@839:
adamc@839: fun search [a] [b] f =
adamc@839: let
adamc@839: fun search' ls =
adamc@839: case ls of
adamc@839: [] => None
adamc@839: | x :: ls =>
adamc@839: case f x of
adamc@839: None => search' ls
adamc@839: | v => v
adamc@839: in
adamc@839: search'
adamc@839: end
adamc@839:
adamc@840: fun foldlM [m] (_ : monad m) [a] [b] f =
adamc@840: let
adamc@840: fun foldlM' acc ls =
adamc@840: case ls of
adamc@840: [] => return acc
adamc@840: | x :: ls =>
adamc@840: acc <- f x acc;
adamc@840: foldlM' acc ls
adamc@840: in
adamc@840: foldlM'
adamc@840: end
adamc@843:
adamc@843: fun all [m] f =
adamc@843: let
adamc@843: fun all' ls =
adamc@843: case ls of
adamc@843: [] => True
adamc@843: | x :: ls => f x && all' ls
adamc@843: in
adamc@843: all'
adamc@843: end
adamc@844:
adamc@844: fun app [m] (_ : monad m) [a] f =
adamc@844: let
adamc@844: fun app' ls =
adamc@844: case ls of
adamc@844: [] => return ()
adamc@844: | x :: ls =>
adamc@844: f x;
adamc@844: app' ls
adamc@844: in
adamc@844: app'
adamc@844: end
adamc@845:
adamc@845: fun assoc [a] [b] (_ : eq a) (x : a) =
adamc@845: let
adamc@845: fun assoc' (ls : list (a * b)) =
adamc@845: case ls of
adamc@845: [] => None
adamc@845: | (y, z) :: ls =>
adamc@845: if x = y then
adamc@845: Some z
adamc@845: else
adamc@845: assoc' ls
adamc@845: in
adamc@845: assoc'
adamc@845: end
adamc@845:
adamc@845: fun assocAdd [a] [b] (_ : eq a) (x : a) (y : b) (ls : t (a * b)) =
adamc@845: case assoc x ls of
adamc@845: None => (x, y) :: ls
adamc@845: | Some _ => ls