Haskell List function (map, zip, etc..) with fix

Question

I try to learn haskell and have exercise -try to rewrite standart list operation(map, foldr, zip, iterate, etc.) with function fix. I have example with repeat:

repeat a = fix $ \xs -> a : xs

and it's further simplify

repeat a = fix (a:)
repeat = fix . (:)

Can anyone help me with map? Sorry for my bad engl and thank u in advance.

Answer 1

To use fix, one needs to write the recursive definition in the form

map = .... something involving map .... 

Then, we let

map = fix (\m -> .... something involving m ....)

For instance,

map = \f xs -> case xs of
   []   -> []
   y:ys -> f y : map f ys

so,

map = fix (\m f xs -> case xs of
   []   -> []
   y:ys -> f y : m f ys)

Alternatively, since the argument f is the same for each recursive call, we can let

map f = \xs -> case xs of
   []   -> []
   y:ys -> f y : map f ys

and obtain

map f = fix (\m xs -> case xs of
   []   -> []
   y:ys -> f y : m ys)