Haskell recursion stack overflow

Question

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.

You could also use even instead of the mod 2 test. And it seems like your otherwise case will never be reached. — Jeff Ames
– Jeff Ames, Commented May 24, 2015 at 0: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
– David Young, Commented May 24, 2015 at 2:54

Jeff Ames · Accepted Answer · 2015-05-24 00:23:41Z

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

answered May 24, 2015 at 0:23

Jeff Ames

1,44610 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Dimitar Over a year ago

could you explain what $ is?

Jeff Ames Over a year ago

You could also write this as f (3 * x + 1). See this post for a longer description of $.

Dimitar Over a year ago

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.

Jeff Ames Over a year ago

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

Collectives™ on Stack Overflow

Haskell recursion stack overflow

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related