-- version 0.2.1  (6. Jun 2005)
-- Autor: Wenzel Svojanovsky
-- Tutor fuer Info II an der Uni Karlsruhe
-- SoSe 2005

-- thanks to B.A.T. fuer inhaltliche und lingusitische Verbesserungen


-- Willkommen beim kleinen Heap-Special!

-- Ich werde mit dieser Version versuchen, euch ein wenig naeher an Haskell zu fuehren.
-- Haskell schreckt viele ab, da es eine ungewohnte Art ist, etwas auszudruecken, ohne Variablen, ect.
-- Die Freaks werden auch denken, dass das Zeug total ineffizient ist.
-- Nun, fuer viele Dinge mag das auch stimmen, aber mit Haskell lassen sich eben auch viele Funktionen,
-- besonders rekursive, schnell implementieren.

-- Bevor ich anfange: Diese Angaben sind alle ohne Gewaehr!

-- Kurzum: In ein paar Wochen habt ihr Klausur und Haskell wird ein Teil der Klausur sein.
-- Was in der Klausur dran kommt, ist sehr schwer einzuschaetzen. Wer sich Haskell verweigert
-- und die Programme aus dem Netz holt, ist selber Schuld. Bedenken wir die alte Klausur aus Info I,
-- in der Java etwa 50% der Punkte ausmachte. Ich wuerde ausserdem nicht von einem leichten
-- Theorie-Teil ausgehen, somit solltet ihr alle in den sauren Apfel beissen und dieses Tutorial durchmachen.
-- Ich hoffe, dass ihr damit alle etwas lernt und gelassener in die Klausur geht.

-- In diesem Tutorial wollen wir uns mit einem Heap beschaeftigen.
-- Dieser wird auch als "Halde" bezeichnet.
-- Ein Heap ist ein binaerer Baum, das heisst, er besteht aus Knoten und Blaettern.
-- In jedem Knoten gibt es entweder 1 oder 2 Aeste, aber niemals mehr.
-- Ein Heap muss nicht balanciert sein, d.h. dass die Knoten etwa gleich auf die linke
-- und rechte Seite verteilt sind. Fachgerecht ausgedrueckt:
-- Die Hoehe des linken Teilbaums ist maximal 1 hoeher oder niedriger als die des
-- rechten Teilbaums.
-- Aber wie gesagt, diese Eigenschaft muss nicht erfuellt sein.

-- In einem Heap gilt folgendes: Der Wert im Knoten ist groesser als alle Werte in den
-- darunterliegenden Knoten und Blaettern.
-- Aus dieser Bedienung folgt, dass das groesste Element in der Wurzel ist.

-- Diese Illustration zeigt ein Beispiel fuer einen Heap!


--            _14_
--          _/    \_
--        10        6
--       /  \      / \
--      7    8    5   3
--     / \       / \
--    2   4     1   *

-- (Es gibt auch Heaps, in denen es genau umgekehrt ist, also das kleinste Element
-- ist in der Wurzel, diese sind aber analog zu behandeln)

-- Der "*" soll hier ein leeres Blatt, bzw. leeren Heap darstellen, da wir ausgehen, dass
-- es in jedem Knoten zwei Aeste gibt, muss die Situation abgefangen werden, in der
-- nur ein einziger Ast besetzt ist.

-- Es sollte auch zu erkennen sein, dass jeder Teilbaum dies Heaps selbst
-- ein Heap ist.

-----------------------------------

-- Soviel erstmal zur Theorie des Heaps!
-- Kommen wir zu Praxis. Der Heap ist ein Abstrakter Datentyp (ADT)
-- was soviel hei�, dass es auf ihm keine trivialen Operationen wie
-- +,-,* gibt, aber andere wie insert,...

-- Wenn wir einen Datentyp in Haskell definieren wollen, brauchen wir das
-- Schluesselwort "data" (wie originell). Dann geben wir dem Kind einen Namen.
-- Vorher m�hte ich den Datentyp "Monat" definieren. Dieser ist vielleicht
-- intuitiver verstaendlich.

-- data Monat = Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dez

