-- Data.hs

data Record = Record {attr1 :: Int, attr2 :: Bool}

a = Record 0 True

b = a {attr2 = False}

-- data Bool = True | False

-- data Maybe a = Nothing | Just a

-- maybe x f Nothing  = x
-- maybe x f (Just a) = f a


-- finite lists				     the standard list type

data List a = Nil | App a (List a)	     -- data [a] = [] | a : [a]
              deriving Show

Nil @@ s          = s			     -- [] ++ s     = s
(a `App` s) @@ s' = a `App` (s @@ s')	     -- (a:s) ++ s' = a:(s ++ s')

head_ Nil         = Nothing
head_ (a `App` _) = Just a		     -- head (a:_) = a

tail_ Nil         = Nothing
tail_ (_ `App` s) = Just s		     -- tail (_:s) = s

-- binary trees

data Bintree a = Empty | Node (Bintree a) a (Bintree a)
	         deriving Show

leaf a = Node Empty a Empty

isLeaf (Node Empty _ Empty) = True
isLeaf _ 		    = False

fringe :: Bintree a -> [a]

fringe t@(Node l a r) = if isLeaf t			-- fringe t@(Node l a r)
			then [a]			--   	| isLeaf t = [a]
			else fringe l ++ fringe r	--   	| True     = fringe l ++ fringe r
fringe _              = []

swap (Node l a r) = Node (swap r) a (swap l)
swap _            = Empty

-- instance Show a => Show (Bintree a) where
--  showsPrec _ = showBt

showBt Empty        = ("Empty"++)
showBt (Node l a r) = ('(':) . ("Node "++) . showBt l . (' ':) . shows a .
	              (' ':) . showBt r . (')':)


-- trees with arbitrary finite outdegree

data Tree a = T a [Tree a] deriving Show

fringeT (T a []) = [a]
fringeT (T _ s)  = concatMap fringeT s


-- further list functions

-- recursive definition				intensional definition
--					        using list comprehension

-- map :: (a -> b) -> [a] -> [b]

-- map f []    = []
-- map f (a:s) = f a:map f s			map f s = [f x | x <- s]

-- foldl :: (a -> b -> a) -> a -> [b] -> a

-- foldl g a []    = a
-- foldl g a (b:s) = foldl g (g a b) s

-- sum = foldl (+) 0
-- product = foldl (*) 1
-- concat = foldl (++) []

-- concatMap f = concat . map f

-- zip (x:s) (y:s') = (x,y):zip s s'		zip s s' = [(s!!n,s'!!n)
-- zip _ _          = []				    | n <- [0..length s-1],
--							      length s == length s']

-- zipWith f (x:s) (y:s') = 
--     (f x y):zipWith f s s'			zipWith s s' = [f (s!!n) (s'!!n)
-- zipWith f _ _          = []				        | n <- [0..length s-1],
--							          length s == length s']

-- take 0 _             = []			take n s = [s!!i | i <- [0..n-1]]
-- take n (x:s) | n > 0 = x:take (n-1) s			   
-- take _ _             = []


-- drop 0 s 	        = s			drop n s = [s!!i | i <- [n..length s-1]]
-- drop n (_:s) | n > 0 = drop (n-1) s
-- drop _ _             = []

intsFrom i = i:intsFrom (i+1)

-- scanl :: (a -> b -> a) -> a -> [b] -> [a]	definition using a regular equation

-- scanl g a []    = [a]			scanl g a s = s' where s' = a:zipWith g s s'
-- scanl g a (b:s) = a:scanl g (g a b) s

sums = scanl (+) 0
products = scanl (*) 1
concats = scanl (++) []