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

Question

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

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

Цель:

• предположим, что n = 10 для этого вопроса
• создать список всех натуральных чисел от 1 до n (переменная '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. Новые элементы нигде не добавляются, а список результатов остается пустым. С вашим алгоритмом вы хотите, чтобы [] -кател возвращал весь список чисел, а не пустой. Тогда \\ modArray n m в окружающих рекурсивных вызовах функций может отфильтровывать все больше и больше не простых факторов.