FFP A4-2

1 files changed, 35 insertions, 7 deletions

diff --git a/ws2015/FFP/blaetter/04/FFP_U04_Lazy.hs b/ws2015/FFP/blaetter/04/FFP_U04_Lazy.hs
index 71c3045..8051ef9 100644
--- a/ws2015/FFP/blaetter/04/FFP_U04_Lazy.hs
+++ b/ws2015/FFP/blaetter/04/FFP_U04_Lazy.hs
@@ -13,10 +13,11 @@
 --  
 --
 
-import Data.Map as Map
-import Data.Set as Set
-
-
+import qualified Data.Map as Map
+import Data.Map (Map)
+import qualified Data.Set as Set
+import Data.Set (Set)
+import qualified Data.List as List
 
 ---- A4-1 Verzögerte Auswertung
 -- Gegeben ist folgendes Programm:
@@ -111,10 +112,24 @@ rs = <70>
 -- HINWEIS: Folgen Sie dem nub2 Beispiel aus Folie 3-30
 
 
-transCl :: (Eq a) => (a -> [a]) -> [a] -> [a]
-transCl r xs =  undefined -- !!! TODO !!!
+transCl :: Eq a => (a -> [a]) -> [a] -> [a]
+transCl r xs = res
+  where
+    res = build xs 0
+    
+    build [] _ = []
+    build xs n = xs' ++ build xs' (n + length xs')
+      where
+        xs' = strikeKnown n $ concatMap r xs
+
+    strikeKnown _ [] = []
+    strikeKnown 0 xs = xs
+    strikeKnown n (x:xs)
+      | x `elem` take n res = strikeKnown n xs
+      | otherwise = x : strikeKnown n xs
 
 -- Zum Testen:
+rel1 :: Integer -> [Integer]
 rel1 11                 = [22]
 rel1 22                 = [33]
 rel1 33                 = [44]
@@ -123,10 +138,17 @@ rel1 n
   | odd n,  n>=1, n<=9 = [1,3,5,7,9]
   | otherwise          = [n]
 
+rel1S :: Integer -> Set Integer
+rel1S = Set.fromList . rel1
+
+rel2 :: Integer -> [Integer]
 rel2 n
   | even n    = [n,n `div` 2]
   | otherwise = [3*n+1,n]
 
+rel2S :: Integer -> Set Integer
+rel2S = Set.fromList . rel2
+
 
 -- b)
 -- Implementieren Sie die Aufgabe noch mal ganz schnell
@@ -134,7 +156,13 @@ rel2 n
 -- sondern ganz bequem mit der Standardbibliothek für Data.Set
 
 transClS :: (Ord a) => (a -> Set a) -> Set a -> Set a
-transClS rel set = undefined -- !!! TODO !!!
+transClS rel xs = build xs Set.empty
+  where
+    build xs known
+      | Set.null xs = Set.empty
+      | otherwise   = xs' `Set.union` build xs' (xs' `Set.union` known)
+      where
+        xs' = Set.foldr Set.union Set.empty (Set.map rel xs) Set.\\ known