I have a list comprehension that looks like this:
cross ps = [ p* pp * ppp | p <- ps, pp <- ps, ppp <- ps, p >= pp , pp >= ppp ]
How do I achieve this using monads without literally typing out the list names?
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)
How can I do this without explicitly assigning values in order to use the list monad?
Here's how I'd do it
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
The replicateM comes from Control.Monad and for the list monad it generates all combinations of n elements of the given list.
Then I filter out just the combinations that are in an ascending order and finally calculate the products of the lists that remained.
A close translation could be:
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
However, this could be improved by putting the guards earlier. I mean:
[ ... | p1<-xs, p2<-xs, p3<-xs, p1 <= p2, p2 <= p3 ]
is worse than
[ ... | p1<-xs, p2<-xs, p1 <= p2, p3<-xs, p2 <= p3 ]
since the latter will avoid scanning the whole list for p3<-xs when p1 <= p2, so we are not going to generate anything anyway.
So, let's try again, with a more primitive approach:
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)
Now we discard impossible alternatives early, removing them from ps before the recursive call.
Perhaps the easiest to understand solution is to “literally use a loop”:
dim ps n = do
pz <- forM [1..n] $ \_i -> do
p <- ps
return p
guard $ descending pz
return $ product pz
But do {p <- ps; return p} is equivalent to simply ps, and for forM [1..n] $ \_i -> ps we have the shorthand replicateM n ps. So you get to chi's suggested solution. I'd say Luka Horvat's is actually a little better, though.
But then again, as chi remarked, you can make this a lot more efficient by not selecting all possible combinations and throwing the vast majority away, but rather only selecting the descending possibilities in the first place. For this I'd manually write a recursive function:
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
]
Given that your list of primes is in ascending order, you can avoid the guards entirely, by only generating each set of products once to begin with:
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
If the list of primes is not in ascending order, then the best option is to sort it and use an algorithm that assumes the list is sorted. amalloy gave one, however you can make the function that generates k-combinations with repetitions (aka cross) quite more efficient by using sharing (an example).
Another such algorithm is
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)]
Note the takeWhile instead of filter. This way you don't need to process the whole list of primes over and over again, instead you always process only those primes that you actually need.
