Haskell: to fix or not to fix
fixpoint-combinators, haskell
Solution
One thing that can be gained by writing in an explicitly `fix`ed form is that the recursion is left "open".
factOpen :: (Integer -> Integer) -> Integer -> Integer
factOpen recur 0 = 1
factOpen recur n = n * recur (pred n)
We can use `fix` to get regular `fact` back
fact :: Integer -> Integer
fact = fix factOpen
This works because `fix` effectively passes a function itself as its first argument. By leaving the recursion open, however, we can modify which function gets "passed back". The best example of using this property is to use something like `memoFix` from the `memoize` package.
factM :: Integer -> Integer
factM = memoFix factOpen
And now `factM` has built-in memoization.
Effectively, we have that open-style recursion requires us impute the recursive bit as a first-order thing. Recursive bindings are one way that Haskell allows for recursion at the language level, but we can build other, more specialized forms.
Problem
I recently learned about `Data.Function.fix`, and now I want to apply it everywhere. For example, whenever I see a recursive function I want to "`fix`" it. So basically my question is where and when should I use it. To make it more specific: 1) Suppose I have the following code for factorization of `n`: ``` f n = f' n primes where f' n (p:ps) = ... -- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n -- if n<=1: returns [] -- otherwise: returns [(n,1)] ``` If I rewrite it in terms of `fix`, will I gain something? Lose something? Is it possible, that by rewriting an explicit recursion into `fix`-version I will resolve or vice versa create a stack overflow? 2) When dealing with lists, there are several solutions: recursion/fix, foldr/foldl/foldl', and probably something else. Is there any general guide/advice on when to use each? For example, would you rewrite the above code using `foldr` over the infinite list of primes? There are, probably, other important questions not covered here. Any additional comments related to the usage of `fix` are welcome as well.