-- Fortgeschrittene Funktionale Programmierung,
--   LMU, TCS, Wintersemester 2015/16
--   Steffen Jost, Alexander Isenko
--
-- Übungsblatt 02. 28.10.2015
--
-- Thema:
--
-- Anweisung:
--   Gehen Sie diese Datei durch und bearbeiten Sie
--   alle Vorkommen von undefined bzw. die mit -- !!! TODO !!!
--   markierten Stellen. Testen Sie Ihre Lösungen mit GHCi!


-- | A2-1 Funktionsdefinitionen
--
-- Implementieren Sie folgende grundlegenden,
-- bekannten Funktionen in Haskell.
-- Selbst wenn Sie die Funktion nicht kennen,
-- sollte Ihnen der Typ die korrekte Lösung ermöglichen!
--

import Prelude hiding (uncurry,flip,(.),map,zip,zipWith,zip,foldl)

import qualified Data.Map as P

-- Hinweis: Das import-Statement müssen Sie jetzt noch nicht verstehen,
--   es ist nur notwendig zur Vermeidung von Namenskonflikten mit der
--   Standardbibliothek, welche die meisten dieser Funktionen bereits enthält.

-- a) Uncurrying
--    > uncurry (/) (1,2) == 0.5
uncurry :: (a -> b -> c) -> ((a,b) -> c)
uncurry f (a,b) = f a b

-- b) Anwendung einer Funktion mit zwei Argumenten auf ein Paar
--    > (1,2) ||> (/) == 0.5
(||>) :: (a,b) -> (a -> b -> c) -> c
p ||> f = uncurry f p


-- c) Vertauschung der Reihenfolge der Funktionsargumente
--    > flip (/) 2 1 == 0.5
flip :: (a -> b -> c) -> (b -> a -> c)
flip f b a = f a b


-- d) Funktionskomposition
--    > ((\x->x+3) . (\y->y*2)) 1 == 5
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f $ g x


-- e) Map (im Gegensatz zu A1-3 dieses Mal ohne List-Comprehension)
--    > map (+10) [1,2,3,4] == [11,12,13,14]
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs


-- f) zip:
--    > zip ['a','b','c'] [1,2,3,4,5] = [('a',1),('b',2),('c',3)]
zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x, y) : zip xs ys


-- g) Zippen mit Funktionsanwendung:
--    > zipWith (+) [1..] [1..3] == [2,4,6]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f xs ys = map (uncurry f) $ zip xs ys


-- h) Falten nach links:
--    > foldl (flip (:)           ) [] [1..3] == [3,2,1]
--    > foldl (\acc x ->  x : acc)) [] [1..3] == [3,2,1]
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ x [] = x
foldl f x (y:ys) = foldl f (f x y) ys



-- | A2-2 LambdaTerme
--
--   Betrachten Sie die Lösung zur A1-1 g):

data LambdaTerm = LVar Char
                | LAbs Char       LambdaTerm
                | LApp LambdaTerm LambdaTerm

-- Ein paar Lambda Terme zum Testen:
lTerm_x   = LVar 'x'
lTerm_y   = LVar 'y'
lTerm_id  = LAbs 'x' lTerm_x
lTerm_xx  = LApp lTerm_x lTerm_x
lTerm_t   = LAbs 'x' $ LApp lTerm_y lTerm_xx
lTerm_yk  = LAbs 'y' $ LApp lTerm_t lTerm_t

-- a) Implementieren Sie eine Eq-Instanz für den Datentyp LambdaTerm!
--
--    (Wer Lambda-Kalkül kennt: Zur Vereinfachung der Aufgabe
--     ignorieren wir die übliche alpha-Äquivalenz, d.h.
--     (LAbs 'x' $ LVar 'x') und (LAbs 'y' $ LVar 'y')
--     dürfen als verschieden betrachtet werden)

instance Eq LambdaTerm where
  (LVar a) == (LVar b) = a == b
  (LVar _) == _ = False
  (LAbs a t_a) == (LAbs b t_b) = a == b && t_a == t_b
  (LAbs _ _) == _ = False
  (LApp t_a t'_a) == (LApp t_b t'_b) = t_a == t_b && t'_a == t'_b
  (LApp _ _) == _ = False

-- b) Implementieren Sie die eine Show-Instanz für LambdaTerm.
--    Achten Sie dabei auf eine korrekte Klammerung, aber
--    verschwenden Sie erst einmal keine Zeit darauf,
--    überflüssige Klammern zu vermeiden.

