CODEWITHSUNDEEP
haskellrecursion
brainoverflow
brainoverflow

Reputation: 745

how to print the iterations inside a Haskell recursion call?

Considering the code below which returns the factorial of a number:

factorial n = go n 1
  where
    go n ret | n > 1 = go (n-1) (ret * n)
             | otherwise = ret

how can I print n in every single recursive call of go n ret? Since n is being decremented each time, I want to see if I can print it every time it gets decremented (like 5 4 3 2 1). This is how I tried to do it (which is totally wrong) but I can't think of a different way:

factorial n = go n 1
  where
    go n ret | n > 1 = go (n-1) (ret * n) print n
             | otherwise = ret

Upvotes: 4

Views: 1109

Answers (3)

nicodp
nicodp

Reputation: 2392

The problem here is you are trying to do some IO (print) within a pure function (factorial): you can't do so in Haskell.

One workaround is to use the module Debug.Trace likewise:

import Debug.Trace

factorial n = go n 1
  where
  go n ret | ("n value is: " ++ show n) `trace` n > 1 = go (n-1) (ret * n)
           | otherwise = ret

And you'll get:

*Main Debug.Trace> factorial 5
n value is: 5
n value is: 4
n value is: 3
n value is: 2
n value is: 1
120

There are some caveats though as stated in the library:

The trace function should only be used for debugging, or for monitoring execution. The function is not referentially transparent: its type indicates that it is a pure function but it has the side effect of outputting the trace message.

As Daniel pointed out, if we want to enforce the multiplication to occur in each step of the evaluation, we have to rewrite this as follows:

factorial n = go n 1
  where
  go n ret | ("n value is: " ++ show n) `trace` n > 1 = go (n-1) $! (ret * n)
           | otherwise = ret

Upvotes: 3

Chris Martin
Chris Martin

Reputation: 30736

The type

To print, you'll need to lift the value into the I/O Applicative; the type will change from

factorial :: (Num a, Ord a) => a -> a

to

factorial :: (Num a, Ord a, Show a) => a -> IO a

What the go action does

The go action needs to do two things:

  1. print the number n
  2. either recursively call go or produce the result

How to do two I/O actions sequentially

To do two things, we need some combinator to combine them. The appropriate one here is *>:

(*>) :: Applicative f => f a -> f b -> f b

Sequence actions, discarding the value of the first argument.

This is exactly what we need because we don't need to use the value of the first action (the type of the print action is IO (), so it doesn't contain any useful result).

Lifting a value into I/O

We also need pure at the end

pure :: Applicative f => a -> f a

Lift a value.

to lift the result into the I/O Applicative.

The code

factorial n = go n 1
  where
    go n acc =
      print n *>
      if n > 1
        then let !acc' = acc * n
             in  go (n-1) acc'
        else pure acc

The ! in the binding of acc' forces the multiplication to occur immediately (thanks to Daniel Wagner for pointing out the need for this).

Testing in GHCi:

λ> factorial 5 >>= print
5
4
3
2
1
120

Upvotes: 3

Daniel Wagner
Daniel Wagner

Reputation: 152697

You can use (>>) to sequence IO actions and return to turn pure computations into IO actions. So:

factorial n = go n 1 where
    go n ret | n > 1 = print n >> go (n-1) (ret*n)
             | otherwise = return ret

Of course, factorial is now a function that produces an IO action; its callers may need to be fixed up to accommodate that.

Also, beware: due to laziness, none of the actual multiplications are done until after all of the printing! This is probably not what you intended. It won't matter much for the kinds of tests you'll be doing on a microbenchmark like this, but for larger functions that do more computation per iteration you might start to notice. You can fix this using $! or similar to make the computation of the IO action depend on the computation of this iteration's work. So:

factorial n = go n 1 where
    go n ret | n > 1 = print n >> (go (n-1) $! ret*n)
             | otherwise = return ret

Upvotes: 1

Related Questions