{-
 - Opgaver på ugeseddel 10 fra "Skriftlig Eksamen Januar 2000"
 -}
module Uge10 where

-- Opgave 1.a

{-
  map :: (a -> b) -> [a] -> [b]
  (.) :: (a -> b) -> (c -> a) -> c -> b

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

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

-- Opgave 2.a

triads :: Int -> [(Int, Int, Int)]
triads n = [ (x,y,z) | x <- [2..n],
	               y <- [x+1..n],
                       z <- [y+1..n],
                       x*x + y*y == z*z]

-- Opgave 2.b

-- Løsning 1 (fra bogen -- ikke lexicografisk)
alltriads :: [(Int, Int, Int)]
alltriads = [ (x,y,z) | z <- [1..],
                        y <- [2..z-1],
                        x <- [2..y-1],
                        x*x + y*y == z*z]

-- Løsning 2: I lexicografisk orden
alltriads2 :: [(Int, Int, Int)]
alltriads2 = [ (x,y,z) | x <- [2..],
                         y <- [x+1 .. (x*x) `div` 2],
                         z <- [round (sqrt (fromInt (x*x + y*y)))],
                         x*x + y*y == z*z]


                        
-- Opgave 3

data Htree a = Null | Fork a (Htree a) (Htree a)

-- Opgave 3.a

levels :: [a] -> [[a]]
levels = levelsWith 1

levelsWith :: Int -> [a] -> [[a]]
levelsWith _ [] = []
levelsWith n xs = 
  y : levelsWith (2*n) ys
  where 
    (y,ys) = splitAt n xs

-- Opgave 3.b

mkHtrees :: [[a]] -> [Htree a]
mkHtrees = foldr addLayer [Null]

addLayer :: [a] -> [Htree a] -> [Htree a]
addLayer []     _          = []
addLayer (x:xs) []         = Fork x Null Null : addLayer xs []
addLayer (x:xs) (t:[])     = Fork x t    Null : addLayer xs []
addLayer (x:xs) (t0:t1:ts) = Fork x t0   t1   : addLayer xs ts

-- Opgave 3.c

mkHtree :: [a] -> Htree a
mkHtree = head . mkHtrees . levels