-- Hier wird ersichtlich, wie man einen Datentyp aufbaut.
-- data Name = Element1 | Element2 | ...
-- Wichtig ist, dass die Elemente mit einem Grossbuchstaben anfangen. Grossgeschiebene
-- Woerter weisen auf Konstrukturen in Haskell hin. Also besteht der Typ Monat
-- aus den Objekten Jan, Feb,... die jeweils mit dem Konstruktor Jan, Feb, ...
-- erzeugt werden.

-- Bisher koennen wir aber nicht viel mit dem Datentyp anfangen
-- geben wir z.B. ein:
-- Dez == Dez
-- so kommt eine Fehlermeldung.
-- Um Monate vergleich zu koennen, brauchen wir eine Ableiteung aus Eq.
-- Diese sieht in Haskell dann so aus

-- data Monat = Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dez deriving (Eq)

-- Eq erlaubt, dass man die Elemente mit "==" vergleichen darf
-- Dez == Dez liefert True
-- Dez == Nov liefert False

-- Um das noch mehr zu erweitern, koennen wir Eq noch um Ord ergaenzen (Ord setzt Eq vorraus).
-- dies sieht dann so aus:
-- data Monat = Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dez deriving (Eq, Ord)

-- die Eingabe
-- Dez > Nov liefert nun keinen Fehler mehr, sondern True

-- Damit wir unseren Monat auch auf dem Bildschirm ausgeben koennen, gibt es zwei
-- Moeglichkeiten. Wir leiten direkt von der Klasse Show ab,
-- oder definieren uns unsere eigenen show-Funktion.
-- Aufgabe von Show ist es, einen Datentyp in einen String (Zeichenkette)
-- zu verwandeln, damit dieser auf dem Bildschirm ausgegeben werden kann.

-- data Monat = Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dez deriving (Eq, Ord, Show)

-- Das ist die Standard und einfachste Loesung. Show nimmt dabei den Typ Dez und verwandelt
-- ihn in den String "Dez". Analog mit Nov, Oct,...
-- Wenn wir nun in ghci
-- Dez
-- eintippen, erhalten wir
-- Dez
-- Vorher kam ein Fehler.

-- Zweiteres ist etwas mehr Arbeit, ist aber sehr flexibel.
-- Um eine eigene Show Funktion zu implementieren, muessen wir eine
-- Instanz aus der Klasse Show ableiten.
-- Dies geht mit
-- instance Show Typ where

data Monat = Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dez deriving (Eq, Ord)
instance Show Monat where
  show Jan = "Mein Geburtstmonat"
  show Feb = "Da ist's noch kalt"
  show Mar = "Da fangen die Klausuren an"
  show x = "den Monat habe ich nicht definiert"

-- Man sieht hier, dass man sowohl die einzelnen Faelle der Monate abfangen kann
-- als auch einen allgemeinen Fall. Zu beachten ist die Einrueckung und Grossschreibung.
-- Aa "x" in der letzten Zeile klein geschrieben ist, wird es als normale Variable angesegen
-- und dementsprechend gilt sie allgemein. Die drei Zeilen davor weisen den Kontruktor auf
-- der fuer die einzelnen Elemente gilt.

-- Nun haben wir Monat definiert. Auf mehr will ich hier nicht eingehen.
-- Es gibt noch weitere Moeglichkeiten, wie z.B. Enum, somit wuerde
-- automatisch Jan die 0, Feb die 1,.. zugewiesen werden
-- mit einer Instanz von Num koennte man dann Jan+Mar rechnen,...
-- Der Kreativitaet sind hier keine Grenzen gesetzt.

-- Aufgabe:
-- Erweitert Monat um gaaanz viele tolle Sachen zu Hause, experimentiert mit
-- dem Datentyp, macht vielleicht ein komplettes Datum draus,...


-------------------------------------------------

-- LEARNING BY DOING!!!!
-- Ich kann euch das hier alles schreiben, aber das bringt nichts, wenn ihr euch
-- nicht auf euren eigenen Hosenboden setzt und es selbst ausprobiert!
-- Wenn ihr keine Ahnung habt, dann probiert aus dem Gedaechtnis den
-- Datantyp Monat zu implementieren, sucht im Netz nach weiteren Ableitungen,
-- wie z.B. Enum, Show, Read... Schreibt Funtionen mit Monat, z.B. eine Funktion die die
-- Anzahl der Tage eines Monats ausgibt. Macht einen Datentyp Datum,
-- der aus Tagen, Monat und Jahr besteht,...

