Discussion :

[Trap D]

Bonjour

je me suis amusé à écrire un code pour calculer les nombres parfaits (nombre dont la somme des diviseurs propres est égale à lui-même exemple 6 = 1 +2 + 3)

Voici mon code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import List
 
-- creation de la liste des diviseurs possibles
lst_nb :: Int -> [Int]
lst_nb n = let x = div n 2 in [1..x] 
 
-- Teste si y est un diviseur de x
is_diviseur :: Int -> Int -> Bool
is_diviseur x y = 0 == mod x y
 
-- renvoie
-- y si x divise y
-- 0 sinon
-- pour pouvoir effectuer la somme des diviseurs
-- on doit surement pouvoir faire beaucoup mieux
-- avec une fonction comme filter de Scheme
diviseur :: Int -> Int -> Int
diviseur x y = 
	case (is_diviseur x y) of
		True -> y
		False -> 0
 
-- retourne la somme des diviseurs d'un nombre	
somme_div :: Int -> Int
somme_div x = foldl (+) 0 (map (diviseur x) (lst_nb x))
 
-- teste la "perfection" d'un nombre
is_perfect :: Int -> Bool
is_perfect x = x == somme_div x
 
-- liste des nombres parfaits
-- J'aurais aimé l'écrire sous forme de filter 
list_perfect :: Int -> [Int]
list_perfect 2 = []
list_perfect x = 
	case (is_perfect x) of
       True -> x : list_perfect (x - 1)
       False -> list_perfect (x - 1)

Je ne suis pas très content des fonctions diviseur et list_perfect mais je manque de connaissances Haskell pour pouvoir faire mieux.

Pouvez-vous m'indiquer une piste ?

Merci

[Trap D]

Pas la peine, je viens de trouver
filter existe aussi en Haskell
Désolé

code final

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import List
 
-- creation de la liste des diviseurs possibles
lst_nb :: Int -> [Int]
lst_nb n = let x = div n 2 in [1..x] 
 
-- Teste si y est un diviseur de x
is_diviseur :: Int -> Int -> Bool
is_diviseur x y = 0 == mod x y
 
-- retourne la somme des diviseurs d'un nombre	
somme_div :: Int -> Int
somme_div x = foldl (+) 0 (filter (is_diviseur x) (lst_nb x))
 
-- teste la "perfection" d'un nombre
is_perfect :: Int -> Bool
is_perfect x = x == somme_div x
 
-- liste des nombres parfaits
list_perfect :: Int -> [Int]
list_perfect y = filter (is_perfect) [1..y]

[DigitalGuru]

Il y a plus court (pas forcément mieux ) :
[ q | q <- [1..], q == sum [ p | p <- [1..q-1], q `mod` p == 0]] !! N

Cette ligne te donne le Nème nombre parfait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Prelude> let np = [ q | q <- [1..], q == sum [ p | p <- [1..q-1], q `mod` p == 0]]
Prelude> np !! 0
6
Prelude> np !! 1
28
Prelude> np !! 2
496
Prelude> np !! 3
8128

++

[Trap D]

Merci de ton code.
Comme je débute en Haskell, j'ai encore besoin d'écrire du code "qui me parle".
Mais je commence à comprendre des lignes qui me paraissaient totalement absconses au début !

[DigitalGuru]

Je débute aussi l'haskell et c'est vrai qu'au début ça fait un peut bizzard !
Par contre, si je peux te donner un conseil, ça serait d'oublier tout ce que tu as appris en programmation impérative et mettre a profit tout ce que le lambda calcul t'offre.
En effet, le gros problème de l'haskell (à mon sens), c'est qu'il faut des bases en lambda calcul pour le pratiquer correctement.

Je pense notamment à l'évaluation paresseuse, une usage agressif de la récursivité, et les lambda fonctions. Je te conseil de te renseigner là dessus. Les conférences du collège de France sont absolument génial à ce sujet !

Pour finir, n'oublie jamais que l'Haskell est un des langages les moins "verbeux" et qu'un programme long signifie souvent un programme mal conçu !

Bonne continuation !

[Trap D]

Par contre, si je peux te donner un conseil, ça serait d'oublier tout ce que tu as appris en programmation impérative et mettre a profit tout ce que le lambda calcul t'offre.

