haskell: debugging <<loop>> exception

Question

For practising Haskell, I have implemented Fermat's factorization method (see https://en.wikipedia.org/wiki/Fermat%27s_factorization_method). However when I run my program, Haskell keeps telling me:

$ ./fermat 7
fermat: <<loop>>

so it seems, that there's an endless loop in my Code (cmp. http://www.haskell.org/pipermail/haskell-cafe/2013-June/108826.html). Can anyone give me a hint, what I'm doing wrong?

Also I would like to extend the question How to debug Haskell code? for tips on how this particular exception can be debugged.

import Data.List
import System.Environment
import Debug.Trace

isQuad :: Integer -> Bool
isQuad x = a == b
    where
        a = ceiling $ s
        b = floor $ s
        s = sqrt (fromIntegral x :: Double)

test :: Integer -> Integer -> Integer -> Bool
test nr n s = trace(show nr ++ " " ++ show n ++ " " ++ show s)
    isQuad(
        (+)
        ( (\j -> j * j) s + nr )
        (-n)
    )

fermat :: Integer -> (Integer, Integer)
fermat n =  (s + x, s - x)
    where
        s = ceiling $ sqrt (fromIntegral x :: Double)
        r = trace
            (show s ++ " " ++ show n)
            (\(Just i) -> i) $
            find
            (\nr -> test nr n s)
            [0..n]
        x = floor $ sqrt (fromIntegral r :: Double)

fact :: Integer -> (Integer, Integer)
fact x
    | x == 1 = (1, 1)
    | even x = (2, x `div` 2)
    | otherwise = fermat x

f :: String -> String
f x = x ++ " = " ++ show a ++ " x " ++ show b
    where
        (a, b) = fact $ (read x :: Integer)

main = do
    args <- getArgs
    putStrLn $ unlines $ map f args

Ganesh Sittampalam · Accepted Answer · 2014-09-04 19:57:58Z

5

In fermat, s depends on x, x depends on r, and r depends on s.

Sometimes laziness might make this kind of cyclic dependency ok, but in this case all the dependencies seem to be strict.

This is just from inspection and I don't have any particular advice on how to debug the problem in general beyond that in the linked post.

I would say that <<loop>> implies that the run-time system has been able to detect an infinite loop, which means that a value depends on itself, e.g. let x = x + 1 in x. So that's a bit of a clue for tracking down the problem.

If you wrote an infinite loop in function calls, e.g. let f x = f x + 1 in f 1, it typically would just run forever. Sometimes the optimizer might turn these function calls into values, but it can't do so in general.

answered Sep 4, 2014 at 19:57

Ganesh Sittampalam

29.2k4 gold badges82 silver badges102 bronze badges

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

Collectives™ on Stack Overflow

haskell: debugging <<loop>> exception

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related