Trouble using map in Haskell

Question

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

Nefrubyr · Accepted Answer · 2009-09-17 11:17:00Z

5

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

answered Sep 17, 2009 at 11:17

Nefrubyr

7,1622 gold badges31 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

dave4420 · Accepted Answer · 2009-09-20 16:19:24Z

2

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:

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

edited Sep 20, 2009 at 16:19

answered Sep 17, 2009 at 11:11

dave4420

47.2k6 gold badges121 silver badges153 bronze badges

2 Comments

Jonno_FTW Over a year ago

I thought that: roundedSq n | (roundedSq n) == roundedSq (n-1) = n : roundedSq (n+1) would check to see if the current iteration is the same as the one before it, it will go to the next one with = n : roundedSq (n+1)

dave4420 Over a year ago

See my edit. You need a different way of detecting when you can stop iterating.

davetapley · Accepted Answer · 2009-09-17 10:59:07Z

1

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.

answered Sep 17, 2009 at 10:59

davetapley

18.1k15 gold badges65 silver badges93 bronze badges

1 Comment

Nefrubyr Over a year ago

You can also use genericLength from Data.List instead of combining length and fromIntegral.

Tobias Wärre · Accepted Answer · 2009-09-17 13:56:07Z

0

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.

edited Sep 17, 2009 at 13:56

answered Sep 17, 2009 at 10:38

Tobias Wärre

8037 silver badges11 bronze badges

3 Comments

Jonno_FTW Over a year ago

I tried loading only the average function and I got a correct answer for the when I typed: average [5..10] i got the answer 7. So the question arises as to how to make it list the average to 10 decimal places

davetapley Over a year ago

I don't see what's wrong with the usage of average, it's just a function of type [Int] -> Int ?

Jonno_FTW Over a year ago

I fixed it with: average :: [Double] -> Double average a = (sum a) / (fromIntegral $(length a)) :: Double It seemed that using div was the source of the error

Collectives™ on Stack Overflow

Trouble using map in Haskell

4 Answers 4

Comments

2 Comments

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related