Haskell: to fix or not to fix

Question

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.

Explicative

"I have recently learned about Data.Function.fix, and now it seems to me that I want to apply it everywhere." This makes you a Boy Scout Haskell programmer then - willamette.edu/~fruehr/haskell/evolution.html#boyscout – Delois

You should use foldr and foldl' if you can, fix or explicit recursion if you must. The latter are less powerful so the reader of your code can deduce more properties from it. – Asquith

@stephentetley This is a great link, but I have already seen that! Actually, at the first time I saw it (and studied it through!) I had another question about couple of those implementations, but maybe some other time... Anyway, the "boyscout" implementation is exactly what I "tend" to do now in most of my code. :) – Explicative

@TomEllis If you could find some time to elaborate on this more, I would really appreciate that. Joseph has already given me a very good tip below regarding my first question, and I am still hoping to build a more general "guidelines" based on masters' experience. – Explicative

beware the difference between _Y f = f (_Y f) (recursion, value--copying) and fix f = x where x = f x (corecursion, reference--sharing). – Pl

@WillNess Thanks for this point. This is definetely something to keep in mind. I think if you post this as an answer with a simple example this will be a great answer for my question as well. – Explicative

Answer 1

One thing that can be gained by writing in an explicitly fixed 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.

Sidonie

Very interesting. And powerful! – Explicative

Answer 2

I'd like to mention another usage of fix; suppose you have a simple language consisting of addition, negative, and integer literals. Perhaps you have written a parser which takes a String and outputs a Tree:

data Tree = Leaf String | Node String [Tree]
parse :: String -> Tree

-- parse "-(1+2)" == Node "Neg" [Node "Add" [Node "Lit" [Leaf "1"], Node "Lit" [Leaf "2"]]]

Now you would like to evaluate your tree to a single integer:

fromTree (Node "Lit" [Leaf n]) = case reads n of {[(x,"")] -> Just x; _ -> Nothing}
fromTree (Node "Neg" [e])      = liftM negate (fromTree e) 
fromTree (Node "Add" [e1,e2])  = liftM2 (+) (fromTree e1) (fromTree e2)

Suppose someone else decides to extend the language; they want to add multiplication. They will have to have access to the original source code. They could try the following:

fromTree' (Node "Mul" [e1, e2]) = ...
fromTree' e                     = fromTree e

But then Mul can only appear once, at the top level of the expression, since the call to fromTree will not be aware of the Node "Mul" case. Tree "Neg" [Tree "Mul" a b] will not work, since the original fromTree has no pattern for "Mul". However, if the same function is written using fix:

fromTreeExt :: (Tree -> Maybe Int) -> (Tree -> Maybe Int)
fromTreeExt self (Node "Neg" [e]) = liftM negate (self e)
fromTreeExt .... -- other cases

fromTree = fix fromTreeExt

Then extending the language is possible:

fromTreeExt' self (Node "Mul" [e1, e2]) = ...
fromTreeExt' self e                     = fromTreeExt self e

fromTree' = fix fromTreeExt'

Now, the extended fromTree' will evaluate the tree properly, since self in fromTreeExt' refers to the entire function, including the "Mul" case.

This approach is used here (the above example is a closely adapted version of the usage in the paper).

Garmon

Great. This and Joseph's answer are two great examples of when fix seems to helpful. – Explicative

Isn't it fromTreeExt self (Node "Neg" [e]) = liftM negate (self e)? Using self instead of fromTree. – Flashover

@DanielVelkov Yes, typo. – Garmon

Answer 3

Beware the difference between _Y f = f (_Y f) (recursion, value--copying) and fix f = x where x = f x (corecursion, reference--sharing).

Haskell's let and where bindings are recursive: same name on the LHS and RHS refer to the same entity. The reference is shared.

In the definition of _Y there's no sharing (unless a compiler performs an aggressive optimization of common subexpressions elimination). This means it describes recursion, where repetition is achieved by application of a copy of an original, like in a classic metaphor of a recursive function creating its own copies. Corecursion, on the other hand, relies on sharing, on referring to same entity.

An example, primes calculated by

2 : _Y ((3:) . gaps 5 . _U . map (\p-> [p*p, p*p+2*p..]))

-- gaps 5 == ([5,7..] \\)
-- _U     == sort . concat

either reusing its own output (with fix, let g = ((3:)...) ; ps = g ps in 2 : ps) or creating separate primes supply for itself (with _Y, let g () = ((3:)...) (g ()) in 2 : g ()).

See also:

• double stream feed to prevent unneeded memoization?
• How to implement an efficient infinite generator of prime numbers in Python?

---

Or, with the usual example of factorial function,

gen rec n = n<2 -> 1 ; n * rec (n-1)            -- "if" notation

facrec   = _Y gen 
facrec 4 = gen (_Y gen) 4 
         = let {rec=_Y gen} in (\n-> ...) 4
         = let {rec=_Y gen} in (4<2 -> 1 ; 4*rec 3)
         = 4*_Y gen 3
         = 4*gen (_Y gen) 3
         = 4*let {rec2=_Y gen} in (3<2 -> 1 ; 3*rec2 2) 
         = 4*3*_Y gen 2                         -- (_Y gen) recalculated
         .....

fac      = fix gen 
fac 4    = (let f = gen f in f) 4             
         = (let f = (let {rec=f} in (\n-> ...)) in f) 4
         = let {rec=f} in (4<2 -> 1 ; 4*rec 3)  -- f binding is created
         = 4*f 3
         = 4*let {rec=f} in (3<2 -> 1 ; 3*rec 2)  
         = 4*3*f 2                              -- f binding is reused
         .....

Pl

Answer 4

1) fix is just a function, it improves your code when you use some recursion. It makes your code prettier.For example usage visit: Haskell Wikibook - Fix and recursion.

2) You know what does foldr? Seems like foldr isn't useful in factorization (or i didn't understand what are you mean in that). Here is a prime factorization without fix:

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->factIt x) $ xs
 where factIt n = map (\x->getFact x n []) [2..n]
   getFact i n xs
    | n `mod` i == 0 = getFact i (div n i) xs++[i]
    | otherwise      = xs

and with fix(this exactly works like the previous):

fact xs = map (\x->takeWhile (\y->y/=[]) x) . map (\x->getfact x) $ xs
  where getfact n  = map (\x->defact x n) [2..n]
       defact i n  = 
        fix (\rec j k xs->if(mod k j == 0)then (rec j (div k j) xs++[j]) else xs ) i n []

This isn't pretty because in this case fix isn't a good choice(but there is always somebody who can write it better).

Fodder