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.
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!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With