Discussion:Tri fusion

Dernier commentaire : il y a 17 ans par Lunar dans le sujet Suggestion de modification de l'implémentation Haskell
Autres discussions [liste]
  • Admissibilité
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
  • Commons

Suggestion de modification de l'implémentation Haskell

modifier

Je propose une version un peu différente de l'implémentation haskell :

  triFusion' [] = []
  triFusion' [a] = [a]
  triFusion' l =
  let
   fusion' [] l = l
   fusion' l [] = l
   fusion' l1@(x:xs) l2@(y:ys)
      | x > y = y:fusion l1 ys
      | otherwise = x:fusion xs l2
   partageListe' [] = ([],[])
   partageListe' [a] = ([a],[])
   partageListe' (a:b:l) = (a:as,b:bs) where (as,bs) = partageListe' l 
   (g,d) = partageListe' l
in fusion' (triFusion' g) (triFusion' d)

En gros, j'ai juste explicité le SplitAt, en utilisant un algorithme un peu différent. Je pense qu'elle serait plus instructive (pour savoir comment faire le split sans utiliser une fonction toute faite), et en plus elle me semble potentiellement plus efficace dans l'idée (un seul parcours de la liste au lieu de deux, un pour length et un pour split) (par contre, elle n'est pas récursive terminale pour des raisons de clarté).

Elle me semble donc préférable, mais n'étant pas un codeur haskell moi même j'ai préféré ne pas prendre l'initiative d'alourdir le code.

Bluestorm 2 mars 2007 à 17:55 (CET)Répondre

Je pense que l'intérêt de mettre une version Haskell de l'algorithme est d'en proposer une implémentation lisible, vu que le tri-fusion est loin d'être le mieux dans un lanage fonctionnel avec des listes chaînées. Je prèfere donc la version avec splitAt (length xs `div` 2) xs qui montre mieux qu'on prend deux moitiés de tableau pour les fusionner ensuite après les avoir trié. Lunar 2 mars 2007 à 18:25 (CET)Répondre
Revenir à la page « Tri fusion ».