Haskell: recursion with array arguments

Question

Disclaimer: I'm new to Haskell and I don't remember a lot about FP from university, so there may be more than one or two errors in my code. This is also my code for Euler Problem 3.

I'm trying to recursively call a function with two arrays as arguments and an array as a result.

The goal:

• assume n is 10 for this question
• create a list of all natural numbers from 1 to n (variable is 'allNumbers' is code)
• create another list of all natural numbers from 1 to n (variable is 'allFactors' is code)
• take the first element in 'allFactors' and multiply the rest of the numbers of 'allFactors' by this number. (this generates an array of numbers)
• remove all these numbers from 'allNumbers'
• continue from 1 to n until 'allFactors' is empty.

Here is my code:

mkList :: Int -> [Int]
mkList n = [1..n-1]

modArray :: Int -> Int -> [Int]
modArray a b =  [ x*b | x <- [1..a], x `mod` b == 0] 

modArrayAll :: [Int] -> [Int] -> [Int]
modArrayAll [] [] = [] 
modArrayAll (x:xs) (y:ys) = (e) 
    where
        m = head( ys)
        n = length( xs)
        e = (modArrayAll xs ys ) \\ modArray n m

(in main)

let allNumbers =  mkList (first + 1)
let allFactors = mkList (first + 1)
let mainList2 =  modArrayAll allNumbers allFactors

This results in a null list. However, if I have:

e = xs \\ modArray n m  --WORKS for one iteration

I get all the odd numbers from 1 to 10.

My Question: Why isn't this working the way I would expect it? I would expect that the recursive stack would hit the empty array condition and just return an empty array which would not be removed from the calling array and it would continue on returning just the prime numbers?

Answer 1

modArray n m creates a list of multiples of m, which you then remove from the "main list" of integers. But modArray n m includes 1*m, so each number is removed because it is a "multiple" of itself. In your test case you get only the odd numbers as a result, while you would want 2 to still be in the resulting list. Additionally 1 is included in your list of factors, which will eliminate all numbers, since they are all multiples of 1.

The terminating case of the recursion is modArrayAll [] [] = [], so there an empty list is returned. Then in the surrounding recursive calls this return value is used here:

(modArrayAll xs ys) \\ modArray n m

This tries to remove further elements (those returned by modArray n m) from the already empty list returned by modArrayAll xs ys. No new elements are added anywhere and the result list stays empty. With your algorithm you want the []-case to return the whole list of numbers, not an empty one. Then the \\ modArray n m in the surrounding recursive function calls can filter out more and more of the non-prime factors.

Answer 2

I copied your goal notes:

-- assume n is 10 for this question
n=10

-- create a list of all natural numbers from 1 to n (variable is 'allNumbers' is code)
allNumbers = [1..n]

-- create another list of all natural numbers from 1 to n (variable is 'allFactors' is code)
allFactors = [2..n] -- i suspect you really wanted this rather than [1..n]

-- take the first element in 'allFactors' and
-- multiply the rest of the numbers of 'allFactors' by this number.
-- (this generates an array of numbers)
-- continue from 1 to n until 'allFactors' is empty
factorProducts = [ x*y | x <- allFactors, y <- allFactors]

--  remove all these numbers from 'allNumbers'
whatYouWanted = allNumbers \\ factorProducts

At the moment you seem to still be thinking in a fairly imperative mindset. Try thinking more about what you want, not how to get it :)