Added monad isntances for List and Maybe.

1 files changed, 16 insertions, 2 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)
+