-- Fortgeschrittene Funktionale Programmierung, 
--   LMU, TCS, Wintersemester 2015/16
--   Steffen Jost, Alexander Isenko
--
-- Übungsblatt 05. 18.11.2015
--
-- Thema: Applikative Funktoren
--
-- 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!
--  
--        _____________________________________________________________________
--       |                                                                     |
--       | Ziele für dieses Blatt:                                             |
--       |   * Instanzen für eigene Datentypen schreiben können                |
--       |   * Applicative Gesetze und Klassenfunktionen kennenlernen          |
--       |   * Klasse Traversable kennenlernen                                 |
--       |_____________________________________________________________________|
--       |
--    λ_/
--   /|
--   / \

import Prelude hiding (Traversable, traverse)
import Data.Functor
import Control.Applicative

---- A5-1 Instanzen von Applikativen Funktoren
--
--    Gegeben ist eine alternative Datentypdeklaration
--    für gewöhnliche Listen:

data List a = Nil | Cons a (List a)
  deriving (Eq, Show)
  
{- 
-- Manuell definierte Show-Instanz für gewöhnliche Schreibweise:
instance Show a => Show (List a) where
  show Nil = "[]"
  show (Cons x Nil) = show x ++ " : " ++ "[]"
  show (Cons x xs) = show x ++ " : " ++ show xs
--
-- Für den Ausdruck gilt damit folgende Schreibweise:
--       []      entspricht   Nil
--       (h:t)   entspricht   (Cons h t)
-}


--    In der Vorlesung wurden zwei Möglichkeiten vorgestellt,
--    Listen zu Applikativen Funktoren zu machen.
--    In dieser Aufgabe sollen Sie dies nachvollziehen,
--    d.h. schauen Sie dabei also möglichst _NICHT_ in Folien 4-19 ff.
--    sondern nur die davor!


-- a) Betrachten Sie folgenden fehlerhaften Lösungsversuch.
--    Der Lösungsversuch kompiliert und lässt sich ausführen,
--    aber die Gesetze eines Applikativen Funktors werden
--    missachtet.
--    Finden Sie durch ausprobieren mindestens ein Gesetz,
--    welches missachtet wird!
--
--    Beispiel:
--              > pure id <*> Nil2   :: List2 Int -- explizite Typangabe
--              Nil2
--      liefert noch keinen Hinweis daruf, dass z.B. das Gesetz "Identität"
--      verletzt wird -- aber vielleicht wird es für andere Werte als Nil2 verletzt,
--      oder vielleicht wird ein anderes Gesetz verletzt?! Finden Sie es heraus!
--
--    Hinweis: Achten Sie bei Ihren Tests in GHCI darauf,
--      dass auch die richtige Instanz verwendet wird,
--      z.B. durch explizite Angabe des Typs!

data List2 a = Nil2 | Cons2 a (List2 a) deriving (Show, Eq)

instance Functor List2 where
  fmap _ Nil2 = Nil2
  fmap f (Cons2 x xs) = Cons2 (f x) (fmap f xs)

instance Applicative List2 where
  -- pure :: a -> List2 a           -- Typsignaturen sind in Instanzdeklarationen unzulässig
  pure x = Nil2
  -- <*> :: List2 (a -> b) -> List2 a -> List2 b
  Nil2 <*> _ = Nil2
  (Cons2 x xs) <*> Nil2       = Nil2
  (Cons2 x xs) <*> Cons2 y ys = Cons2 (x y) (xs <*> ys)

{-
 - Nimm:
 - ghci> pure id <*> (Cons2 () Nil2)
 - Nil2
 - Dies verletzt Identität.
 -}

-- b) Ist folgende Nachbesserung zur a) wirklich besser?
--    Werden nun alle Gesetze respektiert?

data List3 a = Nil3 | Cons3 a (List3 a) deriving (Show, Eq)

instance Functor List3 where
  fmap f xs = pure f <*> xs

instance Applicative List3 where
  -- pure :: a -> List3 a
  pure x = Cons3 x Nil3
  -- <*> :: List3 (a -> b) -> List3 a -> List3 b
  Nil3 <*> _ = Nil3
  (Cons3 x xs) <*> Nil3       = Nil3
  (Cons3 x xs) <*> Cons3 y ys =
    Cons3 (x y) (xs <*> ys)

