Haskell list monad looping

Question

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?

Answer 1

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.

Answer 2

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
                         ]