Fix in Haskell

There’re many interesting features in Haskell, here I want to introduce and analyse the Fixed-point combinator, which spent me several hours understanding but only scratched the surface.

Definition Of Fix

  • You can find the definition of Fix function in wiki. The definition is
1
2
fix :: (a -> a) -> a
fix f = let x = f x in x

Fix And Recursion

  • It seems a little confused. What does let x = f x in x mean? For example, GNU is GNU is not Unix, so how could you expand GNU? GNU GNU GNU ... GNU is not Unix? Another example, let x = (1:) x in x, what will x like? A list of infinite 1. Still confused? You can try let x = x + 2 in x, this will cause an exception because of stack overflow. The reason is that the (+2) operation is expanded constantly. So what is fix exactly? Fix can be imported from Control.Monad.Fix, its definition has been given above.

  • Now we can learn the power of Fix from an example. The fact is used to calculate factorial, here we calculate 5!. There are two kind of implements, the first is common recursion, like first line below. Instead, we can use Fix to rewrite it. We pass a lambda function to fix as a parameter, the lambda function receives rec and n as parameters, rec here is abstracted and it was initialized by if n == 0 then 1, this is indeed initialized for the lambda function, however you can think it as an anonymous rec.

1
2
3
4
Prelude> let fact n = if n == 0 then 1 else n * fact (n-1) in fact 5
120
Prelude> fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5
120
  • In fact, from the definition of Fix, we know that fix means a fixed-point. What we need to do is to write the equation for fix like below. Fix is used to find a fixed-point for given function.
1
f (fix f) = fix f
  • So why fix (+2) is getting an exception? There is no x for x == x + 2, so fix cannot find an fixed-point for (+2). That’s why fix finally came into stack overflow. Now we are going to learn what fix works in details. We can expand fix like below.
1
2
3
4
5
6
7
8
9
10
11
fix (2+)
= 2 + (fix (2+))
= 2 + (2 + fix (2+))
= 2 + (2 + (2 + fix (2+)))
= 2 + (2 + (2 + (2 + fix (2+))))
= ...

fix (1:)
= 1 : fix (1:)
= 1 : (1 : fix (1:))
= 1 : (1 : (1 : fix (1:)))
  • As you can see, fix (1:) can work fine since the lazy evaluation of Haskell. If we pass fix (1:) to show, GHCI can still work and output [1, 1, 1, .... Return to the fact example now, how does it work? We write that lambda function passed to fix as a named function fact' here, the definition is fact' rec n = if n == 0 then 1 else n * rec (n-1). Pass this to fix, fix will find a fixed-point of fact', which is the function f such that f == fact' f. So we can write fact' like below.
1
2
f = fact' f
= \n -> if n == 0 then 1 else n * f (n-1)
  • Are you familiar with the equation above? The f substitute rec in fact', and f also acts as fact' f, which is just recursion. So expand fix as we always did. (Codes below are copied from wiki)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
fix fact'
= fact' (fix fact')
= (\rec n -> if n == 0 then 1 else n * rec (n-1)) (fix fact')
= \n -> if n == 0 then 1 else n * fix fact' (n-1)
= \n -> if n == 0 then 1 else n * fact' (fix fact') (n-1)
= \n -> if n == 0 then 1
else n * (\rec n' -> if n' == 0 then 1 else n' * rec (n'-1)) (fix fact') (n-1)
= \n -> if n == 0 then 1
else n * (if n-1 == 0 then 1 else (n-1) * fix fact' (n-2))
= \n -> if n == 0 then 1
else n * (if n-1 == 0 then 1
else (n-1) * (if n-2 == 0 then 1
else (n-2) * fix fact' (n-3)))
= ...

Implementation Of Foldr & Reverse

  • I am going to show some of the applications of fix. First is reverse. We can write reverse' as the parameter of fix. The type system of reverse' is ([a] ->[a]) -> ([a] -> [a]). Notice that I use a pair of parentheses out of [a] -> [a], that’s because curry. reverse' is just like fact', it receives a function f, and fix is going to find a f which satisfies f = reverse' f. Now we can easily write reverse' below.
1
2
3
4
5
6
7
8
9
10
11
12
13
reverse' :: ([a] -> [a]) -> ([a] -> [a])
reverse' f [] = []
reverse' f (x:xs) = f xs ++ [x]

reverse = fix reverse'

-- expand the definition above
(fix reverse') [1,2,3]
= (reverse' (fix reverse')) [1,2,3]
= (reverse' f) [1,2,3]
= f [2,3] ++ [1]
= (reverse' f) [2,3] ++ [1]
= ...
  • Another example I am going to talk is foldr. I found the kata about fix in Codewars, you can see it here. I didn’t pass the time limitation, and finally I got clues from conversations. There are several ways to write foldr by fix, however, you need to maintain the feature of foldr, the lazy evaluation. I will show two of them both satisfying the lazy evaluation.
1
2
3
4
5
6
7
8
9
foldr' :: ((a ->b ->b) ->b ->[a] ->b) ->((a ->b ->b) ->b ->[a] ->b)
foldr' f g acc [] = acc
foldr' f g acc (x:xs) = f g (g x acc) xs

foldr' :: ((a ->b ->b) ->b ->[a] ->b) ->((a ->b-> b) ->b ->[a] ->b)
foldr' f g acc [] = acc
foldr' f g acc (x:xs) = g x (f g acc xs)

foldr = fix foldr'
  • Which is better? In my own opinion, the first is better since it is written in a format of tail-end recursion. This would not expand the stack space it used. However, the second needs to expand until the end of the list. But, after my experiment testing big integers, both of them met stack overflow at the same size while works as same as each other when they can deal with the parameters. This proved that my thought was wrong. So, why the two formats have same performance? Stay for thought.

I hope this article could give you some help. If this article has any error, or you have some problems/suggestions, please e-mail me. I am glad to learn from each other.

原创作品,允许转载,转载时无需告知,但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/10/08/haskell-fixit/) 、作者信息(Forec)和本声明。

分享到