Simple prime factorization program in Haskell

Question

I'm finally learning Haskell this summer and I have a few questions about conventions. I made a simple prime factorization program which is surprisingly fast, much faster than the ones I made in C++ (though to be fair I made those non-recursively).

It consists of three functions: one checks if a num is prime, one finds the prime factors, and one checks if a list's length is less than a number. The last one is because I was worried that take and length would be too slow and the Haskell wiki agreed. I just copied and pasted their at least function and reversed it.

import Data.List
import Data.Ord

isPrime :: Integer -> Bool
primes :: Integer ->[Integer]

isLengthLessThan :: Int -> [a] -> Bool
isLengthLessThan 0 _      = False
isLengthLessThan _ []     = True
isLengthLessThan n (_:ys) = isLengthLessThan (n-1) ys

isPrime x 
    | x == 2       = True
    | mod x 2 == 0 = False
    | otherwise    = isLengthLessThan 2 [y | y <- [1,3.. roof], mod x y == 0]
    where roof = 1 + truncate (sqrt $fromIntegral x)

primes x
    | isPrime x = [x]
    | otherwise = factor : primes(div x factor)
    where factor = head $filter checkdiv [2..] 
          checkdiv n = x `mod` n == 0

Finally the questions:

• Should isLengthLessThan be in a where under isPrime?

• Is isLengthLessThan's name too verbose?

• What should I name my "primes" function?

• Are the function type specifications called that or declarations?

• Should I put the type specifications right before the function or should I put it at the start?

• Do specifications help speed or do they only help us by giving us better errors?

• Do parenthesis make compilation faster or do they only muddle code up?

Answer 1

First, a few stylistic points:

• It's more common to write the div and mod functions in infix, as x `mod` y == 0, etc.
• A parenthesized argument to a function is never written f(x). It's always with a separating space like f (x), so you want primes (x `div` factor).
• The infix operator $ is pretty much always both preceded and followed by a space.
• Similarly, in the [x..y] syntax, the .. is normally not surrounded by any space, though when it is, it is both preceded and followed by space, so either [1,3..roof] or [1, 3 .. roof] would be more common than [1,3.. roof].

and some advice on functions:

• even x is preferred to x `mod` 2 == 0
• For positive values, 1 + truncate x can be replaced with ceiling x. Technically, though, you don't need to check any numbers greater than the square root, so floor (sqrt $ fromIntegral x) works in your case.

• Also for positive values, the function pair quot/rem is equivalent to div/mod and the former can compile to faster code on x86_64 (e.g., quot on Ints can be a single machine instruction), so many Haskellers will get in the habit of using them whenever the substitution works. (Alternatively, this is a ridiculous micro-optimization here, so sticking with the div/mod pair is fine if it looks more natural.)

  However, it might be even better to introduce a predicate:

  divides :: (Integral a) => a -> a -> Bool
  divides d n = n `rem` d == 0
  

  so you can write y `divides` x in your list comprehension, and use the section (`divides` x) in your filter.

Finally, it's usual practice to provide type signatures that are more general than the ones you've provided. Certainly, generalizing primes and isPrime to all integral types would be usual:

isPrime :: (Integral a) => a -> Bool
primes :: (Integral a) => a -> [a]

On the other hand, isLengthLessThan is probably fine the way it as, as it's usual to assume list lengths will fit in a 64-bit Int, for obvious reasons.

Now, with respect to your questions:

Should isLengthLessThan be in a where under isPrime?

That's up to you. A utility function that's used in only one function is often included in a where clause, though if the function seems "independently useful", it's sometimes kept at top-level. In this small module, keeping it at top level seems reasonable. In a bigger module, you might stick it in a where clause to reduce clutter.

Rearranging the functions can also help. If you put primes at the top and then put utility functions after the functions that use them (e.g., primes, then isPrime, then isLengthLessThan), it can make it easier to follow the program's organization.

Is isLengthLessThan's name too verbose?

I'd say so. Maybe shorterThan? Note that the character count is probably less of an issue than the word count -- shorterThan is simple to read and understand; isLengthLessThan belongs in a Java program as a method in the ListLengthCheckerFactory class. But also, see below for how to eliminate this function entirely.

What should I name my "primes" function?

I'd say factors -- I mean, it's obviously going to be the prime factorization, because what other factors function would make sense?

Are the function type specifications called that or declarations?

According to the Haskell 2010 Report, they're called "type signatures", and the corresponding function definitions f x = ... are called "bindings". Both type signatures and bindings are examples of "declarations", so isPrime :: Int -> Bool is a declaration, but so is isPrime x = .... However, in informal speech, if you asked "should this binding have a type declaration?", everyone would know what you meant.

Should I put the type specifications right before the function or should I put it at the start?

Almost universally in Haskell code, type signatures are placed immediately preceding the corresponding binding rather than collected together at the beginning of the module. While collecting them together probably seems like a nice way of documenting the "interface" at the top of the module, it has the drawback that someone stumbling across the definition may assume there's no type signature (as signatures are often optional) and so never see it, and what's more the standard Haddock documentation tool is set up to have the signature and definition of each binding in the same place.

