Haskell: How to simplify or eliminate liftM2?

Question

Consider the following code I wrote:

import Control.Monad

increasing :: Integer -> [Integer]
increasing n
    | n == 1    = [1..9]
    | otherwise = do let ps = increasing (n - 1)
                     let last = liftM2 mod ps [10]
                     let next = liftM2 (*) ps [10]
                     alternateEndings next last
    where alternateEndings xs ys = concat $ zipWith alts xs ys
          alts x y = liftM2 (+) [x] [y..9]

Where 'increasing n' should return a list of n-digit numbers whose numbers increase (or stay the same) from left-to-right.

Is there a way to simplify this? The use of 'let' and 'liftM2' everywhere looks ugly to me. I think I'm missing something vital about the list monad, but I can't seem to get rid of them.

Answer 1

Well, as far as liftM functions go, my preferred way to use those is the combinators defined in Control.Applicative. Using those, you'd be able to write last = mod <$> ps <*> [10]. The ap function from Control.Monad does the same thing, but I prefer the infix version.

What (<$>) and (<*>) goes like this: liftM2 turns a function a -> b -> c into a function m a -> m b -> m c. Plain liftM is just (a -> b) -> (m a -> m b), which is the same as fmap and also (<$>).

What happens if you do that to a multi-argument function? It turns something like a -> b -> c -> d into m a -> m (b -> c -> d). This is where ap or (<*>) come in: what they do is turn something like m (a -> b) into m a -> m b. So you can keep stringing it along that way for as many arguments as you like.

---

That said, Travis Brown is correct that, in this case, it seems you don't really need any of the above. In fact, you can simplify your function a great deal: For instance, both last and next can be written as single-argument functions mapped over the same list, ps, and zipWith is the same as a zip and a map. All of these maps can be combined and pushed down into the alts function. This makes alts a single-argument function, eliminating the zip as well. Finally, the concat can be combined with the map as concatMap or, if preferred, (>>=). Here's what it ends up:

increasing' :: Integer -> [Integer]
increasing' 1 = [1..9]
increasing' n = increasing' (n - 1) >>= alts
    where alts x = map ((x * 10) +) [mod x 10..9]

Note that all refactoring I did to get to that version from yours was purely syntactic, only applying transformations that should have no impact on the result of the function. Equational reasoning and referential transparency are nice!

Answer 2

It looks very unusual to me to use liftM2 (or <$> and <*>) when one of the arguments is always a singleton list. Why not just use map? The following does the same thing as your code:

increasing :: Integer -> [Integer]
increasing n
  | n == 1    = [1..9]
  | otherwise = do let ps = increasing (n - 1)
                   let last = map (flip mod 10) ps
                   let next = map (10 *) ps
                   alternateEndings next last
  where alternateEndings xs ys = concat $ zipWith alts xs ys
        alts x y = map (x +) [y..9]

Answer 3

Here's how I'd write your code:

increasing :: Integer -> [Integer]
increasing 1 = [1..9]
increasing n = let allEndings x = map (10*x +) [x `mod` 10 .. 9]
               in concatMap allEndings $ increasing (n - 1)

I arrived at this code as follows. The first thing I did was to use pattern matching instead of guards, since it's clearer here. The next thing I did was to eliminate the liftM2s. They're unnecessary here, because they're always called with one size-one list; in that case, it's the same as calling map. So liftM2 (*) ps [10] is just map (* 10) ps, and similarly for the other call sites. If you want a general replacement for liftM2, though, you can use Control.Applicative's <$> (which is just fmap) and <*> to replace liftMn for any n: liftMn f a b c ... z becomes f <$> a <*> b <*> c <*> ... <*> z. Whether or not it's nicer is a matter of taste; I happen to like it.¹ But here, we can eliminate that entirely.

The next place I simplified the original code is the do .... You never actually take advantage of the fact that you're in a do-block, and so that code can become

let ps   = increasing (n - 1)
    last = map (`mod` 10) ps
    next = map (* 10)     ps
in alternateEndings next last

From here, arriving at my code essentially involved writing fusing all of your maps together. One of the only remaining calls that wasn't a map was zipWith. But because you effectively have zipWith alts next last, you only work with 10*p and p `mod` 10 at the same time, so we can calculate them in the same function. This leads to

let ps = increasing (n - 1)
in concat $ map alts ps
where alts p = map (10*p +) [y `mod` 10..9]

And this is basically my code: concat $ map ... should always become concatMap (which, incidentally, is =<< in the list monad), we only use ps once so we can fold it in, and I prefer let to where.

---

1: Technically, this only works for Applicatives, so if you happen to be using a monad which hasn't been made one, <$> is `liftM` and <*> is `ap`. All monads can be made applicative functors, though, and many of them have been.

Answer 4

I think what you are trying to do is this:

increasing :: Integer -> [Integer]
increasing 1 = [1..9]
increasing n = do p <- increasing (n - 1)
                  let last = p `mod` 10
                      next = p * 10
                  alt <- [last .. 9]
                  return $ next + alt

Or, using a "list comprehension", which is just special monad syntax for lists:

increasing2 :: Integer -> [Integer]
increasing2 1 = [1..9]
increasing2 n = [next + alt | p <- increasing (n - 1),
                              let last = p `mod` 10
                                  next = p * 10,
                              alt <- [last .. 9]
                ]

The idea in the list monad is that you use "bind" (<-) to iterate over a list of values, and let to compute a single value based on what you have so far in the current iteration. When you use bind a second time, the iterations are nested from that point on.

Answer 5

I think it's cleaner to pass last digit in a separate parameter and use lists.

f a 0 = [[]]
f a n = do x <- [a..9]
           k <- f x (n-1)
           return (x:k)

num = foldl (\x y -> 10*x + y) 0

increasing = map num . f 1