-- Es gibt 3 Moeglichkeiten an die Klausur zu gehen:
-- 1. Auswendig lernen: Das bringt bei der Klausur nichts, wenn es nicht zufaellig
--      eine alte Aufgabe ist
-- 2. Ansehen und Verstehen: Besser, aber probiert dann mal was selbst zu schreiben!
--      Ein Programm zu verstehen ist gut, reicht aber wohl nicht fr die Klausur
--      Da musst ihr selbst was schreiben
-- 3. Selbst probieren: Der einzige Weg, gelassen an die Klausur zu gehen. Seid ehrlich
--      zu euch selbst. Wenn ihr etwas nicht versteht, nicht verzweifeln. Sehr viele haben
--      das gleich Problem. Fuer euch ist dieses Tutorial gemacht, damit ihr
--      hier sehr, wie etwas gemacht wird und euch Mut gibt, es selbst zu probieren.
--      Wenn ihr das gelesen habt, probiert einen Heap selbst zu implementieren,
--      aber ohne zu spicken. Gruebelt ueber manche Probleme eine Stunde nach.
--      Wenn ihr spickt, habe ich mir die ganze Arbeit umsonst gemacht, dann lernt
--      ihr nichts. Selbst gruebeln und nur um aeussersten Notfall spicken, nach einer
--      Stunde. Und nicht dazwischen ein Kaffe trinken gehen. Schnappt euch ein paar
--      andere Haskell-Schwache. Da gibt es sehr viele hier im Jahrgang!

-- Haskell lernt man nur aus Frust! Wenn ihr nicht frustiert seid,
-- dann koennt ihr auch nicht motiviert sein um zu Lernen!

-- PS: Diese Aussage war total unpaedagogisch.



----------------------------

-- Kommen wir zurueck zum Heap

-- Rufen wir uns nochmal das Bild von vorhin ins Gedaechtnis

--            _14_
--          _/    \_
--        10        6
--       /  \      / \
--      7    8    5   3
--     / \       / \
--    2   4     1   *

-- Der Heap ist ein binaerer Baum, jeder Teilbaum ist ein Heap, jeweils in der Wurzel
-- ist das groesste Element des Heaps.
-- 14 ist max aus {10, 6, 7, 8, 5, 3, 2, 4, 1}
--  6 ist max aus {5, 3, 1}

-- Der Heap besteht aus drei Dingen:
--  1. Den Knoten (Node) an dem ein oder zwei Heaps dranhaengen
--  2. Das Blatt (Leaf), das nur ein Element traegt, keine Heaps
--  3. Der leere Heap (Empty) (hier als *), notwendig, da er wir im Beispiel
--       an der 5 haengen kann, an der haengt naemlich nur ein Heap


-- Vorhin haben wir gelernt, dass wir einen Datentyp wie folgt definieren
-- data Name = Elem1 | Elem2 | ... deriving (...)

-- Hier waere also der Gedanke nahe:
-- data Heap = Emtpy | Leaf | Node deriving (Eq)

-- Das ist schonmal ein Anfang, allerdings reicht das noch nicht, denn
-- anders als in Monat, spannen wir den Heap ueber Zahlen auf.
-- Die Monate waren Werte selbst, haben aber keine Variablen gespeichert.
-- Muessen wir einen Typ festlegen, ueber den wir den Heap aufspannen
-- Es ist aber egal, ob der Typ Integer, Short, Float oder Double ist.
-- Darum verwenden wir einen Platzhalten "a"
-- Haskell sucht sich den richtigen Typ schon raus.
-- Dass es ein geordneter Typ sein muss (schlie�ich muessen wir der
-- Groesse nach sortieren), legen wir hier noch nicht fest.
-- Das "deriving (Eq, Ord)" beschraenkt sich auf den Heap, nicht auf
-- die Elemente im Heap. Ord und Eq koennen sogar weggelassen werden.
-- Eq werden wir aber vollstaendigkeitshalber drin lassen. Vielleicht
-- brauchen wir es.

-- data Heap a = Emtpy | Leaf | Node deriving (Eq)

