Search code examples
haskelllist-comprehension

I would use a list comprehension, but the number of variables to bind is unknown

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?

Solution

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

    notPartial 0 bot top = [[]]
notPartial n bot top = [ x:xs
    | x <- [bot..top]
    , xs <- notPartial (n-1) (x+1) top
    ]

    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]]