Haskell execution sequence

Question

Hi can anybody help me understand this code

solve s | s == 0 = Nothing
        | s == 1 = Just 1
        | otherwise = 
          check [solve (s-(x*2)) | x <- [1..9]]

 check x = case x of
           []           -> Nothing
           (Nothing:xs) -> check xs
           (x:xs)       -> x

why this gives stack over flow when i tried to run it with even value, and is there any way in haskell where i can debug and see the actual value of the running program , like in eclipse we do ?

thanks

Answer 1

Stack overflow suggests an infinite recursion. Branching on the otherwise case of "solve" is not guaranteed to terminate. I'm not sure what the code is supposed to be doing here, so I cannot suggest a fix. Hope that helps!

Answer 2

At least with GHCi, there's no way to "step" through code (Edit: no longer true, see comment below), but you can certainly add debug statements using Debug.Trace. In other words if you wanted to check all the recursive calls to solve you could say:

check [trace ("solving for " ++ show (s-(x*2)))) (solve (s-(x*2))) | x <- [1..9]]

There are cleaner ways to write that but that just illustrates the idea.

In this particular case, the reason it recurses infinitely is that the base cases of solve will never be reached. solve 2 for example, resolves to check [solve 0, solve -2, solve -4 ..., solve -16] and solve -2 resolves to check [solve -4, solve -6, ...] etc.

Answer 3

solve s | s == 0 = Nothing
        | s == 1 = Just 1
        | otherwise = 
          check [solve (s-(x*2)) | x <- [1..9]]

In the case of solve 2:

(2 - (1 * 2)) = 0 (0 - (2 * 2)) = -2

et cetera.

I'm not sure about the debugging stuff, but that's why it's overflowing the stack. It's infinitely recursing.

Answer 4

Adding to Dan's answer, you can simply push trace there in solve, and that'll show the problem.

solve s | s == 0 = Nothing
        | s == 1 = Just 1
        | otherwise = 
          trace (show s) $ check [solve (s-(x*2)) | x <- [1..9]]

Answer 5

You can rewrite that first parts using pattern matching instead, it's a lot nicer notation than guards (if-statements) ;)

solve 0 = Nothing
solve 1 = Just 1
solve s = check [solve (s - (x * 2)) | x <- [1..9]]

The list comprehension feed the range 1 through 9 to the solve method, which calls solve with s - (x * 2) and honestly, I can't intuitively tell that that's gonna terminate... but let's consider some examples.

solve 2

Calling solve 2 will result in the following list, since Haskell is lazy that list won't have values until you (have side-effects) try and print these...

solve s - 1 * 2
solve s - 2 * 2
solve s - 3 * 2
solve s - 4 * 2
solve s - 5 * 2
solve s - 6 * 2
solve s - 7 * 2
solve s - 8 * 2
solve s - 9 * 2

A simple solve 2 will try solve -2 which will try and solve other things, and that' won't end.

Answer 6

check :: [Maybe a] -> Maybe a
check =  Data.Maybe.listToMaybe . Data.Maybe.catMaybes

solve :: (Num a, Num b) => a -> Maybe b
solve 0 = Nothing
solve 1 = Just 1
solve s = solve (s-2)

here, it is pretty obvious that solve -1 and solve 5.3 will run infinite. this version of solve will run just like a while loop. the original version you posted will spam in every call unneeded stuff into your ram/stack.

you can rewrite this:

solve s = check [solve (s-x)|x<-[2,4..18]]

to this:

solve s = check [solve (s-2),solve (s-4),solve (s-6),solve (s-8),solve (s-10),solve (s-12),solve (s-14),solve (s-16),solve (s-18)]

but whenever solve (s-2) returns Nothing, then each solve (s-x) will return Nothing, because that value was already tested like this: solve ((((s-2)-2)-2)-2)

it is an exponential algorithm to test sth, which could be tested in linear time or calculated in constant time.

i suggest to read this book: Haskell: The Craft of Functional Programming