instance Show LambdaTerm where
  show (LVar a) = "LVar '" ++ pure a ++ "'"
  show (LAbs a t) = "LAbs '" ++ pure a ++ "' (" ++ show t ++ ")"
  show (LApp t t') = "LApp (" ++ show t ++ ") (" ++ show t' ++ ")"


-- | A2-3 Klassendeklaration
--
-- a) Deklarieren Sie eine Klasse "FinMap" für endliche partielle Abbildungen, welche folgende Operationen bereitsstellt:
--   1) "emptyM" liefert eine leere Abbildung
--   2) "insertM x a m" fügt die Abbildung  [x->a] in die Abbildung m ein.
--                      Falls x schon enthalten war, dann wird es überschrieben.
--   3) "lookupM x m" liefert Nothing zurück, falls x nicht in m enthalten ist;
--                    ansonsten wird der für x gespeicherte Wert z zurückgeliefert (in Just verpackt)
--                    Die Funktion "lookupM" darf dabei annehmen, dass für x eine Vergleichsoperation vorliegt!?!

class FinMap m where
  emptyM :: m k v
  insertM :: Ord k => k -> v -> m k v -> m k v
  lookupM :: Ord k => k -> m k v -> Maybe v
  -- Can we get around using constraints here without using the MultiParamTypeClasses language extension?

-- b) Machen Sie folgenden Datentyp zu einer Instanz der Typklasse Map:

-- data AL a b = AL [(a,b)]
newtype AL a b = AL [(a,b)]  -- Äquivalent zur vorherigen Zeile.
                             -- newtype kann und darf verwenden werden,
                             -- wenn man nur einen Konstruktor mit nur einem Argument hat.
                             -- Dies erlaubt GHC eine Optimierung durchzuführen.
               deriving (Show, Read, Eq)

instance FinMap AL where
  emptyM = AL $ []
  insertM x a (AL m) = AL $ (x, a) : [p | p@(x', _) <- m, x' /= x]
  lookupM x (AL m) = listToMaybe [y | (x', y) <- m, x' == x] -- Due to lazyness this is no slower than explicitly short-circuiting the search
    where
      -- This is part of Data.Maybe
      listToMaybe [] = Nothing
      listToMaybe (x:_) = Just x


---- Werte zum anschließendem Testen, auskommentieren,
---- sobald Klasse und Instanz definiert wurden:
testMap0  :: AL Int Bool
testMap0 = emptyM
testMap1 = insertM 1 False testMap0
testMap2 = insertM 3 False testMap1
testMap3 = insertM 4 True  testMap2
testMap4 = insertM 2 True  testMap3


-- Hinweis:
--    Partielle Abbildungen wie hier durch Assoziationslisten zu implementieren,
--    ist nicht bensonders effizient, da der Zugriff auf ein Element im Allgemeinen
--    den Aufwand O(n) hat (man muss die ganze Liste abklappern - es könnte sich ja
--    um das letzte Element der Liste handeln).
--    Mit Suchbäumen läßt sich der Aufwand bekanntermaßen auf O(log n) reduzieren.
--    Wer noch Lust & Zeit hat, kann versuchen, dies selbst zu implementieren
--    und zur einer weiteren Instanz von FinMap machen.
--
--    Die Standardbibliothek sieht zur Abstraktion hier keine solche Klasse vor,
--    sondern bietet lediglich eine konkrete, effiziente Implementierung von
--    endlichen Abbildungen an: Data.Map, welche wir in der kommenden Vorlesung
--    betrachten werden.
--
--    Dies kann man natürlich ganz schnell zu einer Instanz von FinMap machen. Wie?

data Map k v = Tip
             | Branch k v (Map k v) (Map k v)

instance FinMap Map where
  emptyM = Tip
  insertM k v Tip = Branch k v Tip Tip
  insertM k v (Branch k' v' lt gt)
    | k == k' = Branch k v lt gt
    | k < k' = Branch k' v' (insertM k v lt) gt
    | otherwise = Branch k' v' lt (insertM k v gt)
  lookupM _ Tip = Nothing
  lookupM k (Branch k' v' lt gt)
    | k == k' = Just v'
    | k < k' = lookupM k lt
    | otherwise = lookupM k gt

instance FinMap P.Map where
  emptyM = P.empty
  insertM = P.insert
  lookupM = P.lookup