У меня есть понимание списка, которое выглядит так:
cross ps = [ p* pp * ppp | p <- ps, pp <- ps, ppp <- ps, p >= pp , pp >= ppp ]
Как мне добиться этого, используя монады, не вводя буквально имена списков?
dim ps n = do
p <- ps
pp <- ps
ppp <- ps
p...p <- ps
guard (p >= pp && pp >= ppp ... && p...p >=p....p)
return (p*pp*ppp*p...p)
Как я могу сделать это без явного присвоения значений, чтобы использовать монаду списка?
Вот как бы я это сделал
ascending :: Ord a => [a] -> Bool
ascending list = and $ zipWith (>=) (tail list) list
dim ps n = map product $ filter ascending allComb
where allComb = replicateM n ps
replicateM происходит от Control.Monad и для монады списка генерирует все комбинации n элементов данного списка. Затем я отфильтровываю только те комбинации, которые находятся в порядке возрастания, и, наконец, вычисляю произведения оставшихся списков.
Возможно, самым простым для понимания решением является буквальное использование цикла:
dim ps n = do
pz <- forM [1..n] $ \_i -> do
p <- ps
return p
guard $ descending pz
return $ product pz
Но do {p <- ps; return p} эквивалентно простому ps, а для forM [1..n] $ \_i -> ps у нас есть сокращение replicateM n ps. Таким образом, вы получаете решение, предложенное Чи. Я бы сказал, что Лука Хорват на самом деле немного лучше.
Но опять же, как заметил Чи, вы можете сделать это намного эффективнее, не выбирая все возможные комбинации и отбрасывая подавляющее большинство, а в первую очередь выбирая только нисходящие возможности. Для этого я бы вручную написал рекурсивную функцию:
descendingChoices :: Ord a => Int -> [a] -> [[a]]
descendingChoices 1 ps = [[p] | p<-ps] -- aka `pure<$>ps`
descendingChoices n ps = [ p : qs | qs <- descendingChoices (n-1) ps
, p <- ps
, all (<=p) qs
]
Близкий перевод может быть:
dim :: Num a => [a] -> Int -> [a]
dim ps n = do
chosen <- replicateM n ps
guard $ increasing chosen
return $ product chosen
increasing :: Ord a => [a] -> Bool
increasing [] = True
increasing xs@(_:ys) = and $ zipWith (<=) xs ys
Однако это можно улучшить, поставив охрану раньше. Я имею в виду:
[ ... | p1<-xs, p2<-xs, p3<-xs, p1 <= p2, p2 <= p3 ]
хуже, чем
[ ... | p1<-xs, p2<-xs, p1 <= p2, p3<-xs, p2 <= p3 ]
поскольку последний будет избегать сканирования всего списка на наличие p3<-xs при p1 <= p2, поэтому мы все равно ничего не будем генерировать.
Итак, попробуем еще раз, с более примитивным подходом:
dim :: Num a => [a] -> Int -> [a]
dim ps 0 = [1]
dim ps n = do
x <- ps
xs <- dim (filter (>=x) ps) (n-1)
return (x * xs)
Теперь мы отбрасываем невозможные альтернативы раньше, удаляя их из ps перед рекурсивным вызовом.
Учитывая, что ваш список простых чисел находится в порядке возрастания, вы можете полностью избежать охранников, сгенерировав каждый набор продуктов только один раз для начала:
cross :: Int -> [a] -> [[a]]
cross 0 _ = [[]]
cross n [] = []
cross n all@(x:xs) = ((x:) <$> cross (n - 1) all) ++ cross n xs
dim :: Num a => Int -> [a] -> [a]
dim n xs = map product $ cross n xs
Если список простых чисел не отсортирован по возрастанию, то лучший вариант — отсортировать его и использовать алгоритм, предполагающий, что список отсортирован. amalloy дал один, однако вы можете сделать функцию, которая генерирует k-комбинации с повторениями (aka cross), более эффективной, используя совместное использование (пример).
Другой такой алгоритм
dim :: (Num a, Ord a) => Int -> [a] -> [a]
dim 0 xs = [1]
dim n xs = [y * x | x <- xs, y <- dim (n - 1) (takeWhile (<= x) xs)]
Обратите внимание на takeWhile вместо filter. Таким образом, вам не нужно снова и снова обрабатывать весь список простых чисел, вместо этого вы всегда обрабатываете только те простые числа, которые вам действительно нужны.