-- Nun spannen wir den Heap ueber den Typ a auf.
-- Das hilft uns aber nicht weiter, wenn wir keine Werte im Heap speichern.
-- Kommen also die Blaetter an die Reihe, diese enthalten einen Wert.
-- Den Wert des Typs geben wir mit "a" an, denn das ist schlie�ich der Typ
-- ueber den wir den Heap aufspannen.

-- data Heap a = Emtpy | Leaf a | Node deriving (Eq)

-- Nicht zu vergessen, dass auch die Node einen Wert enthaelt

-- data Heap a = Emtpy | Leaf a | Node a deriving (Eq)

-- Jetzt sind wir fast fertig mit der Typdefinition
-- Die Node enthaelt aber nicht nur einen Wert vom Typ a
-- sondern auch zwei Aeste. Jeder Ast ist ein Heap.
-- Wir legen also den Typ fr die zweiten und dritten
-- Werte in Node fest, das ist naemlich "Heap a"
-- Da "Heap a" eine Variable sein soll, wird sie geklammert.
-- So haben wir nur einen binaeren Baum, der leer sein kann (Emtpy)
-- ein Blatt mit einem Wert hat (Leaf a) oder ein Knoten mit einem
-- Wert und zwei weiteren Heaps (Node a (Heap a) (Heap a)).

data Heap a = Empty | Leaf a | Node a (Heap a) (Heap a) deriving (Eq)


-- Den Heap dieser Form
--      6
--     / \
--    5   3
--   / \   
--  1   *
-- koennen wir in Haskell nun so eigeben

-- Node 6 (Node 5 (Leaf 1) Empty) (Leaf 3)


-- So, wir sind nun in der Lage einen Heap zu bauen.
-- Da es sich aber um einen ADT handelt, hat Haskell Probleme damit,
-- den Heap auf dem Bildschirm auszugeben. Da es
-- sehr kompliziert waere, den Heap in der Baumform ausgeben zu lassen
-- wie ich es hier in den Kommentaren tue, ist folgende Loesung ein
-- (meiner Meinung nach) guter Kompromiss:

-- "((1/5\-)/6\3)"

-- Jeder Wert in der Node wird von einen "/ \" umgeben.
-- Jeder Heap wird geklammert, damit man sehen kann, 
--       welcher Heap zu welcher Node gehoert.
-- Der leere Heap wird ein "-".

-- Die Signatur fuer unsere Klasse Show muessen wir etwas erweitern.
-- Ein "instance Show (Heap a) where" reicht diesmal leider nicht aus,
-- da wir mit zwei Typen arbeiten: a und Heap
-- Haskell kann nicht davon ausgehen, dass a eine show-Funktion hat,
-- deswegen muessen wir damit eine Bedingung an den Typ a formulieren.
-- Dies geschieht mit "Show a =>" was soviel bedeutet wie:
-- a ist auch eine Instanz der Klasse Show und erbt eine show-Funktion
-- Demnach sieht unsere Signatur der Klasse Show nun so aus:

-- instance Show a => Show (Heap a) where

-- Nun gilt es die einzelnen Faelle abzudecken; das sind
-- Empty, Lead und Node.
-- Bei Empty entschliessen wir uns ein "-" auszugeben. Das ist leicht:
--   show (Empty) = "-"

-- Bei Leaf geht es etwas mehr zu Sache, denn Leaf enthaelt einen Wert
-- den wir ausgeben wollen. Da dieser Wert vom Typ a (also "beliebig")
-- ist, wir aber gefordert haben, dass a eine Instanz von Show ist,
-- so lesen wir den Wert von Leaf ein und rufen seine eigene show-Funktion auf.
--   show (Leaf x) = show x
-- An den (Leaf x) erkennt der Interpreter, dass es sich um ein Blatt handelt.
-- In der Typ-Definition von Heap hatten wir ...| Leaf a |... stehen, was Haskell
-- sagt, dass Leaf ein Datum von Typ a enthaelt. Dieser Wert wird mit dem Konstruktor
-- Leaf uebergeben. Wir bezeichnen nun den Wert mit einem beliebigen kleigneschiebenen
-- Namen, hier "x". x enthaelt also in diesem Aufruf den Wert vom Blatt.
-- Um ihn auszugeben, rufen wir einfach seine show-Funktion mit "show x" auf.

