--- Some Haskell solutions for DM509 exam winter 2009 ---


-- 1a (several versions):

import List
-- for inits and tails (these are also in Section 4.5.2 in textbook).

cuts xs = map ((flip splitAt) xs) [0..length xs]

cuts' xs = zip (inits xs) (tails xs)

cuts'' xs = [splitAt i xs | i <- [0..length xs]]

cuts''' [] = [([],[])]
cuts''' l@(x:xs) = ([],l) : map addx (cuts xs)
  where addx (ys,zs) = (x:ys,zs)

-- 1b (several versions):

shifts xs = zipWith (flip (++)) firsts lasts
  where (firsts,lasts) = unzip (init (cuts xs))

shifts' xs = init (zipWith (++) (tails xs) (inits xs))

shifts'' xs = take (length xs) (iterate shift xs)
  where shift (y:ys) = ys ++ [y]

shifts''' xs = [zs++ys| (ys,zs) <- init (cuts xs)]

-- 1c (several versions):

permutations [] = [[]]
permutations (x:xs) = [ys++(x:zs)| p <- permutations xs, (ys,zs) <- cuts p]

permutations' [] = [[]]
permutations' (x:xs) = [l| p <- permutations' xs, l <- shifts (x:p)]

permutations'' [] = [[]]
permutations'' xs = [z:p| (ys,z:zs) <- cuts xs, p <- permutations'' (ys++zs)]

permutations''''' [] = [[]]
permutations''''' xs = [y:r | (y:ys) <- shifts xs, r <- permutations''''' ys]

-- NB: in permutations'' it seems that it would be necessary to have "init
-- (cuts xs)" instead of "cuts xs", to avoid the last tuple (xs,[]), but is
-- works anyway becaused in list comprehensions, pattern matching in a
-- generator works as a guard/filter (i.e. list values which fail to match
-- the pattern are just skipped).

-- All ideas above can be used without list comprehension, but it gets more
-- clumsy. E.g. here is a version of the first permutations:

permutations''' [] = [[]]
permutations''' (x:xs) = concat (map ((map g) . cuts) (permutations''' xs))
   where g (ys,zs) = ys++(x:zs)

-- or (same thing in smaller steps):

permutations'''' [] = [[]]
permutations'''' (x:xs) = concat yss
  where
    xss = map cuts (permutations'''' xs)
    yss = map (map g) xss
    g (ys,zs) = ys++(x:zs)

-- permutations''''' can be done without list comprehension without too
-- much hassle:

permutations'''''' [] = [[]]
permutations'''''' xs = phelp (shifts xs)
phelp [] = []
phelp ((x:xs):xss) = map (x:) (permutations'''''' xs) ++ phelp xss

-- 4a (the code from the question):

f [] y = y
f (x:xs) y = x: f y xs

-- 4e (two versions):

g [] = ([],[])
g (x:y:zs) = (x:xs,y:ys)
  where (xs,ys) = g zs

g' [] = ([],[])
g' (x:zs) = (x:ys,xs)
   where (xs,ys) = g' zs

-- 4f:

f1 xs ys = (reverse mix) ++ yrest
   where
     (mix,yrest) = foldl h e xs
     e = ([],ys)

h (acc,[]) x = (x:acc,[])
h (acc,(y:ys)) x  = (y:x:acc,ys)

-- for testing in 4d:

mylength:: [a] -> Int

mylength [] = 0
mylength (x:xs) = 1 + mylength xs