CODEWITHSUNDEEP
haskellfunctional-programming
Jonno_FTW
Jonno_FTW

Reputation: 8809

Trouble using map in Haskell

I am attempting to make an algorithm to solve Project Euler Problem 255

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??

Upvotes: 1

Views: 629

Answers (4)

dave4420
dave4420

Reputation: 47072

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.

Upvotes: 2

Tobias Wärre
Tobias Wärre

Reputation: 803

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.

Upvotes: 0

Nefrubyr
Nefrubyr

Reputation: 7094

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])

Upvotes: 5

davetapley
davetapley

Reputation: 17990

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.

Upvotes: 1

Related Questions