-- Umfangreicher, aber nicht schwieriger wird es mit der Node. Hier haben wir
-- 3 Werte gespeichert, den Wert, den linken Heap und den rechten Heap.
-- Wie beim Leaf werden wir einfach den Node-Wert mit x bennen und mit
-- "show x" ausgeben. Da alle drei Werte mit dem Konstruktor Node uebergeben werden
-- muessen wir auch allen dreien einen Variablennamen zuweisen. In der Definition steht
-- ... | Node a (Heap a) (Heapa) ... . Mit (Node x y z) weisen wir also x dem
-- ersten Wert in Node zu, der vom Typ a ist, y bekommt den linken und z den 
-- rechten Heap. 
-- Nun gilt es die alle in die richtige Reihenfolge zu bringen. Da ein kompletter
-- Heap immer geklammert sein soll, schreiben wir an den Rand die Klammern
-- "(" ++ ... ++ ")"
-- Mit "" markieren wir wie gewohnt die Strings, die wir ausgeben wollen. Um zwei
-- Strings miteinander zu verbinden (konkatenieren) benutzen wir den Operator ++
-- Da der linke Heap links von dem Node-Wert stehen soll, muessen wir y auch zuerst
-- ausgeben, das ist das "show y". Bei Baeumen in Haskell macht man das rekursiv. 
-- Wir sind dabei eine show-Funktion fuer Heap zu erstellen und rufen selbst show 
-- Heap auf. Das ist ja gerade der Witz der Rekursion. Sie wird auf jeden Fall 
-- enden, denn jeder Pfad durch den Baum endet entweder mit einem Leaf oder 
-- mit einem Empty. 
-- Um den Node-Wert herum machen setzen wir die "/" "\". Bitte beachtet, dass wir
-- fuer '\' "\\" schreiben muessen. Das '\' leitet ein Sonderzeichen ein. So koennte
-- man mit einen "\n" einen Zeilenumbruch erzwingen.
-- Rechts vom Node-Wert geben wir dann noch den rechten Heap mit "show z" aus.

-- Insgesamt sieht die show-Funktion so aus

instance Show a => Show (Heap a) where
  show (Empty) = "-"
  show (Leaf x) = show x
  show (Node x y z) = "(" ++ (show y) ++ "/" ++ (show x) ++ "\\" ++ (show z) ++ ")"


-- Uebung: Probiert mal eine Ausgabe zu schreiben, die euch den Heap genauso ausgibt,
--         wie ihr in eingegeben habt, also so:
--         "Node 6 (Node 5 (Leaf 1) Empty) (Leaf 3)"

-- Uebung: Findet raus, was passiert, wenn wir die Standard-Show-Methode nehmen,
--         also deriving (Show) verwenden


----------------------------------------------

-- kommen wir nun zu den Funktionen, die ein Heap haben sollte.
-- Erstere ist klein und eher unwichtig, wir bauen sie aber
-- trotzdem mal ein.

-- Diese Funktion nimmt einen Wert vom Typ a und
-- macht daraus einen neuen Heap. Da dieser Heap nach
-- diesem Funktionsaufruf immer genau einen Wert haben wird,
-- erstellen wir gleich ein Leaf. x ist dabei der uebergebene Wert.

newHeap :: Ord a => a -> Heap a
newHeap x = Leaf x

-- wer sich jetzt wundert, warum das "Ord a =>" da steht, der
-- hat recht. Es muss nicht unbedingt da stehen. Wenn man es weglaesst,
-- erhaelt man keine Fehlermeldung.
-- Allerdings wollen wir voraussetzen, dass der Typ a sortierbar ist,
-- denn schliess wollen wir ja die Bedingung eines Heaps ueberpruefen
-- wollen. Dies geht nur, wenn wir die einzelnen Elemente mit ">" und "<"
-- vergleichen koennen. 
-- Wenn wir nun das bei newHeap das "Ord a =>" weglassen wurden, koennte man
-- einen Heap ueber Elemente erstellen, die nicht mehr sortierbar sind.
-- Spaetere Funktionsaufrufe wuerden nicht mehr funktionieren.

----------------------------------------------

-- Es ist wichtig den Kopf eines Heaps bekommen zu koennen.
-- Auch hierfuer definieren wir uns eine Funktion mit der Signatur
-- heapHead :: Ord a => Heap a -> a

