-- Haskell Introduction
-- Jost Berthold, VL Par. in fkt. Spr.
--
-- Types.hs
--------------------------------------


-- wir definieren ein Modul, das wir hinterher auch in 
-- andere Programme importieren können: "import Types"
-- Die Schnittstelle ist hier "alles", kann auch explizit angegeben werden.

module Types where

-- Syntax:

-- Kommentare bis Zeilenende mit Doppel-Minus 

{- mehrzeilige oder begrenzte Kommentare: 
   geschweifte Klammern mit Minus 
 -}

{- 
Variablen:

    werden nur einmal definiert !!! (anders als in imperativen Sprachen)

und fangen mit Kleinbuchstaben an. 
Datentypen (und Typklassen) fangen mit Großbuchstaben an.
-}
-- Zeichen und Zeichenketten
zeichen :: Char
zeichen = 'z'

zeichenkette :: String -- String = [Char]
zeichenkette = "Dies ist ein String"

-- ganze Zahlen
zahl :: Int
zahl = 42

zahl2 :: Integer
zahl2 = 10 ^ 1000 -- (potenzieren)

{-  Haskell ist streng typisiert:

   HUGS:

Types> zahl `div` zahl2
ERROR - Type error in application
*** Expression     : zahl `div` zahl2
*** Term           : zahl
*** Type           : Int
*** Does not match : Integer

Types> fromInt zahl `div` zahl2
42
-}

-- "Fractional": Gleitkommazahlen
frac :: Float
frac = (fromIntegral zahl) / 3.2

dbl :: Double
dbl = realToFrac (frac ** frac) -- type error ohne die Konvertierungsfunktion

-- Datenstrukturen:
-- Listen sind das Grundmuster für Datenstrukturen in funktionalen Sprachen:

eineListe :: [Integer]
eineListe = [1,2,3] -- einfache Aufzählung

nocheineListe :: [Char]
nocheineListe = 'x':'y':[] -- Definition mit Konstruktoren ":" und "[]"

-- Listen konkatenieren und modifizieren
dritteListe :: [Integer]
dritteListe = [10,9..4] ++ reverse eineListe


-- auf Listen sind bestimmte Operationen vordefiniert, die häufig auftreten:
--   Anwenden einer Funktion auf alle Elemente einer Liste: *map*
vierteListe :: [Float]
vierteListe = map fromIntegral dritteListe

-- andere Operation: Faltung (fold), hier nur eine der Varianten:

summe = foldr (+) 0 vierteListe

-- nun aber genauer zu den "Funktionen" im funktionalen Programmieren:
-- Bisher haben wir konstante *Funktionen* definiert (nicht bloß Konstanten).
-- Wir definieren eine Funktion mit Argumenten vom Typ Int und "Liste von Float"

func :: Int -> [Float] -> [Float] -- die Typangabe, kann man auch weglassen, s.u.

-- Die Funktion soll alle Elemente der Liste (Param.2) mit Param.1 multiplizieren. 
--        Ergebnis: eine neue Liste von Float-Zahlen (klar!)
--  Dabei wird Rekursion als Kontrollstruktur eingesetzt.

func x y =  if (length y == 0) 
	       then [] 
	       else z:zs
	 where -- lokale Definitionen
	  z  = fromIntegral x * head y
          zs = func x (tail y) -- Rekursion zur Realisierung von "Schleifen"

------------------------------------------------------
{- Typklassen und Typvariablen:
   ----------------------------
--Statt eines genauen Typs kann man in der Typangabe auch Variablen benutzen.

func' :: a -> [b] -> [b]
func' x y =  if (length y == 0) 
	       then [] 
	       else z:zs
	 where
	  z  = fromIntegral x * head y
          zs = func x (tail y)


 In diesem Beispiel muss man dazu aber Typklassen benutzen.
Typklassen dienen dazu, Funktionen gleich auf mehreren Instanzen zu definieren,
z.B. überall da, wo ein (*) definiert ist (Klasse Num) bzw. Klassen 
  Integral (ganze Zahl) und Fractional (Gleitkommazahl)
Statt eines konkreten Typs gibt man abstrakt an, welchen Klassen die benutzten Typen 
angehören müssen.
-}

