Pretty Haskell?

Un débutant en programmation fonctionnel pur

a marqué ce sujet comme résolu.

Bonjour,

Ce sujet est pour obtenir un retour sur mon code, voir si vous avez des conseils d’amélioration / des critiques. J’apprécie la philosophie fonctionnel mais je ne m’y suis jamais vraiment mis à fond donc je m’essaie à résoudre des problèmes avec Haskell.

Voici une traduction du problème : étant donné une liste d’entiers, retourner une nouvelle liste tel que chaque élément à l’indice i de la nouvelle liste soit le produit de tous les nombres de la liste originale sauf celui à l’indice i. Autrement dit, solve([1 2 3 4 5]) == [120 60 40 30 24]. Sous forme d’algorithme impératif, si ma description n’était pas très clair :

def solve(ls):
    res = []
    for i, _ in enumerate(ls):
        tmp = 1
        for j, m in enumerate(ls):
            if i != j:
                tmp *= m
        res.append(tmp)
    return res

En commençant, je me dis que la solution est probablement récursive. Voici donc ma première version qui est pas mal tiré par les cheveux :

solve :: [Int] -> Maybe Int -> [Int]
solve [] _ = []
solve (x:xs) (Just product) = [div product x] ++ (solve xs (Just product))
solve ls@(x:xs) Nothing = [div product x] ++ (solve xs (Just product))
    where product = foldr (*) 1 ls

En fait, map est là pour ça :

solve :: [Int] -> [Int]
solve ls = map (div product) ls
    where product = foldr (*) 1 ls

Edit, currying <3 :

solve :: [Int] -> [Int]
solve = map (div product)
    where product = foldr (*) 1 ls

Je suis plutôt satisfait de cette version, j’ai du mal à voir comment on peut faire mieux. On commence d’ailleurs à découvrir la puissance du langage avec les syntaxes (div product) et (*) par exemple. Cependant, le problème vient avec une contrainte optionnelle : que faire si on ne peut pas utiliser la division ?

solve :: [Int] -> [Int]
solve [] = []
solve ls = map (\(i, _) -> foldr (\(j, n) acc -> if i == j then acc else acc*n) 1 zipped) zipped
    where zipped = zip [0..] ls

J’utilise quelques petits trucs apportés par Haskell genre l’évaluation fainéante ([0..]) mais je trouve que la solution n’est toujours pas idéale. Pour chaque valeur, on fold toutes les valeurs sauf celle à l’indice actuel ; c’est un peu une traduction mot à mot de l’énoncé. La solution n’est pas très lisible je trouve. Vous avez des conseils ?

J’ai eu du mal à me lancer mais maintenant que j’arrive relativement à écrire du Haskell, j’ai juste envie de continuer à l’explorer et à me casser la tête pour trouver des solutions élégantes. J’espère que ce sujet pourra continuer à vivre pour parler Haskell, et beau code.

+0 -0

Je continue d’apprendre, je suis donc arrivé à cette solution :

solve :: [Int] -> [Int]
solve xs = map (\(i, _) -> product $ map (snd) $ filter ((/=) i . fst) zipped) zipped
    where zipped = zip [0..] xs

Pour un indice i, on filtre pour récupérer toutes les valeurs associés aux autres indices et on fait le produit. La composition de fonctions est plus dans l’esprit fonctionnel je trouve mais le code n’est pas forcément lisible facilement.

J’ai manipulé la forme ((/=) i . fst) au lieu d’une lambda (\(j, _) -> i /= j) juste pour apprendre le langage, je ne vois pas ce qu’elle apporte. Ceux qui lisent du Haskell fréquemment, vous comprenez rapidement cette forme ?

+0 -0

Personnellement je serais resté sur une solution récursive, qui gagne à mon avis en lisibilité, avec une implémentation un peu différente cela dit.

Je pense qu’utiliser map et ses amis, c’est bien, mais qu’il ne faut pas essayer de l’utiliser pour faire autre chose qu’appliquer une fonction sur une liste qui m’est affectée que par l’élément sur lequel elle est appliquée. 

solve' _ [] = []
solve' xl y:ys = (product $ xl ++ ys):(solve' (y:xl) ys)
 where product = foldr (*) 1

solve = solve' []

(Depuis le téléphone, je ne garantis pas que le code compile ;))

Edit: globalement j’ai l’impression que tu veux faire « trop bien », ce qui, pour moi en tout cas, rend la lecture un peu plus difficile. Pour ta dernière question, je ne trouve pas un ((/=) i . fst) aussi immédiat qu’une « vraie comparaison », mais bon, pourquoi pas au fond.

+1 -0

J’utilise en général al@(a:as), avec l pour « liste », rien pour l’élément actuel et s pour « suite » (peut-être que ça correspond à un joli truc en anglais, mais je ne sais pas quoi comme ça).

(Sinon, j’utilise les lettres plus ou moins dans l’ordre alphabétique, sauf s’il y a une raison forte pour en utiliser une autre)

+0 -0

Salut,

Ça fait un petit moment que je n’ai pas eu l’occasion de faire du Haskell, mais l’idée que je propose est de ramener le problème à quelque chose de plus simple.

En admettant qu’on dispose d’une fonction deletions :: [a] -> [[a]] qui donne length xs listes, la liste à la position i étant la liste passée en argument privée de son i-ème élément, la fonction solve devient:

solve :: Num a => [a] -> [a]
solve xs = map product $ deletions xs

La fonction deletions peut s’écrire de la manière suivante:

deletions :: [a] -> [[a]]
deletions []       = []
deletions (x : xs) = xs : map (x:) (deletions xs)
+1 -0

La première solution proposée (avec division) a un problème si l’élément à retirer est 0, non ?

Les autres solutions proposées ont le soucis de faire des calculs inutiles: l’algorithme est en O(N^2) au lieu d’être en O(N) comme les bonnes solutions.

Si on ne veut pas de division mais garder un algorithme linéaire, je propose de calculer les produits cumulés ([1, x1, x1*x2, x1*x2*x3, ...]) de la liste et de la liste à l’envers, avec les fonctions scanl et scanr. Ensuite on itère sur les deux listes de produits cumulés en parallèle, et on multiplie les deux nombres.

solve li = zipWith (*) (scanl (*) 1 li) (tail $ scanr (*) 1 li)
+2 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte