-- Haskell Introduction
-- Jost Berthold
--
-- 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.

Wir definieren ein paar und geben dabei auch ihre 
Typen (durch "<Var>::<Typ>" ) an:
-}

-- Basistypen: Strings und Zahlen
---------------------------------
zeichen :: Char
zeichen = 'z'

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

-- ganze Zahlen, Standardbereich (OS/HW-abhängig, heute meist 32 bit)
zahl :: Int
zahl = 42

-- ganze Zahlen, beliebig präzise (gmp-basiert)
zahl2 :: Integer
zahl2 = 10 ^ 1000 -- (potenzieren)

{-  Haskell ist streng typisiert:

(auch interessant ist der Überlauf in dieser Rechnung...)

  GHCI 6.4.1 :

*Types> zahl2 `div` zahl

<interactive>:1:12:
    Couldn't match `Integer' against `Int'
      Expected type: Integer
      Inferred type: Int
    In the second argument of `div', namely `zahl'
    In the definition of `it': it = zahl2 `div` zahl
*Types> fromIntegral zahl2 `div` zahl
0
*Types> zahl2 `div` fromIntegral zahl
238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238095238
*Types>           

Hugs hingegen produziert eine Fehlermeldung anstelle eines Überlaufs.

-}

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

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

-- elementare Datenstruktur: Liste
----------------------------------

-- 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

-- Funktionen
-------------
-- nun aber zu den *Funktionen* im funktionalen Programmieren:
-- Bisher haben wir konstante *Funktionen* definiert (nicht bloß Konstanten).
-- Wir definieren eine Funktion mit zwei 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 setzen wir eine Rekursion als Kontrollstruktur ein.

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.
-- -}

-- ganze Zahlen von Typ a, Gleitkommazahlen vom Typ b
func2 :: (Integral a, Fractional b) => a -> [b] -> [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 _ [] = [] -- "_" steht in der Def. für den nicht benötigten ersten Parameter
func3 x (y:ys) = (fromIntegral x * y) : (func3 x ys)

head' [] = error "leer"
head'  (z:_) = z 

-- aber nochmal zurück zu unseren Listen: 

-- auf Listen sind bestimmte Operationen vordefiniert, die häufig auftreten.

--   Anwenden einer Funktion auf alle Elemente einer Liste: *map*
-- Wir erzeugen durch Konvertierung eine Float-Liste aus der Integer-Liste.
vierteListe :: [Float]
vierteListe = map fromIntegral dritteListe

{- ein Merkmal funktionaler Sprachen: Funktionen höherer Ordnung
                                      --------------------------
Die Funktion *map* hat ein Argument, das selbst wieder eine Funktion ist.

Die "andere Variante" der Funktion höherer Ordnung: 
     eine Funktion liefert als Ergebnis eine Funktion zurück.
-}
mal :: Integer -> ( Double -> Double )
-- ... und die Klammern im Typ sind sogar überflüssig (Typ wird rechts geklammert)!
mal x = \d -> d * (fromIntegral x)
-- Die Funktion wird hier als Lambda-Ausdruck beschrieben: "d wird auf ... abgebildet"

-- Wie man jetzt sieht: am einfachsten geht "func" mit dem vordefinierten map:
func4 x = map (mal x)

-- andere Listenoperation (Funktion höherer Ordnung: 
--   eine *Faltung* (fold), hier nur eine der Varianten (Rechtsfaltung):

summe = foldr (+) 0 vierteListe

-- wir summieren die Liste, d.h. verknüpfen die Elemente mit (+), von rechts geklammert.
-- der Startwert für die Verknüpfung (Resultat, falls die Liste leer wäre) ist 0 

-- Typen / Typinferenz: 
   --------------------
{- 
Hugs und GHC inferieren den allgemeinsten möglichen 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 richtigen 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. 15 sec mit hugs, 2 mit ghci (Linux) - aber nur beim ersten Aufruf!
-----------------------------------------------------------------------------


{-
Aufgabe: 

Darstellung von Mengen (mit Hilfe von Listen) und übliche Mengenoperationen

-}