-- Es sollte beachtet werden, dass der Kopf eines leeren Heaps
-- nicht existiert und deswegen ein Fehler ausgegeben soll. Eine
-- Anfrage dieser Form muss abbrechen, da es sonst nicht weiter
-- defniniert ist. Diesen Fehler erzeugen wir mit dem Befehl "error"
-- der einen String als Parameter verlangt, der den Fehler beschreiben soll.
-- heapHead (Empty) = error "'heapHead' got empty heap"

-- Der Kopf eines Blattes ist der Wert in dem Blatt, also:
-- heapHead (Leaf x) = x

-- Stossen wir auf eine Node, was die Regel sein sollte, ist es nicht
-- notwendig die daran haengenden Heaps zu untersuchen, denn der Head
-- ist in diesem Fall auch der Wert, der in der Node steht.
-- heapHead (Node x y z) = x

-- Zusammengesetzt erhalten wir dann

heapHead :: Ord a => Heap a -> a
heapHead (Empty) = error "empty heap"
heapHead (Leaf x) = x
heapHead (Node x y z) = x

-- war doch nicht so schwer! Inzwischen solltet ihr etwas Uebung mit dem
-- Binaer-Baum haben und deswegeb folgt eine kleine Uebung:

-------------------------------------

-- Uebung:

-- Da wir es gerade es vorhin erwaehnt hatten. Wir wollen nun eine Funtion
-- schreiben, die ueberprueft, ob der gegebene Heap auch tatsaechlich einer
-- ist. Die Signatur soll dabei so aussehen:

-- isHeap :: Ord a => Heap a -> Bool

-- Ist die Reihenfolge der Elemente korrekt, soll er "True" ausgeben,
-- sobald aber einmal die Reihenfolge nicht stimmt, soll "False"
-- ausgegeben werden.

-- Diese Funtion ist eine nette Uebung. Alle dafuer notwendigen Mittel
-- sollten bereits vorhanden sein.
-- Zum Arbeiten mit dem Typ Bool: 
-- || ist das logische ODER
-- && ist das logische UND
-- True ist das True
-- False ist das False

-- Die Loesung zu dieser Aufgabe ist bereits unten im Tutoral vorhanden.
-- Echte Klausur-Lerner sollten aber auf das Nachschlagen verzichten,
-- da man ja einen Lerneffekt erziehlen will. Also nicht nachschauen
-- sondern selbst probieren

---------------------------------------------------------


heapInsert :: Ord a => Heap a -> a -> Heap a
heapInsert (Empty) v = Leaf v
heapInsert (Leaf x) v
  | x >= v = Node x (Leaf v) (Empty)
  | otherwise = Node v (Leaf x) (Empty)
heapInsert (Node x (Empty) z) v
  | x >= v = Node x (Leaf v) (z)
  | otherwise = Node v (Leaf x) (z)
heapInsert (Node x y (Empty)) v
  | x >= v = Node x (y) (Leaf v)
  | otherwise = Node v (y) (Leaf x)
heapInsert (Node x y z) v
    | x >= v = if heapHead y > heapHead z then Node x (y) (heapInsert z v) else Node x (heapInsert y v) (z)
    | otherwise = if heapHead y > heapHead z then Node v (y) (heapInsert z x) else Node v (heapInsert y x) (z)



__heapFromListHelper :: Ord a => Heap a -> [a] -> Heap a
__heapFromListHelper x [] = x
__heapFromListHelper x (y:ys) = __heapFromListHelper (heapInsert x y) ys
heapFromList :: Ord a => [a] -> Heap a
heapFromList x = __heapFromListHelper Empty x




--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------Achtung!----------------------------
--------------------------------------------------
-------Bitte lest jetzt nicht weiter!-------------
--------------------------------------------------
--------------------------------------------------
-----Hier kommen naemlich die Loesungen-----------
----------zu den Uebungen hin---------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
-----Wenn ihr hier nachlest, habt ihr nichts------
-------fuer die Klausur gelernt.------------------
--------------------------------------------------
-----Dies dient einzig und allein der-------------
-----Korrektur eurer Loesungen.-------------------
--------------------------------------------------
-----Probiert es erst auf dem Papier,-------------
-----dann auf dem Rechner-------------------------
-----und dann erst spicken------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------
--------------------------------------------------











