! Write out the definition of init

init [] = []
init [x] = []
init (x:xs) = x : init xs

! Write out the definition of fold

foldr cons nil [] = nil
foldr cons nil (x:xs) = cons x (foldr cons nil xs)

! therefore nil = []

foldr cons [] [] = []
foldr cons [] (x:xs) = cons x (foldr cons [] xs)

! case analysis on xs in order to get three equations (like init has)

foldr cons [] [] = []
foldr cons [] [x] = cons x []
foldr cons [] (x:y:ys) = cons x (cons y (foldr cons [] ys))

! cons x [] = []

foldr cons [] [] = []
foldr cons [] [x] = []
foldr cons [] (x:y:ys) = cons x (cons y (foldr cons [] ys))

! cons x (y:ys) = x : y : ys

init = foldr cons [] where
 cons x [] = []
 cons x (y:ys) = x : y : ys