func2 :: (Integral a, Fractional b) => a -> [b] -> [b] -- ganze Zahlen von Typ a, Gleitkommazahlen vom Typ b
func2 x y = if (y == []) 
	       then [] 
	       else z:zs
	 where
	  z  = fromIntegral x * head y
          zs = func2 x (tail y) -- Rekursion zur Realisierung von "Schleifen"

-- andere Syntax:
func2' x y | y == []   = []
	   | otherwise = z:zs
	 where
	  z  = fromIntegral x * head y
          zs = func2' x (tail y) -- Rekursion zur Realisierung von "Schleifen"

-- das ganze sieht wesentlich schöner aus, wenn man "Pattern Matching" benutzt:
func3 x [] = []
func3 x (y:ys) = (fromIntegral x * y) : (func3 x ys)

head' [] = error "leer"
head'  (z:_) = z -- "_" bezeichnet in der Def. "unnötige", aber vorhandene Elemente


-- am einfachsten aber mit dem vordefinierten map:
func4 x = map (* fromIntegral x)

{- 
   Typinferenz: 
   ------------
Hugs und GHC inferieren den Typ der Funktion, wenn er nicht angegeben (eingeschränkt) ist.
In diesem Beispiel tun func, func2, func2' und func3 offenbar das gleiche, aber mit unterschiedlichem Typ:

    HUGS:
    -----
Types> :t func2'
func2' :: (Num a, Integral b) => b -> [a] -> [a]
Types> :t func3
func3 :: (Integral a, Num b) => a -> [b] -> [b]
Types>

   Nochmal zu den Typklassen:
   --------------------------
Typklassen fassen Typen mit gleichartigen Operationen zusammen, hier etwa +,-,*, negate,... 
Sie werden mit Typen *instanziert*, wobei entweder der Default, oder eine eigene
Definition für die Operatoren gilt ("überladen").

       HUGS:
       -----
Types> :i Num
-- type class
infixl 6 +
infixl 6 -
infixl 7 *
class (Eq a, Show a) => Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
  fromInt :: Int -> a

-- instances:
instance Num Int
instance Num Integer
instance Num Float
instance Num Double
instance Integral a => Num (Ratio a)

----------------------------------
-}

--Man kann weitere Instanzen definieren, wenn man die nötigen Funktionen bereitstellt:

instance Num Char where
      (+) a b = a
      (-) a b = b
      (*) a b = maximum [a,b]
      negate a = a
      abs a = a
      signum a = a
      fromInteger _ = '%'

{- 
diese Definitionen machen natürlich hier keinen Sinn...
        HUGS:
	-----
Types> fromInteger 32 :: Char
'%'
Types> fromInteger 32 :: Float
32.0
Types>
-}
----------------------------------------------------------------
-- eigene Typen und Klassen, rekursive Strukturen:

type Zahl = Int -- nur Synonym

data Baum = Blatt | Knoten Baum Baum -- algebraischer Typ "Binaerbaum" (ohne Inhalt)

data Zahlbaum = Bl Zahl | Kn Zahlbaum Zahlbaum -- Binaerbaum mit Int-Inhalten
	      deriving Show -- zum Anzeigen (Defaults für Anzeige benutzen)

data Tree a = Leaf a | Node (Tree a) (Tree a) -- generischer Binaerbaum, Inhalte vom Typ a

-- Beispielbaum:
infiniteTree :: Zahlbaum
infiniteTree = Kn infiniteTree infiniteTree
-- Welche Zahlen enthalten die Blätter in diesem Baum ??

-- das rekursive Definieren geht auch mit Listen:
noEnd :: [Zahl]
noEnd = 42:noEnd

-- fuer Listen finden sich sinnvolle Anwendungen: hier Primzahlenliste nach Eratosthenes
primes :: [Integer]
primes = 2 : oddPrimesFrom 3
         where oddPrimesFrom n | isPrime n primes = n : oddPrimesFrom (n+2) -- greift auf eigenes Ergebnis zu !
                               | otherwise        =     oddPrimesFrom (n+2)

isPrime :: Integer -> [Integer] -> Bool
isPrime n (l1:ls) | n < l1*l1        = True
                  | n `mod` l1 == 0  = False
                  | otherwise        = isPrime n ls

-- z.B.: Primzahl Nr. 8000 ausgeben:
-- Types>primes !! 8000
-- .... (ca. 40 sec mit Hugs auf Linux - aber nur beim ersten Aufruf!)
----------------------------------------------------------------