# Generating smooth numbers in Haskell

I wrote a smooth function that returns a list of all smooth numbers below a certain limit from a list of prime:

repeatMul init limit = takeWhile (<=limit) . scanl (*) init . repeat

smooth limit = (inner 1)
where inner [] init = [init]
inner (x:xs) init = repeatMul init limit x >>= inner xs


For instance:

main = print . sort . smooth 20 $[2, 3, 5] -- [1,2,3,4,5,6,8,9,10,12,15,16,18,20]  It works fine, but I wonder if the inner function could be written in a different way. I've been trying to find a high order function to achieve the same purpose, but I can't wrap my head around it. Also I'm new to haskell, so any general comment is welcome. Extra question: I have another version of smooth that returns a set instead of a list: import Data.Set (singleton, unions) repeatMul limit x = takeWhile (<=limit) . iterate (*x) smooth limit xs = foldr f singleton xs$ 1
where f x c = unions . map c . repeatMul limit x


Is it possible to simplify this as well even though the Set type does not instantiate the Monad type class?

smooth limit = foldlM (repeatMul limit) 1


Intermediate steps:

smooth limit = (inner 1)
where inner [] = pure
inner (x:xs) = flip (repeatMul limit) x >=> inner xs

smooth limit = (inner 1)
where inner = foldr (>=>) pure . map (flip (repeatMul limit))

smooth limit xs = (foldr (>=>) pure \$ map (flip (repeatMul limit)) xs) 1

smooth limit = foldl (>>=) (pure 1) . map (flip (repeatMul limit))

smooth limit = foldlM (flip id) 1 . map (flip (repeatMul limit)) -- did I mention foldlM has its argument order as stupid as repeatMul? :P


There is no need for the no-duplicates bookkeeping of sets - every natural has a unique prime factorization. Anyway, here as a fold from the right, if repeatMul produced a set:
smooth limit = foldr (foldMap . repeatMul limit) (singleton 1)

Note that this also works for the list case with [1] in place of singleton 1.
• Yep, that was the idea. He knows of higher order functions and uses scanl and []'s Monad instance and googling "haskell foldlM" also shows him what he needs if he doesn't know hoogle. – Gurkenglas Dec 19 '16 at 23:54
• The foldrM version reverses the order of monadic operations, that is the order in which it chooses the exponent of each prime. If you sort the output anyway, that makes no difference. (I'm not sure of the runtime properties of each order.) Writing from scratch, I would have used foldlM and inlined repeatMul, grumbling about foldlM's first argument's argument order. – Gurkenglas Dec 20 '16 at 10:32