Haskell Mini Function Implementation

Question

I have been trying to take this function and make small implementation using iterate and takeWhile. It doesn't have to be using those functions, really I'm just trying to turn it into one line. I can see the pattern in it, but I can't seem to exploit it without basically making the same code, just with iterate instead of recursion.

fun2 :: Integer -> Integer
fun2 1 = 0
fun2 n 
    | even n = n + fun2 (n `div` 2)
    | otherwise = fun2 (3 * n + 1)

Any help would be great. I've been struggling with this for hours. Thanks

Answer 1

If you want to do this with iterate, the key is to chop it up into smaller logical parts:

• generate a sequence using the rule

  a_k+1 = a_k/2 if a_k even

  a_k+1 = 3a_k+1 if a_k odd

• stop the sequence at a_j = 1 (which all do, if the collatz conjecture is true).

• filter out the even elements on the path
• sum them

So then this becomes:

  f = sum . filter even . takeWhile (>1) . iterate (\n -> if even n then n `div` 2 else 3*n + 1)

However, I do think this would be clearer with a helper function

  f = sum . filter even . takeWhile (>1) . iterate collatz
    where collatz n | even n    = n `div` 2
                    | otherwise = 3*n + 1

This may save you no lines, but transforms your recursion into the generation of data.

Answer 2

Firstly, I agree with tom's comment that there is nothing wrong with your four line version. It's perfectly readable. However, it's occasionally a fun exercise to turn Haskell functions into one liners. Who knows, you might learn something!

At the moment you have

fun 1 = 0
fun n | even n    = n + fun (n `div` 2)
      | otherwise = fun (3 * n + 1)

You can always convert an expression using guards into an if

fun 1 = 0
fun n = if even n then n + fun (n `div` 2) else fun (3 * n + 1)

You can always convert a series of pattern matches into a case expression:

fun n = case n of
            1 -> 0
            _ -> if even n then n + fun (n `div` 2) else fun (3 * n + 1)

And finally, you can convert a case expression into a chain of ifs (actually, in general this would require an Eq instance for the argument of your function, but since you're using Integers it doesn't matter).

fun n = if n == 1 then 0 else if even n then n + fun (n `div` 2) else fun (3 * n + 1)

I think you'll agree that this is far less readable than what you started out with.