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 | fix :: (a -> a) -> a |

# 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 | Prelude> let fact n = if n == 0 then 1 else n * fact (n-1) in fact 5 |

- 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 | fix (2+) |

- 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 | f = fact' f |

- 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 | fix fact' |

# 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 | reverse' :: ([a] -> [a]) -> ([a] -> [a]) |

- 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 | foldr' :: ((a ->b ->b) ->b ->[a] ->b) ->((a ->b ->b) ->b ->[a] ->b) |

- 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）和本声明。