Printing a result during a recursion in haskell

Question

Hi I am beginning to learn Haskell and am making a program to do the iterative process:

n -> n/2 (for even n)
n -> 3n+1 (for odd n)

So I got this far:`

chain n     | n == 0       = error "What are you on about?"
            | n == 1       = error "Finished"
            | rem n 2 == 0 = chain (n `div` 2) 
            | rem n 2 /= 0 = chain (3 * n + 1)

` Will this work? But it only does the calculations behind the scenes, is there any way to make it display or export as list the result for n on each iteration until it reaches 1 so I can find the length of the list later?

On a side note, is there any way to make GHCi begin in a specific folder ?(I'm using windows)

Answer 1

You could have it return a list of the results in the "chain" like this:

chain n     | n == 0       = error "What are you on about?"
            | n == 1       = []
            | rem n 2 == 0 = (n `div` 2) : chain (n `div` 2)
            | otherwise    = (3 * n + 1) : chain (3 * n + 1)

Now you'll get results like these:

*Main> chain 3
[10,5,16,8,4,2,1]
*Main> chain 7
[22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Answer 2

Yes, certainly. There's even a function from the Data.List module that captures this usage pattern.

import Data.List (unfoldr)

chain 0 = []
chain n = unfoldr f n
  where
    f 1 = Nothing
    f n = let n' | even n    = n `div` 2
                 | otherwise = 3 * n + 1
          in Just (n', n')

The type of unfoldr is: (b -> Maybe (a, b)) -> b -> [a]

b is the state variable that used to generate the list. The function supplied as the first argument to unfoldr should either returns Nothing (which means terminate the list) or Just (b, a) where a is the element to add to the list, and b is the new state variable.

Answer 3

You will notice that the two earlier answers use the paradigm of "build the whole list, and then output it at the end" rather than "output one element at a time". This is the functional way of doing things.

If you really want to do it in an imperative style, you have to use monadic programming, which is a more advanced topic. Here's an example (don't worry if you can't understand everything that's going on ... monads are quite mysterious and magical):

import Control.Monad.Writer

chain :: Int -> (String, [Int])
chain = runWriter . chain'
    where
      chain' 0 = return "Failure"

      chain' 1 = do
        tell [1]         -- write 1
        return "Success" -- finished

      chain' n = do
        -- write n
        tell [n]
        -- calculate next n and recurse
        if even n
           then chain' $ n `div` 2
           else chain' $ 3 * n + 1

Which gives results like:

*Main> chain 3
("Success",[3,10,5,16,8,4,2,1])

But, as you can see, the writer monad still just generates the list behind the scenes.

This might seem inefficient. What if you want to print a list of 1,000,000 elements? Do you really have to generate the whole list upfront? In fact, Haskell's lazy semantics mean that, whenever possible, Haskell will compile your "build the whole thing upfront and then print it out" code into "only generate and output one element at a time" code.

Answer 4

The function should just return the list of found elements. This list can be inspected further later on:

chain 0 = error "No no no."
chain 1 = [1]
chain n
  | rem n 2 == 0 = n : chain (n `div` 2) 
  | otherwise    = n : chain (3 * n + 1)

Here [1] is a list containing just 1 and : is a list constructor that adds the element on the left to the list on the right.

The list constructed by chain can then be displayed or used with other functions:

*Main> chain 5
[5,16,8,4,2,1]
*Main> length (chain 31)
107

Answer 5

is there any way to make it display or export as list the result for n on each iteration until it reaches 1

You can use the Debug.Trace.trace to print logging messages to stdout as values are evaluated. Good for quick debugging.