Trouble using map in Haskell

Question

Hi, I am attempting to make an algorithm to solve question 255 at Project Euler

I came up with this solution:

roundedSq n | (roundedSq n) == roundedSq (n-1) = n : roundedSq (n+1)
      | rem n 2 == 1  = n : floor ( ((2*10^((d-1) `div` 2)) + ceiling (n `div` (2*10^((d-1) `div` 2)) )) `div` 2 )
      | otherwise     = n : floor ( ((7*10^((d-2) `div` 2)) + ceiling (n `div` (7*10^((d-2) `div` 2)) )) `div` 2 )
     where
       d = length (map (digitToInt) (show (n)))

average a = (sum a) `div` (length a)
answer = average [map roundedSq [10E13..10E14]]

main = do
  print answer

But every time I try to load, it comes with an error for the answer calculating function. What have I done wrong and will this even give me a correct solution or will it just get stick in a loop??

Answer 1

You'll get stuck in an infinite loop due to

roundedSq n | (roundedSq n) ...

Edit: Sometimes it seems like I have a hole in my head. Of course average is ok.

However, since you don't decrement or increment all recursive calls to roundedSq you will never hit the "bottom" and terminate.

Answer 2

If you want average to return a Fractional number you'll need to use this definition:

average a = (sum a) / (fromIntegral $ length a)

(/) is the Fractional division operator whereas div is the Integral division operator. Note you also need to use fromIntegral because length returns an Int which is not a part of the Fractional type class.

Answer 3

There is a problem with your average.

average a = (sum a) `div` (length a)

sum uses the entire list. length also uses the entire list. This means that the whole list will be generated and held in memory while one of these functions traverses it, and will not be garbage collected until the other function traverses it.

You pass average a very large list, so you will run out of memory.

Solution: rewrite average as a function that only traverses the list once, so that the list can be garbage collected as it is generated.

Example (untested):

average a = sum `div` length
  where (sum, length) = foldl' f (0, 0) a
        f (sum, length) i = (sum + i, length + 1)

Note that this uses foldl', from Data.List, not foldl. foldl has its own space issues (which someone more knowledgeable than me may wish to comment on).

And as Tobias Wärre has pointed out,

roundedSq n | (roundedSq n) == roundedSq (n-1) = n : roundedSq (n+1)

will result in an endless loop:

1. we want to evaluate roundedSq n
2. if (roundedSq n) == roundedSq (n-1) is true, we will return n : roundedSq (n+1) as the answer
3. we need to evaluate (roundedSq n) == roundedSq (n-1)
4. we need to evaluate roundedSq n
5. goto 1.

Answer 4

answer = average [map roundedSq [10E13..10E14]]

You've put the mapped list into a list of one element here. I think perhaps you mean:

answer = average (map roundedSq [10E13..10E14])