DEV Community

lotz
lotz

Posted on • Updated on

Write a simple loop with fix

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)

Write a simple loop with fix

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.

Give the loop an initial value

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 flip.

Latest comments (0)