Haskell school of expression fix function

Question

So I am reading Paul Hudak's book "The Haskell School of Expression" and am stuck on an exercise in there.

Here it goes

Suppose function fix is defined as

fix f = f (fix f)

What is the principal type of fix? That one I know, it's b -> b -> b

But I don't understand the way fix is defined, won't it go into an infinite recursion?

Also, let the remainder function be defined as

remainder :: Integer -> Integer -> Integer
remainder a b = if a < b then a 
                else remainder (a - b) b

Rewrite remainder using fix so that it is non-recursive.

I added a missing `then` to your `if`. Otherwise, your `remainder` function is not valid Haskell... — Alec, Nov 19 '16 at 16:57
Haskell uses lazy evaluation. `f (fix f)` calls the outer `f` first, not `fix`. — melpomene, Nov 19 '16 at 16:57
For many functions `fix` will indeed go into infinite recursion without returning. However for many it wont. For example `fix (const 1)` or `fix (1:)`. — Julia Path, Nov 19 '16 at 16:58
How would it not go into infinite recursion for (const 1) and (1:) — Abdul Rahman, Nov 19 '16 at 17:01
Nice I see it for (1:) and (const 1). Its haskell's lazy evaluation :) — Abdul Rahman, Nov 19 '16 at 17:03

Alec · Accepted Answer · 2016-11-19T17:10:18.653

First of all the principal type of fix is actually (b -> b) -> b (remember that only b -> (b -> b) is the same as b -> b -> b).

In a strict language, such a definition would go into infinite recursion, but because Haskell is lazy, the arguments to a function are evaluated only if they are at any point needed. For example you can define factorial.

-- with recursion
factorial :: Int -> Int
factorial n = if n == 0 then 1 else n * factorial (n-1)

-- with `fix`
factorial' :: Int -> Int
factorial' = fix (\f n -> if n == 0 then 1 else n * f (n - 1))

Following the same pattern, you should be able to define remainder.

score 2 · Answer 2 · answered Nov 19 '16 at 19:28

Playing with it a little gives us

fix f         = f (fix f)                                            -- definition
fix f     a   = f (fix f) a                                          -- eta expansion
fix f     a b = f (fix f) a b                                        -- eta expansion
remainder a b = if a < b then a else remainder (a - b) b             -- definition
-- we want  remainder = fix f:                                       -- equation
fix f     a b = if a < b then a else (fix f)   (a - b) b             -- substitution
       = (\g -> if a < b then a else g         (a - b) b) (fix f)    -- abstraction
   = fix (\g -> \a b -> if a < b then a else g (a - b) b) a b        -- abstraction

thus

remainder = 
     fix (\g     a b -> if a < b then a else g (a - b) b)            -- eta reduction

Haskell school of expression fix function

2 Answers2