Haskell: How to simplify or eliminate liftM2?

Question

Consider the following code that 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 xy = liftM2 (+) [x] [y..9] 

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

Is there any way to simplify this? Using ' let ' and ' liftM2 ' everywhere looks ugly to me. I think that I am missing something vital for the monad list, but I cannot get rid of them.

Answer 1

I think you are trying to do 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 a 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 a list monad is that you use "bind" ( <- ) to iterate over the list of values ​​and let to calculate a single value based on what you still find in the current iteration. When you use bind a second time, iterations are nested from that point.

Answer 2

Well, as for the liftM functions, my preferred way to use them is with combinators defined in Control.Applicative . Using them, you can write last = mod <$> ps <*> [10] . The ap function from Control.Monad does the same, but I prefer the infix version.

What (<$>) and (<*>) looks like this: liftM2 turns the function a -> b -> c into the function ma -> mb -> mc . The usual liftM is just (a -> b) -> (ma -> mb) , which matches fmap as well as (<$>) .

What happens if you do this with a function with multiple arguments? It turns something like a -> b -> c -> d into ma -> m (b -> c -> d) . Here ap or (<*>) enter: what they do turns something like m (a -> b) into ma -> mb . Thus, you can maintain binding to it in the same way as many arguments as you like.

---

However, Travis Brown is right that in this case it seems that you really do not need any of the above. In fact, you can greatly simplify your function: for example, both last and next can be written as functions with one argument displayed on the same list, ps and zipWith are the same as zip and a map . All these cards can be combined and shifted to the alts function. This makes the alts function with one argument, excluding zip as well. Finally, concat can be combined with map as concatMap or, if desired, (>>=) . Here it ends:

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

Please note that all the refactorings I made for this version were purely syntactic, using transformations that should not affect the result of the function. Rational reasoning and link transparency are good!

Answer 3

It is very unusual for liftM2 use liftM2 (or <$> and <*> ) when one of the arguments is always a singleton list. Why not just use map ? The following does the same 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 xy = map (x +) [y..9] 

Answer 4

This is how I 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 came to this code as follows. The first thing I did was use pattern matching instead of guards, as it is clearer here. The next thing I did was remove liftM2 s. They are not needed here because they are always called with one size-one list; in this case, this is the same as calling map . So, liftM2 (*) ps [10] is just map (* 10) ps and similarly for other call sites. If you need a general replacement for liftM2 , you can use Control.Applicative <$> (it's just fmap ) and <*> to replace liftMn for any n : liftMn fabc ... z becomes f <$> a <*> b <*> c <*> ... <*> z . Whether it is more enjoyable is a matter of taste; I like it so. ¹ But here we can completely rule it out.

The next place I simplified the source code is do ... You never use the fact that you are in a do block, and therefore the code may become

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

From here, having come to my code, it was essentially connected with a record holding all your map together. One of the remaining calls that was not map was zipWith . But since you have zipWith alts next last , you only work with 10*p and p `mod` 10 at a 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, by the way, is =<< in the list monad), we use only ps so that we can collapse it, and I'm from let to where .

---

1: Technically, this only works for Applicative s, so if you use a monad that has not been done, <$> is `liftM` and <*> `ap` . All monads can be made by applicative functors, and many of them were.

Answer 5

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

 fa 0 = [[]] fan = do x <- [a..9] k <- fx (n-1) return (x:k) num = foldl (\xy -> 10*x + y) 0 increasing = map num . f 1