How to recursively compare the digits in a number in Haskell

Question

Hi

I am doing problem 112 on Project Euler and came up with the following to test the example case (I'll change the number in answer to 0.99 to get the real answer):

isIncre  x | x == 99 = False
        | otherwise = isIncre' x
       where
        isIncre' x = ???

isDecre  x = isIncre (read $ reverse $ show x :: Int)
isBouncy x = (isIncre x == False) && (isDecre x == False)

bouncers x = length [n|n<-[1..x],isBouncy n]
nonBouncers x = length [n|n<-[1..x],(isBouncy n) == False] 

answer = head [x|x<-[1..],((bouncers x) / (nonBouncers x)) == 0.5]

But what I don't know how to do is define a function isIncre' which tests to see if the digits in a number are greater than or equal to the one on their left. I know it needs to be done recursively but how?

On a side note, I know I can only use / on two floating point numbers but how can I make the output of bouncers to be floating point number instead of an integer?

Edit:

Thanks for the help, but it didn't like the = when I changed isIncre to:

isIncre  x | x <= 99 = False
           | otherwise = isIncre' (mshow x)
                        where
                            isIncre' (x:y:xs) = (x <= y) && (isIncre' (y:xs))
          isIncre' _ = True

Answer 1

If you have a string representation of an integer number, you could write the isIncre function like this (ord converts a character to an integer and string is just a list of chars):

isIncre (x:y:xs) = ord x <= ord y && isIncre (y:xs)
isIncre _ = True

It could be even nicer to write the isIncre function without ord, working on any ordered type, then combine it with "map ord" when you call it instead. The implementation would then be just:

isIncre (x:y:xs) = x <= y && isIncre (y:xs)
isIncre _ = True

That could be called like this, if x is an integer number

isIncre (map ord (show x))

Answer 2

1. The number 0.99 cannot be represented exactly in base 2. Hence you may want to avoid the use of floating point numbers for this assignment. Instead, to see whether exactly 99% of the numbers <= x are bouncers, test whether

   100 * (x - bouncers x) == x
   

   This works because it is (mathematically) the same as (x - bouncers x) == x / 100, which is true if (x - bouncers x) (the number of non-bouncy numbers) is 1% of x. Observe that there is thus no need to define nonBouncers.

2. Also, another way to define bouncers is

   bouncers x = length $ filter isBouncy [1..x]
   

3. However, you should reconsider your design. Currently you are recalculating the number of bouncy numbers up to x, for every x that you try. So a lot of work is being done over and over. What you may instead want to do, is generate a sequence of tuples (x, n), where n is the number of bouncy numbers <= x. Observe that if there are n bouncy numbers <= x, then there are either n or n + 1 bouncy number <= x + 1.

   More specifically, to calculate (x + 1, n'), all you need is (x, n) and the output of isbouncy (x + 1).

Answer 3

I would use really nice functional version of isIncre if you have string representation of intetger.

isIncre :: (Ord a) => [a] -> Bool
isIncre list = and $ zipWith (<=) list (tail list)

If not, just compose it with show.

isIncreNum :: Integer -> Bool
isIncreNum = isIncre . show