Added monad isntances for List and Maybe.

3 files changed, 30 insertions, 4 deletions

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)
+
diff --git a/transfer/lib/maybe.tr b/transfer/lib/maybe.tr
index 02d7fe56d..2b7beee9a 100644
--- a/transfer/lib/maybe.tr
+++ b/transfer/lib/maybe.tr
@@ -1,3 +1,5 @@
+import prelude
+
 data Maybe : Type -> Type where
 	Nothing : (A : Type) -> Maybe A
 	Just : (A : Type) -> A -> Maybe A
@@ -8,4 +10,15 @@ fromMaybe _ _ (Just x) = x
 
 maybe : (A : Type) -> (B : Type) -> B -> (A -> B) -> Maybe A -> A
 maybe _ _ x _ Nothing = x
-maybe _ _ _ f (Just x) = f x
\ No newline at end of file
+maybe _ _ _ f (Just x) = f x
+
+-- Instances:
+
+monad_Maybe : Monad Maybe
+monad_Maybe = 
+  rec return = Just
+      bind = \A -> \B -> \m -> \k -> 
+         case m of
+		Nothing _ -> Nothing B
+		Just _ x  -> k x
+
diff --git a/transfer/lib/prelude.tr b/transfer/lib/prelude.tr
index 97336c47f..fb5f724dd 100644
--- a/transfer/lib/prelude.tr
+++ b/transfer/lib/prelude.tr
@@ -327,4 +327,3 @@ return _ d = d.return
 bind : (M : Type -> Type) -> Monad M 
     -> (A : Type) -> (B : Type) -> M A -> (A -> M B) -> M B
 bind _ d = d.bind
-