Übung 03

Dateiinhalt

-- | Functional Programming, course at LMU, summer term 2012
--   Andreas Abel and Steffen Jost
--
-- Exercise sheet 3, 2012-05-10
--
-- Instructions:
--
-- Replace all occurrences of 'undefined' and 'Undefined' by sensible code.
-- Do not change the type of functions you are asked to implement!
--
-- Submit your solutions via UniWorX.

----------------------------------------------------------------------
-- Header
--
-- You can add imports and LANGUAGE pragmas here.
----------------------------------------------------------------------
------------------------------------------------------------------


module Main where


import Data.List as List
import qualified Data.Set as Set

import Debug.Trace



----------------------------------------------------------------------
-- Exercise 1  "Uendliche Bäume / Collatz-Folge"
-- 
-- Die Collatz-Folge ist definiert durch:
--    falls a_n   gerade ist, dann ist a_(n+1) = a_n `div` 2
--    falls a_n ungerade ist, dann ist a_(n+1) = 3*a_n + 1
-- Siehe http://de.wikipedia.org/wiki/Collatz-Folge
--
-- 1) Definieren Sie eine Funktion, welche die Collatz-Folge für einen gegebenen Startwert berechnet
-- 
-- 2) Es wird vermutet, aber bislang unbewiesen, dass die Collatz-Folge für jeden Startwert irgendwann in den Zyklus [4,2,1] mündet.
--    
-- 3) Definieren Sie den unendlichen Collatz-Baum, welcher bei 1 beginnt und als Nachfolger im Baum jeweils die Vorgänger dieser Zahl in der Collatz-Folge hat.
--
----------------------------------------------------------------------


collatzFolge :: Integer -> [Integer]
collatzFolge n = undefined

data Baum a = Ast a (Baum a) | Gabel a (Baum a) (Baum a)

-- Abgeschnittene show Funktion
showBaum :: (Show a, Num b, Eq b) => b -> Baum a -> [Char]
showBaum 0  _            = " _ "
showBaum n (Ast   w  t ) = "Ast "  ++(show w) ++ " (" ++ (showBaum (n)   t) ++ ")"
showBaum n (Gabel w l r) = "Gabel "++(show w) ++ " (" ++ (showBaum (n-1) l) ++ ")Y(" ++ (showBaum (n-1) r) ++ ")"
  

collatzTree :: Baum Integer
collatzTree = undefined
      

----------------------------------------------------------------------
-- Exercise 2  "Sieve of Erathostenes"
--
-- In der Vorlesung wurde eine Liste aller Primzahlen nach dem 
-- Verfahren "Sieb des Erathostenes" vorgestellt (siehe primes1).
-- Definieren Sie nach dem gleichen Prinzip eine Liste aller 
-- Primzahlen als zirkuläre Datenstruktur 
-- (siehe auch Folie 04 aus Kapitel 07 "Zirkuläre Programme"
--  
----------------------------------------------------------------------

primes1 :: [Integer]
primes1 = sieve [2..]

turnerdiv :: [Integer] -> [Integer]
turnerdiv (p:xs) = p : turnerdiv [x | x <-xs , x `mod` p /=0] -- Turners Trial Division; ineffizient, folgt NICHT dem Sieb des Erathosthenes

sieve (p:xs) = p : sieve (xs `minus` [p,p+p..])  -- akkurate Version, welche vielfache entfernt.
  
minus xs@(x:xt) ys@(y:yt)         -- Data.List.(\\) ist nicht produktiv
  | LT == cmp = x : minus xt ys
  | EQ == cmp =     minus xt yt
  | GT == cmp =     minus xs yt
 where
   cmp = compare x y 

primes2 = undefined -- es gibt mehrere Möglichkeiten
   

 ----------------------------------------------------------------------
-- Exercise 3
-- 
-- Schreiben eine Funktion, welche für einen Strom von Double-Werten glättet
-- (also eine unendliche Liste)
-- 
-- "averaging n xs" liefert einen Strom zurück, bei dem jedes Element
-- den Durschnitswert des Elements und seinen (n-1) Nachfolgerelementen 
-- im ursprünglichen Strom ist.
--
----------------------------------------------------------------------     

averaging :: Int -> [Double] -> [Double]
averaging n xs = undefined


-- Beispiel: averaging 3 [1,2,3,4,..] =[(1+2+3)/3,(2+3+4)/3,(3+4+5)/3,...]

----------------------------------------------------------------------
-- Exercise 4
-- 
-- Schreiben Sie ein zirkuläres Programm transcl,
-- welches zu einer gegebenen Relation r :: a -> [a] 
-- und einer als Liste gegebenen Menge, 
-- die transitive Hülle dieser Menge zu der Relation berechnet.
-- 
-- Eine Relation r :: a -> [a] ist dabei so kodiert, 
-- das r x die Menge aller Elemente ist, welche zu x in Relation stehen.
--
----------------------------------------------------------------------

transcl :: (Eq a) => (a -> [a]) -> [a] -> [a]
transcl r xs = undefined