Haskell: рекурсия с аргументами массива

Question

Отказ от ответственности: я новичок в Haskell, и я не очень много помню о FP из университета, поэтому в моем коде может быть более одной или двух ошибок. Это также мой код для проблемы Эйлера 3.

Я пытаюсь рекурсивно вызывать функцию с двумя массивами в качестве аргументов и массивом в результате.

Цель:

• предположить п 10 на этот вопрос
• создать список всех натуральных чисел от 1 до п (переменная «allNumbers» является кодом)
• создать еще один список все натуральные числа от 1 до n (переменная является «allFactors» - это код)
• возьмите первый элемент в «allFactors» и умножьте оставшиеся числа «allFactors» на это число. (это генерирует массив чисел)
• удалите все эти цифры из «allNumbers»
• Продолжите с 1 по n, пока 'allFactors' не будет пустым.

Вот мой код:

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 

(в основном)

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

Это приводит к нулевому списка. Тем не менее, если у меня есть:

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

Я получаю все нечетные числа от 1 до 10.

Мой вопрос: почему это не работает так, как я ожидал бы это? Я бы ожидал, что рекурсивный стек попадет в пустое состояние массива и просто вернет пустой массив, который не будет удален из вызывающего массива, и он будет продолжать возвращать только простые числа?

Answer 1

Я скопировал свои голевые ноты:

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

На данный момент, кажется, вы все еще думать в довольно повелительном мышления. Подумайте больше о том, чего вы хотите, а не о том, как его получить :)

Answer 2

modArray n m создает список кратных m, который затем удаляется из «основного списка» целых чисел. Но modArray n m включает в себя 1*m, поэтому каждый номер удален, потому что он является «кратным». В вашем тестовом примере вы получаете только нечетные числа в результате, в то время как вы хотите, чтобы 2 все еще находились в результирующем списке. Кроме того, 1 входит в ваш список факторов, который исключает все числа, так как они все кратные 1.

Завершающий регистр рекурсии - modArrayAll [] [] = [], поэтому возвращается пустой список. Тогда в окружающих рекурсивных вызовах это возвращаемое значение используется здесь:

(modArrayAll xs ys) \\ modArray n m 

Это пытается удалить дополнительные элементы (возвращаемые modArray n m) из уже пустого списка, возвращаемого modArrayAll xs ys. Никакие новые элементы не добавляются нигде, и список результатов остается пустым. С вашим алгоритмом вы хотите, чтобы [] -case возвращал весь список чисел, а не пустой. Тогда \\ modArray n m в окружающих рекурсивных вызовах функций может отфильтровывать все больше и больше непеременных факторов.