6
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$
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

Extra answer:

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.

\$\endgroup\$
  • \$\begingroup\$ How is this a code review? Please read how-to-answer \$\endgroup\$ – janos Dec 19 '16 at 23:12
  • \$\begingroup\$ That rule is stupid. He wondered whether a higher order function could achieve his purpose and it could. Elaboration just answers more general questions in this case. In fact I started with a longer answer and threw away unnecessary parts until perfection. I suppose intermediate steps can provide reasonable filler. \$\endgroup\$ – Gurkenglas Dec 19 '16 at 23:29
  • 1
    \$\begingroup\$ Are you sure that your original one-line answer without an explanation is adequate guidance for somebody new to haskell? Would the OP surely get your point, marvel at the beauty, and be enlightened without explanation? (btw I'm not the downvoter) \$\endgroup\$ – janos Dec 19 '16 at 23:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Dec 19 '16 at 23:54
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Dec 20 '16 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.