{-
 - Nimm:
 - ghci> pure id <*> (Cons3 () (Cons3 () Nil3))
 - Cons3 () Nil3
 - Auch dies verletzt Identität.
 -}

-- c) Machen Sie es nun selbst richtig!
--    Machen Sie den Typ List zu einer korrekten Instanz von Applicative!
--    Experimentieren Sie anschliessend mit ein paar Beispielen.

instance Functor List where
  fmap f xs = pure f <*> xs

-- Analog zu ZipList
instance Applicative List where
  pure x = Cons x (pure x)
  (Cons x xs) <*> (Cons y ys) = Cons (x y) (xs <*> ys)
  _ <*> _ = Nil


---- A5-2 Kontextfolge
--
-- Gegeben ist folgende Funktionsdefinition,
-- bei der leider die Typsignatur fehlt.

-- a)
-- Berechnen Sie die Typsignatur selbst manuell, also ohne einfach GHCI zu fragen!
-- Schlagen Sie ggf. die Typen von pure, (:), (<$>) und (<*>) nach!

folgeA :: Applicative f => [f a] -> f [a]
folgeA []    = pure []
folgeA (h:t) = (:) <$> h <*> folgeA t


-- b)
-- Wieder eine Denksportaufgabe:
-- zu welchem Ergebnis wertet folgende Ausdrücke aus:

a5_2b1 = folgeA [Just 1, Just 27, Just 2]
-- Just [1, 27, 2]
a5_2b2 = folgeA [Just 4, Just (sqrt 27), Just (sum [1..100]), Nothing, Just 0]
-- Nothing
a5_2b3 = folgeA [[1,2],[3],[4,5]]
-- [[1,3,4],[1,3,5],[2,3,4],[2,3,5]]
a5_2b4 = folgeA [ZipList [1,2], ZipList [3], ZipList [4,5]]
-- ZipList [1, 3, 4]
a5_2b5 = folgeA [(*2),(+1), negate] $ 3
-- [6, 4, -3]




---- A5-3 Anwendung von Applikativen Funktoren mit der Typklasse Traversable
--
--
-- Gegeben ist folgende vereinfachte Version 
-- der Typklasse Traversable (im Original siehe Modul Data.Traversable:
-- 

class Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  
  sequenceA :: Applicative f => t (f a) -> f (t a)
  sequenceA = traverse id
  

-- Weiterhin ist folgender Datentyp für Binäre Bäume gegeben:
  
data Baum a = Blatt a | Gabel (Baum a) a (Baum a) | Astloch
  deriving (Show, Eq)

test1 = Gabel (Blatt 42) 1 (Gabel (Gabel Astloch 69 $ Blatt 7) 44 Astloch)
test2 = Gabel (Blatt [42]) [1,2,3] (Gabel (Gabel Astloch [69,96] $ Blatt [7]) [44,101,0] Astloch)


-- a) Machen Sie den Typ "Baum" zu einer Instanz
-- der Tyklasse Traversable!
--
-- Hinweis:
--  Schauen Sie sich _NICHT_ das Modul Data.Traversable
--  aus der Standardbibliothek an, da dessen Dokumentation
--  bereits die Lösung zu dieser Aufgabe als Beispiel behandelt.

instance Traversable Baum where
  traverse _ Astloch = pure Astloch
  traverse f (Blatt x) = Blatt <$> f x
  traverse f (Gabel c1 x c2) = Gabel <$> traverse f c1 <*> f x <*> traverse f c2

-- Beispiele:
--  > take 1 $ drop 4 $ traverse (\x->[x,-x]) test1
--  [Gabel (Blatt 42) 1 (Gabel (Gabel Astloch (-69) (Blatt 7)) 44 Astloch)]
--
--  > traverse (\x->if x>0 then Just x else Nothing) test1
--  Just (Gabel (Blatt 42) 1 (Gabel (Gabel Astloch 69 (Blatt 7)) 44 Astloch))
--
--  > traverse (\x->if even x then Just x else Nothing) test1
--  Nothing
--
--  > take 2 $ drop 5 $ sequenceA test2
--  [Gabel (Blatt 42) 1 (Gabel (Gabel Astloch 96 (Blatt 7)) 0 Astloch),Gabel (Blatt 42) 2 (Gabel (Gabel Astloch 69 (Blatt 7)) 44 Astloch)]


-- b) Gibt es einen Zusammenhang zwischen folgeA und sequenceA? 

-- folgeA ist sequenceA spezialisiert auf []