import List


-- Some possible solutions for Haskell programming parts of DM22 exam
-- summer 2007

------------ Opgave 1 ---------------------------


-- straight-forward solution:
limit f x = if x == f x then x else limit f (f x)

-- another solution (looks involved, but the idea is simple):
limit' f x = (fst . head . dropWhile (uncurry (/=))) (zip fxs (tail fxs))
  where fxs = iterate f x

-- test function for limit
-- testfunc x = 3 + div x 2



expand s (x,y) = if x `subset` s then s `union` y else s


-- Some possibilities for the function subset, using the standard library
-- to varying degrees (\\ is the set diffence operator, defined in standard
-- library List):

subset x s = x \\ s == []

subset' [] _ = True
subset' (x:xs) s = elem x s && subset xs s

subset'' x s = all ((flip elem) s) x

subset''' x s = x == [a|a<-x, elem a s]

-- A version of subset crucially requiring both arguments to be dublicate
-- free (but using no library functions):
subset'''' x s = x == [a|a<-x, b<-s, a==b]


-- The function union is already contained in standard library List. Else
-- are here some possibilities:

union' x s = (x \\ s) ++ s

union'' x s = mkSet (x ++ s)

mkSet [] = []
mkSet (x:xs) = x : mkSet [y|y<-xs, y/=x]




-- (The explicit typing seems needed in the following definition, as
-- otherwise the type inference in Haskell for some reason fails)
expandList :: String -> [(String,String)] -> String
expandList = foldl expand

-- The same more detailed, without using currying (here, the type inference
-- does not fail):
expandList' s fdList = foldl expand s fdList

expandList'' s [] = s
expandList'' s (fd:fds) = expandList'' (expand s fd) fds


closure t fdList = limit ((flip expandList) fdList) t




---- Opgave 3 -------------------------------


findLongestLine :: IO ()
findLongestLine
  = do l1 <- getLine
       l2 <- getLine
       putStrLn "The longest of the two strings is:"
       putStrLn (if length l1 >= length l2 then l1 else l2)


---- Opgave 4 -------------------------------


gpfs1 xs = 0 : f 0 xs

f a [] = []
f a (x:xs) = s : f s xs
  where s = a+x

-- If type not written out for gpfs2, then Haskell deducts 
-- [Integer] -> [Integer] due to the disambiguating default thing.
gpfs2 :: Num a => [a] -> [a]
gpfs2 = scanl (+) 0

-- using a cyclic structure
gpfs3 xs = ys
  where ys = 0:zipWith (+) xs ys