Comment faire une liste triée de multiples pour plusieurs nombres?

Si vous voulez le faire avec la fonction modulo, vous pouvez définir un simple one-liner

baz ds = O.nub $ foldr O.merge [] [ [d, d+d ..] | d <- ds ]
       = foldr    O.union [] [ [d, d+d ..] | d <- ds ]
       = O.foldt' O.union [] [ [d, d+d ..] | d <- ds ]
       = O.unionAll [ [d, d+d ..] | d <- sort ds ]
       = (O.unionAll . map (iterate =<< (+)) . sort)  ds

ou, sous une forme plus lisible,

import qualified Data.List.Ordered as O
import           Data.List               (sort)

bar :: (Ord a, Num a, Enum a) => [a] -> [a]
bar ds = foldr    O.merge [] [ [d, d+d ..] | d <- ds ]
       = O.foldt' O.merge [] [ [d, d+d ..] | d <- ds ]   -- more efficient, 
       = O.mergeAll [ [d, d+d ..] | d <- sort ds ]       -- tree-shaped folding

La réponse ici montre juste l'idée, ce n'est pas une solution optimisée, il peut exister de nombreuses façons de l'implémenter.

Premièrement, calculez toute la valeur de chaque facteur à partir de la liste saisie:

import Data.Sequence (update, fromList)
import Data.Foldable (toList)

function :: [Int] -> [Int]
function xs = removeDup $ sortMulti $ map (\d->[d*x|x<-[1..]]) xs
    where sortMulti xss = 
            let idx = findMinValueIndex $ zip [0..] xss
            in  head (xss!!idx):sortMulti (updateList idx (tail $ xss!!idx) xss)

removeDup::[Int]->[Int]
removeDup [] = []
removeDup [a] = [a]
removeDup (x:xs) | x == head xs = removeDup xs
                 | otherwise = x:removeDup xs

findMinValueIndex::[(Int, [Int])]->Int
findMinValueIndex xss = minimum $ 
                        map fst $ 
                        filter (\p-> (head $ snd p) == minValue) xss
    where minValue = minimum $ map (head . snd) xss

updateList::Int->[Int]->[[Int]]->[[Int]]
updateList n xs xss = toList $ update n xs $ fromList xss

Par exemple: xs = [3, 5] donne

[[6, 9, ...], [5, 10, 15, ...]]

alors, trouvez la valeur minimale du 1er élément de chaque liste comme:

sortMulti xss = 
            let idx = findMinValueIndex $ zip [0..] xss
            in  head (xss!!idx):sortMulti (updateList idx (tail $ xss!!idx) xss

Une fois que nous avons trouvé la liste, tenir la valeur minimale, renvoyez-la et supprimez la valeur minimale de la liste comme suit:

findMinValueIndex::[(Int, [Int])]->Int
findMinValueIndex xss = minimum $ 
                        map fst $ 
                        filter (\p-> (head $ snd p) == minValue) xss
    where minValue = minimum $ map (head . snd) xss

Donc, par exemple, après trouver la première valeur (c'est-à-dire 3 ) du résultat, les listes pour trouver la valeur suivante est:

[[3, 6, 9, ...], [5, 10, 15, ...]]

répétez les étapes ci-dessus, nous pouvons construire la liste souhaitée. Enfin, supprimez les valeurs dupliquées. Voici le codage terminé:

map (\d->[d*x|x<-[1..]]) xs

Il existe une solution récursive assez intéressante. La fonction

function' :: Int -> [Int]
function' d = [d * x | x <- [1..]]

braid :: [Int] -> [Int] -> [Int]
braid []        bs = bs
braid as        [] = as
braid aa@(a:as) bb@(b:bs) 
  | a < b     = a:braid as bb
  | a == b    = a:braid as bs # avoid duplicates
  | otherwise = b:braid aa bs

function :: [Int] -> [Int]
function ds = foldr braid [] (map function' ds)

tresse crée la liste souhaitée "à la volée" en utilisant uniquement la tête et la paresse de l'entrée

Si vous pensez que d n'est pas un facteur comme

function' ds   
    | null ds   = [1..]
    | otherwise = [ x | x <- [1..], divByAnyIn ds x ]
    where
      divByAnyIn ds x = 
          case ds of
            (d:ds') -> if x `mod` d == 0 then True 
                                         else divByAnyIn ds' x
            _       -> False

mais plutôt

function ds 
    | null ds   = [1..]
    | otherwise = [ x | x <- [1..], qualifies x ]
    where
      qualifies x = any (==0) $ (flip mod) <$> ds <*> [x]

alors vous peut rechercher la compréhension de la liste à partir de la liste [1 ..] et ajouter une fonction de prédicat, par exemple:

y `mod` d == 0,

Une version plus expressive qui est peut-être plus facile à comprendre au début:

y = x * d 

J'ai une ligne unique.

commutative a b = combine [a] [b] == combine [b] [a]

runtime devrait être O (n² + n * d) dans la liste résultante. Le nub s'exécute en O (n²). Ce serait bien de s'en débarrasser.

i xs = foldr1 combine [[x, x+x ..] |x<- sort xs]
    where
      combine l [] = l
      combine [] r = r
      combine l@(x:xs) r@(y:ys)
        | x < y = (x: combine xs r)
        | x > y = (y: combine l ys)
        | otherwise = (x: combine xs ys)

Cela fonctionne assez bien. Il devrait fonctionner en O (n * d). J'ai aussi cette version qui, à mon avis, fonctionne au moins aussi bien que g , mais apparemment, elle fonctionne mieux que f et pire que g .

h xs = [x |x<-[1..], or [x `mod` d == 0 |d<-xs] ]

Je ne sais pas pourquoi, ou est paresseux pour autant que je sache et je ne vois aucune raison pour laquelle il devrait fonctionner Ralentissez. En particulier, il ne s'adapte pas aussi bien lorsque vous augmentez la longueur de la liste d'entrée.

g xs = [x |x<-[1..], let ys = map (mod x) xs in 0 `elem` ys]

Ce n'est plus une seule ligne, mais le plus rapide que j'ai pu trouver. Je ne sais pas à 100% pourquoi cela fait une si grande différence à l'exécution si vous vous pliez à droite ou à gauche et si vous triez la liste d'entrée à l'avance. Mais cela ne devrait pas faire de différence sur le résultat puisque:

import Data.List (nub)

f xs = nub [x|x<-[1..], d<-xs, x `mod` d == 0]

take 10 $ f [3,5] -- [3,5,6,9,10,12,15,18,20,21]

Je trouve complètement insensé de penser à ce problème en termes de pliage d'une fonction récursive sur une liste de listes interminables de multiples de coefficients d'entrée.

Sur mon système, il est toujours un facteur 10 plus lent qu'une autre solution présentée ici en utilisant Data.List.Ordered.