The example I want to generalize

The following function generates every length-2 list [a,b] using the integers from 1 to top for which a < b.

ascendingPairs top = [ [x,y]
                     | x <- [1..top],
                       y <- [x 1..top] ]

Here it is in action:

> mapM_ (putStrLn . show) $ f  4
[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]

The generalization I want

ascendingPairs is defined only for the special case that the lists produced should have length 2. What if I don't know how long the output lists should be, and want that length to be an argument?

Some bad strategies

Here's a dumb way to provide for an additional length argument:

partial :: Int -> Int -> [[Int]]
partial 1 top = [ [x]
             | x <- [1..top] ]
partial 2 top = [ [x,y]
             | x <- [1..top],
               y <- [x 1 .. top] ]
partial 3 top = [ [x,y,z]
             | x <- [1..top],
               y <- [x 1 .. top],
               z <- [y 1 .. top] ]
partial 4 top = ...
partial 5 top = ...
...

Writing partial that way, it would take literally forever to cover every case.

Here's a way to cover all cases. (This way actually does need the list monad.)

slow :: Int -> Int -> [[Int]]
slow top size =
  filter monotonicAscending $
  mapM (\x -> [1..top]) [1..size]

monotonicAscending :: [Int] -> Bool
monotonicAscending (a:b:rest) = a < b
  && monotonicAscending (b:rest)
monotonicAscending _ = True

slow saves human time, but at the expense of a ton of machine time, because it generating so many scales that filter monotonicAscending immediately drops. Computing length $ f 41 7 takes at least a minute, maybe hours (I cut it off). For my purposes I'd actually prefer partial to slow.

A solution that I hope is more complex than necessary

Eventually I did find a way, but I feel like I'm brute forcing it.

monoAscending :: Int -> Int -> [[Int]]
monoAscending top size =
  map reverse $
  incrementNTimes top (size-1) $ [ [a]
                                 | a <- [1..top] ]

incrementNTimes :: Int -> Int -> [[Int]] -> [[Int]]
incrementNTimes top 0 lists = lists
incrementNTimes top n lists = let
  x :: [[Int]]
  x = concatMap (increments top) lists
  in incrementNTimes top (n-1) x

-- | All the ways of prepending a bigger element to the input list.
-- This assumes the input list is in descending order.
increments :: Int -> [Int] -> [[Int]]
increments top (a:as) = [ b:a:as
                        | b <- [a 1 .. top]]

It works:

> mapM_ (putStrLn . show) $ monoAscending 4 3
[1,2,3]
[1,2,4]
[1,3,4]
[2,3,4]

But is there a better way?

CodePudding user response：

I recommend directly extending your very first idea, for partial. Just... use recursion!

notPartial 0 bot top = [[]]
notPartial n bot top = do
    x <- [bot..top]
    xs <- notPartial (n-1) (x 1) top
    pure (x:xs)

Then you can make an alias that fixes bot if you like.

monoAscending n top = notPartial n 1 top

Try it out:

> monoAscending 3 5
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

CodePudding user response：

Your solution suffers from three resolvable complexities.

1. You have two base cases (the last argument to incrementNTimes in monoAscending is a base case, as well as the base case in incrementNTimes).
2. You're passing the result as an argument rather than simply using it as a result (almost like you've prematurely tail-call optimized).
3. You're messing around with reversing.

Fortunately, all three of these are simplifiable!

First, let's start by having just one base case:

mkLists :: Int -> Int -> [[Int]]
mkLists _top 0 = [[]]
mkLists top size = ...

There is a single possible list of zero length, which is the empty list, so we return the list containing the empty list.

Now, let's use the result of the recursive call without tail-call optimizing:

mkLists top size = concatMap increments $ mkLists top (size - 1)
  where
    increments ...

There's no need to pass the recursive call as an argument anywhere if we can manipulate it directly with concatMap go.

Lastly, let's write a version of increments that adds small elements to the beginning of the list rather than big ones so that we don't need to reverse the lists at the end.

  where
    increments [] = pure <$> [1..top]
    increments xs@(x:_) = (:xs) <$> [1..(x-1)]

When increments gets the empty list, it presumably means the recursive call was for size=0, so we produce all of the singleton lists from 1..top. For all other cases, we want to cons a smaller element on the front of the given list.

In total, the code is:

mkLists :: Int -> Int -> [[Int]]
mkLists _top 0 = [[]]
mkLists top size = concatMap increments $ mkLists top (size-1)
  where
    increments [] = pure <$> [1..top]
    increments xs@(x:_) = (:xs) <$> [1..(x-1)]

From here, if you want, you can code golf this down even more. The helper function increments can be written as a one-liner (increments xs = (:xs) <$> [1..(maybe top (subtract 1) $ headMay xs)]), and the recursion itself can be rewritten as a fold.