Как составить отсортированный список по нескольким числам?

Question

У меня проблемы с заданием из моего класса на Хаскеле. Я уже решил частичную проблему этой задачи: мне нужно написать функцию, которая принимает Int и создает бесконечный список с кратными этого Int.

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

Консоль

ghci> take 10 (function 3)

дает

[3,6,9,12,15,18,21,24,27,30]

Во втором задании мне нужно расширить функцию, чтобы она принимала список чисел и использовала каждое значение этого списка в качестве фактора (d ранее). Например:

ghci> take 10 (function [3, 5])

должен дать

[3,5,6,9,10,12,15,18,20,21]

Уже попробовал понимание списка, как

function d = [y*x | y <- [1..], x <- d]

но функция возвращает список в несортированном виде:

[3,5,6,10,9,15,12,20,15,25]

Мы получили подсказку, что мы должны использовать функцию по модулю Haskell, но я не знаю, как именно поступить. У вас есть хороший совет для меня?

Answer 1

У меня есть один вкладыш.

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]

время выполнения должно быть O (n² + n * d) из результирующего списка. nub работает в O (n²). Было бы неплохо избавиться от этого.

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

Это работает довольно хорошо. Это должно работать в O (n * d). У меня также есть эта версия, которая, по моему мнению, работает по крайней мере так же хорошо, как g , но, очевидно, она работает лучше, чем f и хуже, чем g .

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

Я не уверен, почему это так, или настолько ленивы, насколько я могу судить, и я не вижу причин, почему он должен работать медленнее. Это особенно не масштабируется, когда вы увеличиваете длину списка ввода.

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)

Больше не один лайнер, но самый быстрый, который я смог придумать. Я не уверен на сто процентов, почему это имеет такое большое значение во время выполнения, если вы свернули вправо или влево и если вы сортируете входной список заранее. Но это не должно повлиять на результат, так как:

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

Мне совершенно безумно думать об этой проблеме с точки зрения сворачивания рекурсивной функции по списку бесконечных списков, кратных входным коэффициентам.

В моей Системе он примерно в 10 раз медленнее, чем другое решение, представленное здесь с использованием Data.List.Ordered.

Answer 2

Если вы думаете, что d является фактором, а не

y = x * d 

но вместо

y `mod` d == 0,

затем вы можете получить понимание списка из списка [1..] и добавить функцию предиката, например:

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

Более выразительная версия, которую, пожалуй, легче понять в начале:

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

Answer 3

Ответ здесь просто показывает идею, это не оптимизированное решение, возможно, существует много способов его реализации.

Во-первых, вычислите все значения каждого фактора из введенного списка:

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

Например: xs = [3, 5] дает

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

затем найдите минимальное значение 1-го элемента каждого списка как:

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

Как только мы нашли, что список содержит минимальное значение, верните его и удалите минимальное значение из списка как:

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

Так, например, после поиска первого значения (т.е. 3) результата, списки для поиска следующего значения:

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

Повторите вышеперечисленные шаги, мы можем построить нужный список. Наконец, удалите дублированные значения. Вот завершенная кодировка:

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

Answer 4

Есть довольно хорошее рекурсивное решение

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)

braid функция строит нужный список "на лету", используя только голову ввода и лень

Answer 5

Если вы хотите сделать это с помощью функции по модулю, вы можете определить простой однострочный

foo ds = filter (\x -> any (== 0) [mod x d | d <- ds]) [1..]

или, в более читаемой форме,

foo ds = filter p [1..]
  where
  p x = any id [ mod x d == 0 | d <- ds]
      = any (== 0) [ mod x d | d <- ds]
      = not $ null [ () | d <- ds, mod x d == 0]
      = null [ () | d <- ds, mod x d /= 0]
      = null [ () | d <- ds, rem x d > 0]

С этим мы получаем

> take 20 $ foo [3,5]
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]

Но это неэффективно: last $ take 20 $ foo [300,500] == 4200, поэтому для получения этих 20 чисел этот код проверяет 4200. И чем хуже эти числа, тем хуже.

Вместо этого мы должны произвести n чисел во времени, примерно пропорциональных n.

Для этого сначала запишите кратные числа каждого числа в их собственном списке:

[ [d*x | x <- [1..]] | d <- ds ] ==
[ [d, d+d ..] | d <- ds ] 

Затем объедините эти упорядоченные увеличивающиеся списки чисел упорядоченным образом, чтобы получить один упорядоченный неубывающий список чисел. Пакет data-ordlist имеет множество функций для работы со списками такого типа:

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

Если мы хотим, чтобы созданный список не содержал дубликатов, то есть создать увеличивающийся список, мы можем изменить его на

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

Да, и, в отличие от квадратичного Data.List.nub, Data.List.Ordered.nub является линейным, тратит O(1) времени на каждый элемент списка ввода.