-- strom, jehoz vrcholy obsahuji prvky typu a, a syn(ove) jsou ulozeni
-- ve strukture typu c

data Strom c a = Vrchol a (c (Strom c a))
data Jeden a = Jeden a
data Dva a = Dva a a

type Seznam a = Strom Jeden a
type BinarniStrom a = Strom Dva a
type ObecnyStrom a = Strom [] a

class Fold c where
  gfold :: (b->a->b) -> b -> c a -> b

instance Fold Jeden where
  gfold f x (Jeden y) = f x y
 
instance Fold Dva where
  gfold f x (Dva y z) = f (f x y) z

instance Fold [] where
  gfold f x [] = x
  gfold f x (h : t) = gfold f (f x h) t

-- odvodime instanci pro obecny strom

instance Fold c => Fold (Strom c) where
  gfold f x (Vrchol y s) = gfold f1 (f x y) s
    where
      f1 b t = gfold f b t

-- vypis Fold-ovatelne struktury (specialne stromu v preorderu)
-- neefektivni (kvadraticka casova slozitost)

vypis::(Show a, Fold c) => c a -> String
vypis s = gfold (\x y -> x ++ show y) "" s

-- chteli bychom pripojovat na zacatek
-- finta -- nepotrebujeme znat retezec predchozich prvku, ale nasledujicich !

-- type ShowS = String->String

vypisE::(Show a, Fold c) => c a -> String
vypisE s = (gfold (\x y -> x . shows y) id s) ""

-- podrobnejsi zapis:
-- vypisE s = (gfold (\x y zbytek -> x (shows y zbytek)) id s) ""
--
-- coz vyjde podobne jako
--
-- vypisE s = (gfold (\x y zbytek -> x (show y ++ zbytek)) id s) ""
-- pripojujeme na zacatek!