haskell: factors of a natural number

Question

I'm trying to write a function in Haskell that calculates all factors of a given number except itself.

The result should look something like this:

factorlist 15 => [1,3,5]

I'm new to Haskell and the whole recursion subject, which I'm pretty sure I'm suppoused to apply in this example but I don't know where or how.

My idea was to compare the given number with the first element of a list from 1 to n div2 with the mod function but somehow recursively and if the result is 0 then I add the number on a new list. (I hope this make sense)

I would appreciate any help on this matter

Here is my code until now: (it doesn't work.. but somehow to illustrate my idea)

 factorList :: Int -> [Int]
 factorList n  |n `mod` head [1..n`div`2] == 0 = x:[]

Answer 1

There are several ways to handle this. But first of all, lets write a small little helper:

isFactorOf :: Integral a => a -> a -> Bool
isFactorOf x n = n `mod` x == 0

That way we can write 12 `isFactorOf` 24 and get either True or False. For the recursive part, lets assume that we use a function with two arguments: one being the number we want to factorize, the second the factor, which we're currently testing. We're only testing factors lesser or equal to n `div` 2, and this leads to:

createList n f | f <= n `div` 2 = if f `isFactorOf` n
                                     then f : next
                                     else next
               | otherwise      = []
    where next = createList n (f + 1)

So if the second parameter is a factor of n, we add it onto the list and proceed, otherwise we just proceed. We do this only as long as f <= n `div` 2. Now in order to create factorList, we can simply use createList with a sufficient second parameter:

factorList n = createList n 1

The recursion is hidden in createList. As such, createList is a worker, and you could hide it in a where inside of factorList.

Note that one could easily define factorList with filter or list comprehensions:

factorList'  n = filter (`isFactorOf` n) [1 .. n `div` 2]
factorList'' n = [ x | x <- [1 .. n`div` 2], x `isFactorOf` n]

But in this case you wouldn't have written the recursion yourself.

Further exercises:

• Try to implement the filter function yourself.
• Create another function, which returns only prime factors. You can either use your previous result and write a prime filter, or write a recursive function which generates them directly (latter is faster).

Answer 2

@Zeta's answer is interesting. But if you're new to Haskell like I am, you may want a "simple" answer to start with. (Just to get the basic recursion pattern...and to understand the indenting, and things like that.)

I'm not going to divide anything by 2 and I will include the number itself. So factorlist 15 => [1,3,5,15] in my example:

factorList :: Int -> [Int]

factorList value = factorsGreaterOrEqual 1
  where
    factorsGreaterOrEqual test
      | (test == value) = [value]
      | (value `mod` test == 0) = test : restOfFactors
      | otherwise = restOfFactors
      where restOfFactors = factorsGreaterOrEqual (test + 1)

The first line is the type signature, which you already knew about. The type signature doesn't have to live right next to the list of pattern definitions for a function, (though the patterns themselves need to be all together on sequential lines).

Then factorList is defined in terms of a helper function. This helper function is defined in a where clause...that means it is local and has access to the value parameter. Were we to define factorsGreaterOrEqual globally, then it would need two parameters as value would not be in scope, e.g.

factorsGreaterOrEqual 4 15 => [5,15]

You might argue that factorsGreaterOrEqual is a useful function in its own right. Maybe it is, maybe it isn't. But in this case we're going to say it isn't of general use besides to help us define factorList...so using the where clause and picking up value implicitly is cleaner.

The indentation rules of Haskell are (to my tastes) weird, but here they are summarized. I'm indenting with two spaces here because it grows too far right if you use 4.

Having a list of boolean tests with that pipe character in front are called "guards" in Haskell. I simply establish the terminal condition as being when the test hits the value; so factorsGreaterOrEqual N = [N] if we were doing a call to factorList N. Then we decide whether to concatenate the test number into the list by whether dividing the value by it has no remainder. (otherwise is a Haskell keyword, kind of like default in C-like switch statements for the fall-through case)

Showing another level of nesting and another implicit parameter demonstration, I added a where clause to locally define a function called restOfFactors. There is no need to pass test as a parameter to restOfFactors because it lives "in the scope" of factorsGreaterOrEqual...and as that lives in the scope of factorList then value is available as well.