Übung 03
Lazy Evaluation und zirkuläre Datenstrukturen
03Circular.hs
—
Haskell source code,
4 KB (4302 bytes)
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
Artikelaktionen
abgelegt unter:
FunktionaleProgrammierung,
Übung