[Haskell] Manipulations de listes

Deux questions "simples".

1. j'aimerais construire couple :: [a] -> [[a]] qui me donnerait toutes les paires [x,y]. Je précise que je démarre depusi hier (ça vous le savez ... ;)), juste avec la doc.

La fonction générale pour les sous-tuples est ok:

Code:

---

1 2 3 4

combinations :: Int -> [a] -> [[a]] combinations 0 _ = [ [] ] combinations n xs = [ y:ys | y:xs' <- tails xs , ys <- combinations (n-1) xs']

---

Mais est-il possible de la simplifier pour ne tenir compte que de n=2 ? J'ai essayé

Code:

---

1 2 3

couple :: [a] -> [[a]] couple xs = [y:ys | y:xs' <- tails xs , ys <- tails xs']

---

qui bien sûr ne marche pas, et même

Code:

---

1 2 3

couple :: [a] -> [[a]] couple xs = [y:ys | y:xs' <- tails xs , ys <- head.tails xs']

---

mais ce head qui me resoudrait le problème ne fonctionne pas!

2. Une fois la fct couple ok, j'obtiendrai donc une liste [[x1,y1],[x2,y2],...], et étant donné une fonction f:Integer -> Integer -> Integer, j'aimerais l'appliquer à cette liste; c'est avec zipWith, c'est cela?

Merci pour ceux qui pourront aider un dilletante ...

J'ai regardé dans mes fonctions persos et celle-ci me semble correspondre à ce que tu cherche:

Code:

---

1 2 3 4 5

# let rec pair_list l = match l with | [] -> [] | a::t -> (List.map (fun b -> a,b) t) @ pair_list t;; val pair_list : 'a list -> ('a * 'a) list = <fun>

---

Remarques:

• désolé, c'est du Caml
• désolé, je ne saurais pas faire avec une liste 'en compréhension'
• j'ai supposé que la fonction à appliquer est commutative, c'est-à-dire que si la liste renvoyée contient le couple (a,b) alors elle ne contient pas le couple (b,a)

Alors, pour toutes les parties à deux éléments d'une liste :

Code:

---

couple xs = [ [x,y] | x:ys <- tails xs, y <- ys]

---

Mais je ne suis pas sûr que tu veuilles vraiment une liste de liste, ne veut tu pas plutôt une liste de tuples ?

Code:

---

couple xs = [ (x,y) | x:ys <- tails xs, y <- ys]

---

Par ailleurs zipWith prend deux listes en paramêtre, pas une liste de tuple, il faudrait d'abord utiliser unzip pour pouvoir utiliser zipWith, il serait plus simple de faire un simple map (si j'ai bien compris le but) :

Code:

---

applyToCoupleList f = map (uncurry f)

---

(mon nom manque d'imagination...)

--
Jedaï

Merci Jedai. Je pense avoir trouvé:

Code:

---

1 2 3

couple xs = [ (x,y) | x:ys <- tails xs, y <- ys] compa c cc = (foldl (\x y -> x+y) 0 (zipWith (\x y -> if x>y then x-y else y-x) c cc)) compar = (uncurry compa)

---

Ca marche, mais y-a-t'il mieux pour la fct compa?

Je ne suis pas très sûr de ce que tu veux dire par "ça marche" vu que je n'ai pas vu d'exemple d'application, mais pour compa, voilà ce que j'aurais écris (principalement des améliorations esthétiques) :

Code:

---

compa xs ys = sum $ zipWith (\x y-> abs $ x-y) xs ys

---

(Par ailleurs je l'aurais sans doute directement écrit en style non-curryfié, sauf si j'en avais besoin ailleurs bien sûr (mais ça ressemble à un bon candidat pour l'inclusion dans un "where", du moins avec les informations dont je dispose)).

--
Jedaï

merc pour la rq Jedai. OUi, ça va être utilisé dans un where.

Ceci dit, je me rends compte qu'ayant commencé "en direct" Haskell, je découvre les fct de base au fur et à mesure! En fait j'utilsie l'index pour chercher des lsites de fct... j'utilise la recherche sur "tails" pour obtenir les fct datalist, etc.

Il me faudra encore bien du temps avant d'appréhender toute la puissance d'Haskell... ;)

Tu pourrais utiliser la fonction "recherche par types" de hoogle : l'idée est de demander un type de fonction à hoogle, et il te propose les fonctions qui coresspondent le plus au type demandé.

C'est assez utile pour la recherche, et très formateur parce que ça oblige à bien penser au type de la fonction que l'on cherche, et que souvent le type, c'est l'essentiel.

Merci pour l'info Bluestorm, c'est effectivement très utilise. Mais je vais laisser de coté Haskell pour un temps, la charge au boulot remonte fortement :mouarf:

Le but de l'algorithme est-il bien de calculer la somme des différences en valeurs absolues de toutes les paires d'éléments ?

Dans ce cas, pourquoi ne pas écrire simplement:

Code:

---

1 2	compar xs = sum [abs $ x - y | x:ys <- tails xs, y <- ys]

---

On peut aussi utiliser cet autre algorithme, basé sur le fait que le calcul est simplifiable si les valeurs sont triées:

Code:

---

1 2 3

compar2 xs = sum $ zipWith (*) [n,n+2..] $ sort xs where n = 1 - genericLength xs

---

La compexité de l'algorithme original est O(n^2) puisqu'il faut générer toutes les paires, alors que la complexité de celui-ci dépend de celle de la fonction sort. Je ne sais pas quel algorithme de tri est implémenté dans le module List mais j'imagine qu'il est O(n*log(n)).