-- wenn du dies liest
-- dann hast du geschummelt
-- moege dein Bauch sich aufblaehen und dir 
-- alle Haare ausfallen bis auf drei!


-----------------------------------------------

-- Gut, da sind wir bei der Funktion isHeap.
-- Da wir Elemente der Groesse nach vergleichen wollen
-- muessen wir das "Ord a =>" in der Signatur fordern
-- Ueberprueft wird ein Heap und ein Bool (True oder False)
-- wird ausgegeben.
-- isHeap :: Ord a => Heap a -> Bool

-- Ist der Heap leer, ist es immer noch ein Heap, demnach True
-- isHeap Empty = True

-- Ist es nur ein Blatt, so gibt es nichts zum ueberpruefen. 
-- Es ist aber immer noch ein Heap, demnach True
-- isHeap (Leaf a) = True

-- Kommen wir zur Node. Wir muessen uns dabei die Koepfe der
-- Teilheaps anschauen. Da wir aber fuer Empty keinen Kopf bzw.
-- Wurzel definiert haben, muessen wir alle moeglichen Faelle 
-- abdecken. Das waeren:
-- isHeap (Node x Empty Empty) 
-- isHeap (Node x y Empty) 
-- isHeap (Node x Empty z) 
-- isHeap (Node x y z)

-- Erster Fall ist True, aehnlich wie beim Leaf
-- isHeap (Node x Empty Empty) = True

-- Im zweiten Fall vergleichen wir den Kopf vom Heap y mit dem
-- Wert x in der Node. Ist dieser groesser, so ist das True sonst False
-- isHeap (Node x y Empty) = if x >= (heapHead y) then True else False
-- Da wir aber noch nicht ueberprueft haben, ob auch y ein korrekter Heap ist
-- muessen wir dies rekursiv ueberpruefen. 
-- Es soll nur True ergeben, wenn BEIDE korrekt Heaps sind. Demnach muessen
-- wir hier beide Ergebnisse mit einen logischen und "&&" verknuepfen
-- isHeap (Node x y Empty) = (if x >= (heapHead y) then True else False) && (isHeap y)
-- Das "if b then True else False" laesst sich auch einfach mit "b" ausdruecken.
-- Wir lassen also das "then True else False" weg und erhalten.
-- isHeap (Node x y Empty) = (x >= (heapHead y) ) && (isHeap y)

-- Analog verlaeuft das mit dem rechten Heap
--isHeap (Node x Empty z) = (x >= (heapHead z)) && (isHeap z)

-- Sind beide Heaps nicht leer, ist es nichts weiter, als die &&-Verkettung von
-- allen drei anfragen, denn sowohl y als auch z muessen ein Heap sein, und
-- x muss groe�r als der Kopf von y und der Kopf von z sein.
-- Letzte Abfrage kann man abkuerzen, indem man x nur mit dem Maximum der beiden vergleicht
-- isHeap (Node x y z) = (x >= (max (heapHead y) (heapHead z))) && (isHeap y) && (isHeap z)

-- komplett zusammen sieht das jetzt so aus!

isHeap :: Ord a => Heap a -> Bool
isHeap Empty = True
isHeap (Leaf a) = True
isHeap (Node x Empty Empty) = True
isHeap (Node x y Empty) = (x >= (heapHead y)) && (isHeap y)
isHeap (Node x Empty z) = (x >= (heapHead z)) && (isHeap z)
isHeap (Node x y z) = (x >= (max (heapHead y) (heapHead z))) && (isHeap y) && (isHeap z)

-- Nachtrag: 
-- Das ">=" ist wichtig und richtiger als das ">", denn mit dem ">" koennte man keinen
-- Heap zusammenbauen, in dem zwei gleiche Zahlen vorkommen.

-- Ueberpruefen wir nun diese beiden Heaps
--      6
--     / \
--    5   3
--   / \   
--  1   *
--
--  und
--
--      6
--     / \
--    1   3
--   / \   
--  5   *
-- 
-- Unterer ist kein korrekter Heap, auch wenn wir ihn mit Haskell bauen koennen.

-- isHeap Node 6 (Node 5 (Leaf 1) Empty) (Leaf 3)
-- Ergibt True
-- waehrend 
-- isHeap Node 6 (Node 1 (Leaf 5) Empty) (Leaf 3)
-- False ergeben sollte.