Haskell : récursion avec des arguments de type tableau

Question

Avertissement : Je suis nouveau en Haskell et je ne me souviens pas de beaucoup de choses sur la FP à l'université, donc il peut y avoir plus d'une ou deux erreurs dans mon code. C'est aussi mon code pour le problème d'Euler 3.

J'essaie d'appeler récursivement une fonction avec deux tableaux comme arguments et un tableau comme résultat.

Le but :

• supposez que n est égal à 10 pour cette question
• créer une liste de tous les nombres naturels de 1 à n (la variable 'allNumbers' est le code)
• créer une autre liste de tous les nombres naturels de 1 à n (la variable 'allFactors' est le code)
• prendre le premier élément de 'allFactors' et multiplier le reste des nombres de 'allFactors' par ce nombre. (cela génère un tableau de nombres)
• supprimez tous ces numéros de 'allNumbers'.
• continuer de 1 à n jusqu'à ce que 'allFactors' soit vide.

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

(en principal)

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

Le résultat est une liste nulle. Cependant, si j'ai :

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

J'obtiens tous les nombres impairs de 1 à 10.

Ma question : Pourquoi cela ne fonctionne-t-il pas comme je l'attends ? Je m'attendrais à ce que la pile récursive rencontre la condition de tableau vide et renvoie simplement un tableau vide qui ne serait pas retiré du tableau appelant et qu'elle continue à renvoyer uniquement les nombres premiers ?

Answer 1

J'ai copié tes notes sur les objectifs :

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

Pour l'instant, vous semblez encore penser dans un état d'esprit assez impératif. Essayez de penser davantage à ce que vous voulez, et non à la manière de l'obtenir :)

Answer 2

modArray n m crée une liste de multiples de m que vous retirez ensuite de la "liste principale" des entiers. Mais modArray n m comprend 1*m Ainsi, chaque nombre est supprimé parce qu'il est un "multiple" de lui-même. Dans votre cas de test, vous n'obtenez que les nombres impairs comme résultat, alors que vous voudriez que 2 soit toujours dans la liste résultante. De plus, 1 est inclus dans votre liste de facteurs, ce qui éliminera tous les nombres, puisqu'ils sont tous des multiples de 1.

Le cas final de la récursion est modArrayAll [] [] = [] de sorte qu'une liste vide est retournée. Ensuite, dans les appels récursifs environnants, cette valeur de retour est utilisée ici :

(modArrayAll xs ys) \\ modArray n m

On essaie de supprimer d'autres éléments (ceux renvoyés par modArray n m ) de la liste déjà vide renvoyée par modArrayAll xs ys . Aucun nouvel élément n'est ajouté nulle part et la liste de résultats reste vide. Avec votre algorithme, vous voulez que le [] -case pour retourner la liste entière de nombres, pas une liste vide. Ensuite, le \\ modArray n m dans les appels de fonction récursifs environnants peut filtrer de plus en plus de facteurs non primaires.