fix (defined in
Data.Function) is a function that calculates the least fixed point of a function.
fix :: (a -> a) -> a fix f = f (fix f)
For example, the fixed point of a function that always returns "hello" is
> fix (const "hello") "hello"
just "hello". This is because a fixed point is a point where the input and the output of a function become the same.
It is well known that recursive functions can be written as least fixed point of higher-order functions in domain theory.
fact :: Int -> Int fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)
You can also use
fix to write code in your everyday life. For example, let's implement a program that repeats the action of inverting the user's input and outputting it until the input "quit" is received.
main :: IO () main = do putStrLn "Start" fix $ \loop -> do str <- getLine unless (str == "quit") $ do putStrLn (reverse str) loop putStrLn "Bye"
If you don't use
fix, you can use
let to define the recursive function once and then execute it, but I think using fix is cleaner because you can define and execute it at once.
Next let's consider an example of setting a limit on the number of loops. Let's make a loop that terminates automatically after 3 loops, even if you don't type "quit".
main :: IO () main = do putStrLn "Start" flip fix 3 $ \loop n -> do unless (n == 0) $ do str <- getLine unless (str == "quit") $ do putStrLn (reverse str) loop (n-1) putStrLn "Bye"
You can give an initial value by flipping a fix. You can see this in the type, as shown below.
> :t flip flip :: (a -> b -> c) -> b -> a -> c > :t fix fix :: (a -> a) -> a > :t flip fix flip fix :: b -> ((b -> c) -> b -> c) -> c
In other words, you can think of the
fix type as
((b -> c) -> b -> c) -> b -> c and