{-# Language ScopedTypeVariables #-}
module Fold where
import Test.QuickCheck


{- 
Hier einige Ueberlegungen zur Frage, wie man foldl mit Hilfe von foldr schreiben kann.

Die Musterloesung hat folgende Form:

foldl :: forall a b .(a -> b -> a) -> a -> [b] -> a
foldl fkt seed list = foldr fkt2 XXXXXXXXXXXXXXX
  where
    fkt2 XXXXXXX = XXXXXXXXXXXXXXX
-}


-- zum ausprobieren kann man mit fold schoene Strings zusammenbauen:
fref :: Int -> String -> String
fref v s = "("++show v ++ " op " ++ s ++ ")"

test1 = foldr fref "seed" [1..4]

gref :: String -> Int -> String
gref s v = "("++ s ++ " op " ++ show v ++ ")"

test2 = foldl gref "seed" [1..4]

{-
naiveFoldL zeigt dass man foldl mit foldr schreiben kann
aber dies erklaert nicht die Musterloesung
-}
naiveFoldl :: (a -> b -> a) -> a -> [b] -> a
naiveFoldl f seed list
  = foldr (flip f) seed $ reverse list

-- naive version von reverse
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (h:t) = myReverse t ++ [h]

prop_MyReverse :: [Int] -> Bool
prop_MyReverse l = myReverse l == reverse l

myReverse2 :: [a] -> [a]
myReverse2 = foldr (\h t -> t ++ [h] ) [] 

prop_MyReverse2 :: [Int] -> Bool
prop_MyReverse2 l = myReverse2 l == reverse l

type DList a = [a] -> [a]

-- mit Differenz-Listen kann man reverse effizienter schreiben!
myReverse3 :: [a] -> [a]
myReverse3 list = (foldr fkt empty list) []
  where
     empty :: DList a
     empty = id
     fkt :: a -> DList a -> DList a
     fkt e l = l . ((:) e)

prop_MyReverse3 :: [Int] -> Bool
prop_MyReverse3 l = myReverse2 l == reverse l


{-
Man kann allgemein eine Funktion a->b als einen Wert interpretieren, in dem es ein Loch von Typ a gibt.
Um den Wert b zu bekommen muss man erst ein a zur Verfuegung stellen.
Interpretation for Differenz-Listen: [a] -> [a] entspricht einer Liste in der es eine Loch gibt,
das später durch eine andere Liste gefuellt werden kann.

Um foldl zu implementieren verwendet man Zwischenergebnisse mit einem Loch.
Der Trick besteht darin ein Loch mit einem neuen Term aufzufuellen,
wobei dieser neue Term aber wieder ein Loch enthaelt.
Den Seed fuegt man ganz zu letzt ein.
-}

foldHole :: forall a b .(a -> b -> a) -> a -> [b] -> a
foldHole fkt hole list = (worker list) hole
  where

{-
der gewuenscher Ausdruck hat die Form:
    ((((seed op 1) op 2) op 3) op 4)


zwischen Ergebnisse in worker:
    worker [] ~>               ___________hole___________________
    worker [4] ~>              (__________hole______________ op 4)
    worker [3,4] ~>            ((_________hole_______) op 3) op 4)
    worker [2,3,4] ~>          (((____hole_____) op 2) op 3) op 4)
    worker [1,2,3,4] ~>        (((( _hole_ op 1) op 2) op 3) op 4)

Typ des Ausdruck mit Loch : type withHole = (a -> a)
Typ von worker :: [b] -> withHole
-}

    worker :: [b] -> (a -> a)
    worker [] = firstHole
    worker (h:r) = \hole -> worker r (fkt hole h)
    firstHole = id

{-
Die Funktion worker in foldHole ist explizit rekursiv geschrieben.
Man kann foldHole aber leicht in eine Anwendung von foldr umschreiben.

foldrW :: (a -> b -> b) -> b -> [a] -> b
foldrW fkt seed list = worker list
  where
    worker []    = seed
    worker (h:r) = fkt h (worker r) 
-}


foldHole2 :: forall a b .(a -> b -> a) -> a -> [b] -> a
foldHole2 fkt seed list = (foldr fkt2 firstHole list) seed
  where
    firstHole = id
    fkt2 :: b -> (a -> a) -> (a -> a)
    fkt2 h r = \hole -> r (fkt hole h)

{-
Man beachte auch die Aehnlichkeiten zwischen foldHole2 und MyReverse3

Hier nochmal fkt2 mit einer Pseudo-Imperativen Erleuterung:

fkt2 :: b -> (a -> a) -> (a -> a)
fkt2 h r = \hole -> r (fkt hole h)

fkt2 nimmmt einen Wert h aus der Liste und ein Zwischenergebnis r.
Das Zwichenergebnis r ist ein Ausdruck mit einem Loch (Typ a->a)
fkt2 erzeugt ein neues Loch (namens hole)
und fuellt das Loch in r mit (fkt hole h)
-}

test3 = foldHole gref "seed" [1..4]