0

I am pretty new to Haskell, so sorry for the question. But - how to get rid of the endless recursion and not been overflown. This is the code:

foo :: Integer -> Integer
foo x
    | x == 1         = 1
    | x <= 0         = error "negative number or zero"
    | odd x          = foo 3 * x + 1
    | x `mod` 2 == 0 = foo x `div` 2
    | otherwise      = x

EDIT:

foo :: Integer -> (Integer, Integer)
foo x
    | x == 1         = (1, z) 
    | x <= 0         = error "negative number or zero"
    | odd x          = foo  (3 * x + 1) . inc z
    | even x         = foo  (x `div` 2) . inc z
    | otherwise      = (x, z)
  where z = 0

inc :: Integer -> Integer
inc i = i + 1

I believe that the code is self-explanatory, but yet : If x is even then divide it with 2 otherwise 3*x + 1. This is part of the famous Collatz problem.

David Young
  • 10,713
  • 2
  • 33
  • 47
Dimitar
  • 4,402
  • 4
  • 31
  • 47
  • 1
    You could also use `even` instead of the `mod 2` test. And it seems like your `otherwise` case will never be reached. – Jeff Ames May 24 '15 at 00:29
  • In your edit, an expression like `f x . g y` associates like `(f x) . (g y)` instead of `(f x . g) y` because function application binds tighter than any operator. You could use `$` here (in fact, you might be mixing up `$` with `.`), but you could also just make the parentheses explicit and not use `.` or `$`. – David Young May 24 '15 at 02:54

1 Answers1

5

Function application has higher precedence than many other operations, so foo 3 * x + 1 is actually calling foo 3, then multiplying that result by x and adding 1, which looks like where your infinite loop might be.

Changing it to the following should fix that:

| odd x          = foo $ 3 * x + 1
| x `mod` 2 == 0 = foo $ x `div` 2
Jeff Ames
  • 1,424
  • 10
  • 18
  • could you explain what `$` is? – Dimitar May 24 '15 at 00:37
  • 2
    You could also write this as `f (3 * x + 1)`. See [this post](http://stackoverflow.com/questions/940382/haskell-difference-between-dot-and-dollar-sign) for a longer description of `$`. – Jeff Ames May 24 '15 at 00:40
  • When I want to increment it using `.` to count the number of times `foo` has been applied, what else should I do? It is in the edit part. – Dimitar May 24 '15 at 01:05
  • I could imagine doing something like `odd x = inc . foo $ 3 * x + 1`, and then defining `inc (x, i) = (x, i + 1)`, which makes `inc` have type `(Integer, Integer) -> (Integer, Integer)`. – Jeff Ames May 25 '15 at 03:09