Pour ce qui est du grand saut conceptuel, je l'ai fait lorsque je suis passé du C au Prolog !
Mais c'est vrai que j'ai fait pas mal de Scheme à un moment et je m'aperçois maintenant que je n'avais pas pigé le paradigme fonctionnel (si tant est que je l'ai vraiment bien compris)

Pour ce qui est du lambda calcul, j'en fait un peu il y a très longtemps, c'était extrêmement théorique et j'ai un peu tout oublié !

[gg373]

Je ne sais pas trop si un programme hyper-concis est pour autant mieux.
L'exemple des nombres parfaits est intéressant, car le code donné dans les messages précédents relève assez de la force brute.
Et le moins qu'on puisse dire est qu'il est vraiment très lent.
Je me suis amusé à passer par la recherche des facteurs premiers en les composants pour retrouver les diviseurs.
Cette approche est bien plus rapide (8 fois pour 10 000 nombres et je ne suis pas sûr qu'elle soit quadratique contrairement à ton code). C'est moins déclaratif (je me méfie des solutions compactes souvent peu efficaces) et surtout cela illustre une des grandes forces d'Haskell : la composition. Ici, on passe par les fonctions sur les listes pour regrouper les facteurs par puissance croissante puis les monades opèrent la composition finale qu'il n'y a plus qu'à sommer...
C'est pas mal de code, mais si vous pouvez faire mieux et plus vite... (quoique je me suis demandé si dans le code précédent on 'chassait' jusqu'à la racine carrée cela n'accélererait pas grandement aussi... à tester)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
-- creation de la liste des diviseurs possibles
lst_nb :: Int -> [Int]
lst_nb n = let x = div n 2 in [1..x] 
 
-- Teste si y est un diviseur de x
is_diviseur :: Int -> Int -> Bool
is_diviseur x y = 0 == mod x y
 
-- retourne la somme des diviseurs d'un nombre	
somme_div :: Int -> Int
-- somme_div x = foldl (+) 0 (filter (is_diviseur x) (lst_nb x))
somme_div x = div (sum $ divisors x False) 2
 
-- teste la "perfection" d'un nombre
is_perfect :: Int -> Bool
is_perfect x = x == somme_div x
 
-- liste des nombres parfaits
list_perfect :: Int -> [Int]
list_perfect y = filter (is_perfect) [1..y]
 
-- Integral square root of an Integral
-- long division method 
isqrtLD :: Integral i => i -> i
isqrtLD n =
 let lDiv n b 
      | n<0 = b - 1
      | otherwise =
         let n' = n - b
             b' = b + 1
             n'' = n' - b'
         in lDiv n'' b'
 in lDiv n 0
 
-- list of prime numbers
primes :: [Int]
primes = sieve (2:[3,5..])
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
 
-- prime factors of an integer
-- e.g. 1,008 -> [2,2,2,2,3,3,7]
primeFactors :: Int -> [Int]
primeFactors nb =
 factors primes nb
  where
   sqr = isqrtLD nb
   factors qs@(p:ps) n
    | p > sqr = if n == 1 then [] else [n] 
    | m == 0 = p : factors qs d
    | otherwise = factors ps n
    where (d,m) = n `divMod` p
 
-- take nb and gets a list of its factors listed in successive powers
-- e.g. 504
--      primeFactors -> [2, 2, 2, 3, 3, 7]
--      group -> [[2, 2, 2], [3, 3], [7]]
--      result -> [[1,2,4,8],[1,3,9],[1,7]]
powersOfPrimeFactors :: Int -> [[Int]]
powersOfPrimeFactors nb =
  let pfct = group $ primeFactors nb
      mapAcc accSameFactor =
        snd $ mapAccumL (\acc x-> let m = acc*x in (m, m)) 1 accSameFactor
  in map (1:) $ map mapAcc pfct
 
-- gives the list of divisors (unsorted or sorted depending on bool) of
-- an integer
-- e.g. 496 False -> [1,31,2,62,4,124,8,248,16,496]   
--      8128 True -> [1,2,4,8,16,32,64,127,254,508,1016,2032,4064,8128]   
divisors :: Int -> Bool -> [Int]  
divisors n bSort =
 let p = powersOfPrimeFactors n
     multList fct1 fct2 =  -- fct1 >>= \x -> map (x*) fct2
       do
        x <- fct1
        y <- fct2
        return (x*y)
     r = foldl multList [1] p
 in if bSort then (sort r) else r

[Trap D]

Bonjour

Merci de ta réponse. Malheureusement, je n'ai pratiquement plus fait d'Haskell depuis que j'ai posté ici.
J'ai essayé de compiler avec WinGHCI et j'ai obtenu ces erreurs :

Prelude> :cd C:\a-travail\developpements\Haskell
Prelude> :load "perfect-1.hs"
[1 of 1] Compiling Main ( perfect-1.hs, interpreted )

perfect-1.hs:61:14: Not in scope: `group'

perfect-1.hs:63:15: Not in scope: `mapAccumL'

perfect-1.hs:79:20:
Not in scope: `sort'
Perhaps you meant `sqrt' (imported from Prelude)
Failed, modules loaded: none.
Prelude>

[gg373]

Oups, désolé, j'ai oublié les imports :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
import List
import Monad