From d92a26fc9be92fb269888947a8b26aa12883065e Mon Sep 17 00:00:00 2001 From: bringert Date: Wed, 30 Nov 2005 18:57:23 +0000 Subject: Added monad isntances for List and Maybe. --- transfer/lib/list.tr | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-) (limited to 'transfer/lib/list.tr') diff --git a/transfer/lib/list.tr b/transfer/lib/list.tr index 079208167..da3bcc516 100644 --- a/transfer/lib/list.tr +++ b/transfer/lib/list.tr @@ -1,3 +1,4 @@ +import prelude import nat data List : (_:Type) -> Type where @@ -13,5 +14,18 @@ map _ B _ (Nil _) = Nil B map A B f (Cons _ x xs) = Cons B (f x) (map A B f xs) append : (A:Type) -> (xs:List A) -> List A -> List A -append _ (Nil _) ys = ys -append A (Cons _ x xs) ys = Cons A x (append A xs ys) +append A xs ys = foldr A (List A) (Cons A) ys xs + +concat : (A : Type) -> List (List A) -> List A +concat A = foldr (List A) (List A) (append A) (Nil A) + +foldr : (A : Type) -> (B : Type) -> (A -> B -> B) -> B -> List A -> B +foldr _ _ _ x (Nil _) = x +foldr A B f x (Cons _ y ys) = f y (foldr A B f x ys) + +-- Instances: + +monad_List : Monad List +monad_list = rec return = \A -> \x -> Cons A x (Nil A) + bind = \A -> \B -> \m -> \k -> concat B (map A B k m) + -- cgit v1.2.3