Do specifications help speed or do they only help us by giving us better errors?

If the type signature matches what would be inferred by GHC if it was missing (which is often the most general possible type), then there is no effect on generated code. Moreover, GHC is designed to generate efficient code even when highly generalized signatures are used, by specializing and inlining functions aggressively. You could most likely drop your signatures, or use the signatures I suggested above with no effect on performance.

So, yes, type signatures are primarily useful for generating better error messages, occasionally for catching certain design errors, and -- when the code is finished -- for documenting the interface.

Do parenthesis make compilation faster or do they only muddle code up?

Any effect of parentheses on compilation speed will be miniscule, and it's standard Haskell style to omit them except where they are necessary.

Anyway, incorporating the advice I gave above, my version of your program currently looks like the following. Note that I turned on -Wall, which reminded me that your program doesn't actually need the modules it imports, and let me know that there was a type defaulting going on in the sqrt call that I thought should be made explicit. I also ran hlint on it, which didn't have any hints for me.

{-# OPTIONS_GHC -Wall #-}

module MorePrimes where

factors :: (Integral a) => a -> [a]
factors x
    | isPrime x = [x]
    | otherwise = factor : factors (x `div` factor)
    where factor = head $ filter (`divides` x) [2..]

isPrime :: (Integral a) => a -> Bool
isPrime x
    | x == 2    = True
    | even x    = False
    | otherwise = shorterThan 2 [y | y <- [1,3..roof], y `divides` x]
    where roof = floor $ sqrt (fromIntegral x :: Double)

shorterThan :: Int -> [a] -> Bool
shorterThan 0 _      = False
shorterThan _ []     = True
shorterThan n (_:ys) = shorterThan (n-1) ys

divides :: (Integral a) => a -> a -> Bool
divides d n = n `rem` d == 0

Finally, some additional optimizations.

Your test in the third case of isPrime can be simplified. Since 1 always divides x, you can replace the test with:

shorterThan 1 [y | y <- [3,5..roof], y `divides` x]

which is equivalent to:

null [y | y <- [3,5..roof], y `divides` x]

which would more usually be written:

not $ any (`divides` x) [1,3..roof]

allowing you to drop the definition of shorterThan entirely and use:

isPrime :: (Integral a) => a -> Bool
isPrime x
    | x == 2    = True
    | even x    = False
    | otherwise = not $ any (`divides` x) [3,5..roof]
    where roof = floor $ sqrt (fromIntegral x :: Double)

The other problem is that factors is doing extra work here -- it's using isPrime to check if x is prime using an algorithm that handles even numbers specially for efficiency, but then it turns around and does trial division by all numbers [2..] for composites. Instead, you could replace isPrime with a function to find the first prime factor of x, like so:

firstPrime :: (Integral a) => a -> a
firstPrime x
    | even x    = 2
    | otherwise = head [y | y <- [3,5..roof]++[x], y `divides` x]
    where roof = floor $ sqrt (fromIntegral x :: Double)

This finds the first prime factor below roof, but throws in x itself as a last resort. (There's an unnecessary check here that x divides itself, so we could improve this code to avoid that, but it might not be worth the trouble.)

Then, factors can grab this first prime factor, and see if it was x itself (in which case x is prime and we're done) or else look for more factors. The complete code for this version looks like:

{-# OPTIONS_GHC -Wall #-}

module MorePrimes where

factors :: (Integral a) => a -> [a]
factors x = case firstPrime x of
    factor | factor == x -> [x]
           | otherwise   -> factor : factors (x `div` factor)

firstPrime :: (Integral a) => a -> a
firstPrime x
    | even x    = 2
    | otherwise = head [y | y <- [3,5..roof]++[x], y `divides` x]
    where roof = floor $ sqrt (fromIntegral x :: Double)

divides :: (Integral a) => a -> a -> Bool
divides d n = n `rem` d == 0

Obviously, further optimization is possible, as illustrated by @Gurkenglas's answer.

Answer 2

• Yes, but you don't need it.
• It is good that your intuition tells you to give this function this long a name: It tells you to get rid of it. While you can't get rid of it, keep the name long as a symbol of shame.
• factors.
• Annotations.
• Right before. If all goes well, your definition will have form foo = bar $ _ where bar is some library function that tells the experienced reader what sort of definition he's looking at, much like the type does.
• They do not directly help speed, but in my estimation can make it easy to make code simple/short, and therefore easy to improve in any direction.
• Parentheses do not influence compilation noticably. Optimize for readability.

isPrime = null [y | y <- 2:[3,5..floor $ sqrt $ fromIntegral x], mod x y == 0]

Or rather:

primes 1 = []
primes x = factor : primes (div x factor) where
  factor = head $ [y | y <- 2:[3,5..floor $ sqrt $ fromIntegral x], mod x y == 0] ++ [x]