# Optimized list filtering on implementation of Project Euler 23

I'm new to Haskell, the part of my code I'm concerned with is the isSumAbundant function. Surely there must be a better way, in an imperative language I might use a for loop and break out of the loop if i got greater than n, but it seems like having to filter the list for every single function call is not optimal.

The problem is Problem 23 from project-euler.net.

projectEuler23 =
let a = abundantNums 28124 in
sum [x | x <- [1..28124], not $isSumAbundant x a] isSumAbundant n a = any (\x -> (n - x) elem a) (takeWhile (<n) a) abundantNums n = [x | x <- [1..n], (>x)$ sum $properDivisors x] properDivisors n = let limit = (floor.sqrt.fromIntegral) n in [limit | limit^2 == n] ++ ((1:)$ concat [ [x, div n x] | x <- [2..limit - 1], rem n x == 0])

• elem is linear, here's some cryptic pointlesser linear self-intersection. isSumAbundant n = any (not . null . tail) . group . sort . ap (++) (map (n-)) . takeWhile (<n) Dec 23 '17 at 12:50

Add type signatures. Without type signatures, your integral types will default to Integer. So let us add type signatures:

projectEuler23 :: Int
projectEuler23 =
let a = abundantNums 28124 in
sum [x | x <- [1..28124], not $isSumAbundant x a] isSumAbundant :: Int -> [Int] -> Bool isSumAbundant n a = any (\x -> (n - x) elem a) (takeWhile (<n) a) abundantNums :: Int -> [Int] abundantNums n = [x | x <- [1..n], (>x)$ sum $properDivisors x] properDivisors :: Int -> [Int] properDivisors n = let limit = (floor.sqrt.fromIntegral) n in [limit | limit^2 == n] ++ ((1:)$ concat [ [x, div n x] | x <- [2..limit - 1], rem n x == 0])


Note that a type signature on projectEuler23 would have been enough. Operations on Int are usually faster than Integer.

In isSumAbundant you can stop at ndiv2, e.g.

isSumAbundant n a = any (\x -> (n - x) elem a) $takeWhile (<= (n div 2)) a  Similar in abundantNums, you can use scanl1: abundantNums n = [x | x <- [1..n], any (x <)$ scanr1 (+) \$ properDivisors x]


This models your "break" from imperative languages.