fixing at higher orders
In reminding myself about the fixed-point combinator yesterday, I wrote some sample functions in Haskell such as fib, prod, and sum. Eventually I convinced myself that I could write a fold but I only got so far. I have that
import Data.Function (fix) foldGenerator :: (b -> a -> b) -> b -> ([a] -> b) -> ([a] -> b) foldGenerator f b g (x:[]) = b `f` x foldGenerator f b g (x:xs) = g xs `f` x myFold :: (b -> a -> b) -> b -> [a] -> b myFold f b = fix (foldGenerator f b)
This is all well and good, but what I really like is to find some f such that fix f = fold. I would be fine even with just getting a fold1. But everything seems so much higher order that I'm not sure if it's possible. Does anyone know if it is? Can anyone point to a reference that does this sort of thing, or even just let me know if it's possible in principle?