Infinite loop in haskell program

Question

The following code gives me a stack overflow error in some cases (ex hosum (\x->x `mod` 3) 1000 ) and I don't understand why. Could anyone explain this to me? (I am new to Haskell and I'd appreciate any help :) )

 hosum :: (Int -> Int) ->  (Int -> Int)
    hosum f  = (\x -> hs f x (- x))
            where hs :: (Int -> Int) -> Int -> Int -> Int
                  hs f 0 0 = f 0
                  hs f n m
                          | m <= n 
                          = f m + hs f n (m+1)
                          | n <= m 
                          = f n + hs f (n+1) m
                          | otherwise
                          = 0

Phil Kiener · Accepted Answer · 2017-04-02 18:10:56Z

3

The stack overflow is likely caused by the infinite recursion. Your guards are m <= n and n <= m; for every n and m, one of those is always true. Your otherwise is never reached, the recursion never terminates. You probably meant your guards to be m < n and n < m.

Your hs should therefore be

hs f 0 0 = f 0
hs f n m | m < n     = f m + hs f n (m + 1)
         | m > n     = f n + hs f (n + 1) m
         | otherwise = 0

Because of that last guard, you could even remove the pattern hs f 0 0; the otherwise catches that one.

answered Apr 2, 2017 at 18:10

Phil Kiener

7781 gold badge7 silver badges15 bronze badges

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

2 Comments

Eirini Over a year ago

oh ok, I understand. Thank you so much :)

chi Over a year ago

I second removing the hs f 0 0 case. It looks funny to see that as a base case, when n,m are increasing (by 1) in each recursive call.

Collectives™ on Stack Overflow

Infinite loop in haskell program

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related