-- Das folgende Pragma definiert die Haskell-Spracherweiterungen, die
-- wir im Verlauf dieser Übung verwenden.
--
-- TypeOperators:    Verwendung von :+: und :*: als Infix-Typkonstruktoren.
-- TypeFamilies:     Verwendung von Rep als Typsynonym innerhalb
--                   von Klassen und Instanzen.
-- FlexibleContexts: Verwendung von (GEncode (Rep a) => ...) im Typ einer
--                   Funktion.
-- TemplateHaskell:  Verwendung von Template Haskell.
-- EmptyDataDecls:   Verwendung von Datentypen ohne Konstruktoren.
{-# LANGUAGE TypeOperators, TypeFamilies, FlexibleContexts, TemplateHaskell, EmptyDataDecls #-}
module Assignment where

-- Installieren Sie zunächst die instant-generics Bibliothek von Hackage, indem
-- Sie auf der Kommandozeile folgende Befehle eingeben:
--
--   cabal update
--   cabal install instant-generics
--
-- Danach sollte es möglich sein, dieses Modul via
--
--   ghci Assignment
--
-- zu laden.
--
-- Die folgenden Anweisungen binden die Module der instant-generics Bibliothek
-- ein, die wir brauchen werden.
import Generics.Instant
import Generics.Instant.TH (deriveAll)

-- Der folgende Datentyp definiert binäre Bäume mit Elementen
-- in den Knoten. Zum Testen lassen wir auch Eq und Show-Instanzen
-- ableiten.
data Bin a = Leaf | Node (Bin a) a (Bin a)
  deriving (Eq, Show)

-- Und hier ist ein Datentyp für Pfade in binären Bäumen.
data Path = Stop | DownLeft Path | DownRight Path
  deriving (Eq, Show)

-- *** Repräsentation von Datentypen

-- Aufgabe 1: Korrigieren Sie die folgende Representable-Instanz
-- für Bin. Sie können eine einfache Repräsentation ohne Konstruktoren
-- wählen.
instance Representable (Bin a) where
  type Rep (Bin a) = Bin a

  from = undefined
  to   = undefined

-- Aufgabe 2: Geben Sie eine Representable-Instanz für Path an.
--
-- instance Representable Path where

-- *** Bits

-- Wir definieren den Datentyp für Bits, und der Einfachheit halber
-- auch Eq- und Show-Instanzen.
data Bit = O | I deriving (Eq, Show)

-- Trotz allem ist es günstig, auch eine Repräsentation für den Datentyp
-- anzugeben. Da wir das jetzt oft genug gemacht haben, lassen wir uns
-- von Template-Haskell helfen: Die folgende Anweisung ersetzt die komplette
-- Instanz.
$(deriveAll ''Bit)

-- Aufgabe 3: Sie können nachvollziehen, welchen Code der Compiler für
-- die obige Anweisung generiert. Tippen Sie einfach am GHCi-Prompt das
-- Kommando
--
--   :set -ddump-splices
--
-- ein, verändern Sie dann diese Datei geringfügig, um einen Reload zu
-- erzwingen und tippen Sie dann
--
--   :r
--
-- ein. Die Ausgabe ist nicht besonders schön und kein völlig korrektes
-- Haskell, weil eine interne Repräsentation gezeigt wird. Dennoch werden
-- hinreichende Informationen geliefert, um sich ein Bild machen zu können.

-- *** Encode

-- Aufgabe 4: Vervollständigen Sie die folgende Definition von "gencode"
-- gemäß den Ideen, die wir während der Vorlesung besprochen haben.

class GEncode a where
  gencode :: a -> [Bit]

instance GEncode U where
  gencode U = undefined

instance (GEncode a, GEncode b) => GEncode (a :+: b) where
  gencode x = undefined

instance (GEncode a, GEncode b) => GEncode (a :*: b) where
  gencode x = undefined

-- Anders als in der Vorlesung behandelt instant-generics Bool als einen
-- primitiven Datentyp, so dass wir eine separate Instanz definieren müssen.
instance GEncode Bool where
  gencode False = [O]
  gencode True  = [I]

-- Selbst wenn in den eigenen Repräsentationen keine Konstruktor-Markierungen
-- auftauchen, so kommen sie doch in den durch instant-generics vordefinierten
-- Repräsentationen vor. Daher sollten wir auch hierfür eine einfache Instanz
-- definieren.
instance GEncode a => GEncode (C c a) where
  gencode (C a) = gencode a

-- Wie in der Vorlesung erwähnt, markiert instant-generics in der Repräsentation
-- außerdem jeden als Argument vorkommenden Typ entweder als Variable (Var) oder
-- als anderen Datentypen (Rec). Rec wird sowohl für direkt rekursive Aufrufe als
-- auch für beliebige andere Typen verwendet. Wir können diese Markierungen
-- einfach ignorieren.
instance GEncode a => GEncode (Var a) where
  gencode (Var a) = gencode a

instance GEncode a => GEncode (Rec a) where
  gencode (Rec a) = gencode a

-- Aufgabe 5: Definieren Sie die generische Funktion encode.

encode :: (Representable a, GEncode (Rep a)) => a -> [Bit]
encode a = undefined

-- Hier ist nun eine triviale Instanz für Listen.
instance GEncode a => GEncode [a] where
  gencode = encode

-- Aufgabe 6: Definieren Sie generische GEncode-Instanzen für
-- die Datentypen Maybe, Bin und Path.

-- *** Decode

type BitParser a = [Bit] -> Maybe (a, [Bit])

class GDecode a where
  gdecode :: BitParser a

-- Aufgabe 7: Geben Sie GDecode-Instanzen für U, :+:, :*:,
-- C, Var und Rec an. Beachten Sie, dass die gdecode-Funktion
-- Werte des repräsentierten Typen erzeugt und sich dadurch
-- einige Kleinigkeiten ändern. Die Verwendung von
-- Parser-Kombinatoren ist in diesem einfachen Fall zwar
-- möglich, aber nicht zwingend nötig. Die Instanzen sind
-- einfach genug, dass man sie direkt implementieren kann.

-- Aufgabe 8: Definieren Sie die generische Funktion decode.
decode = undefined

-- Aufgabe 9: Definieren Sie generische GDecode-Instanzen für
-- die Datentypen Bool, Maybe, [], Bin und Path.

-- Aufgabe 10: Überzeugen Sie sich mit Hilfe von Beispielen,
-- dass die unten gebene Funktion decodeEncodeTest angewendet
-- auf einen repräsentierbaren Ausdruck a tatsächich wieder
-- Just (a, []) liefert.
decodeEncodeTest :: (Representable a, GEncode (Rep a), GDecode (Rep a)) =>
                    a -> Maybe (a, [Bit])
decodeEncodeTest a = decode (encode a)

-- *** BONUS-Aufgaben

-- Aufgabe 11: Versuchen Sie die obige Eigenschaft
-- für Binärbäume oder Pfade als QuickCheck-Property zu
-- implementieren.

-- Aufgabe 12: Definieren Sie eine generische Funktion
-- um die Klasse
--
--   class GEnum a where
--     genum :: [a]
--
-- Die Funktion soll alle Elemente (ohne Berücksichtigung
-- von undefined) eines Typs aufzählen. Versuchen Sie
-- zunächst, die Funktion für endliche Typen korrekt
-- arbeiten zu lassen. Überlegen Sie sich dann, wie Sie
-- erreichen können, dass bei unendlichen Typen tatsächlich
-- eine unendliche Liste erzeugt wird, in der jedes Element
-- des Typen an einer endlichen Position vorkommt.
--
-- Aufgabe 13: Versuchen Sie, encode und decode fuer den
-- Int-Datentyp zu definieren. Hierfür können Sie sich des
-- Moduls Data.Bits bedienen, welches u.a. die Funktionen
--
--   bitSize :: Bits a => a -> Int
--   testBit :: Bits a => a -> Int -> Bool
--   setBit  :: Bits a => a -> Int -> a
--
-- definiert. Z.B. liefern auf einer 32-bit Maschine
--
--   bitSize (0 :: Int)
--
-- und
--
--   setBit (0 :: Int) 5
--
-- beide das Ergebnis 32.
--
-- Aufgabe 14: Definieren Sie eine generische Funktion
-- um die Klasse
--
--   class GDeepSeq a where
--     gdeepSeq :: a -> b -> b
--
-- Die primitive Funktion
--
--     seq :: a -> b -> b
--
-- wertet das erste Argument bis zur head normal form aus
-- und gibt dann das zweite zurück. Die Funktion deepSeq
-- soll nun das erste Argument *komplett* auswerten und dann
-- das zweite zurückgeben. Verwenden Sie pattern matching oder
-- die seq-Funktion, um das in Ihrer generischen Definition
-- zu erreichen. Helfen Sie sich evtl., indem Sie (wie wir
-- es bei der Gleichheitsfunktion gemacht haben) zunächst
-- einige konkrete Instanzen definieren, um ein Gefühl dafür
-- zu bekommen, wie es funktionieren müsste.