CODEWITHSUNDEEP
haskell
Quentin Liu
Quentin Liu

Reputation: 141

Arithmetic error when trying to add two numbers

I tried to implement a function that takes a limit and a string, parses the string and tests if the parsed number exceeds the limit. The function works well only for strings without 0s in it, like "123". However, it could not parse strings correctly like "100", whose result is 1.

What caused this problem?

Below is the code. 

reachBounded :: Int -> String -> Maybe Int 
reachBounded limit str = case str of 
    ""  -> Nothing 
    "0" -> Just 0
    _   -> foldr (\digit s -> do 
                sum <- s
                let n = sum * 10 + digitToInt digit 
                guard (isDigit digit) 
                guard (n <= limit) 
                return n)
            (Just 0) str

Moreover, is there any way to debug this code like we normally do in imperative languages? I found ghci debugger only able to print the type, not the value.

Upvotes: 1

Views: 147

Answers (1)

Steven Armstrong
Steven Armstrong

Reputation: 475

This is a very imperative way of solving the problem, and if you keep thinking like that you're going to have difficulties moving forward.

Here's how you might want to re-think the problem:

Replace "I have a list of characters, but I want digits, I'll iterate and replace them one by one" with "I have a list of characters but I want digits, I'll just replace them all at once" (I'm going to assume you want to actually parse the string yourself fully manually rather than just using read or some kind of parsing tool)

So far we have:

reachBounded limit str = ... map digitToInt str

Next, you want to turn these digits into a number. Replace "I want to iterate through this list increment a sum" with "I need to know the place value of each digit". We can do this by reversing the digits and multiplying them pairwise with the list [1,10,100,1000...]. We can produce the place value list by mapping (10^) over the list of positive integers, or declaring that each element is 10 times the previous, starting with 1. Let's use the latter:

reachBounded limit str = ... zipWith (*) (iterate (*10) 1) $ reverse $ map digitToInt str

And we want the sum of these place values:

reachBounded limit str = ... where
    val = sum $ zipWith (*) (iterate (*10) 1) $ reverse $ map digitToInt str

Lastly, we must check if it's within the bound given:

reachBounded limit str = val <$ guard (val < limit) where
    val = sum $ zipWith (*) (iterate (*10) 1) $ reverse $ map digitToInt str

In this case a <$ b will replace the contents of b with a if b is Just something, and leave it alone if b is Nothing.

In terms of debugging, it is now trivial, as it is not some process we need to interrupt, but a series of values that we manipulate to get the desired result. You cannot run part of your process on each step and get a sensible answer, but here we can look at the result produced by any of these stages and see if we are on track.

There isn't a toMaybe :: (a -> Bool) -> a -> Maybe a function. I'm not sure why, but with one and using read, the solution is merely:

bounded l = toMaybe (<l) . read

Or using the Safe library...

bounded l = toMaybe (<l) <=< readMay

Which will not throw exceptions if you don't input a string that actually represents a number.

Now, let's say you really do want to write your algorithm iteratively, maybe you need to for performance or it's just one of those algorithms that doesn't readily admit a declarative implementation (there aren't many of those, though). It's still going to be cleaner to use values instead of exceptions, but you need to stop and look at it sometimes.. so what do you do?

Let's write our own iterator function:

data Iter a b c = Next a | Final b | Error c

iterateE :: (a -> Iter a b c) -> a -> ([a], Either c b)
iterateE f = go where
    go x = case f x of
        Next a -> let (list, final) = go a in (x:list, final)
        Final b -> ([x], Right b)
        Error c -> ([x], Left c)

This more directly encapsulates stopping the fold early and tracking the intermediate results - even though you can also just stop folds early and track the intermediate results - this is a simpler way to think about it for now. This will provide you with a complete list of all intermediate states and either a result or error that your iterator function can choose to terminate with.

Transforming your solution into this format...

reachBounded limit str = iterateE iter (Just 0,str) where
    iter (n, []) = Final n
    iter (n, (s:str)) = Next (do
        sum <- s
        let n = sum * 10 + digitToInt digit 
        guard (isDigit digit) 
        guard (n <= limit) 
        return n, str)

... we don't don't announce any error in this code, but this will let us see what's happened at each step, and also doesn't have a direction in the fold, so you can't get it backwards between left and right.

Upvotes: 4

Related Questions