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\$

1 Answer 1

Reset to default
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\$
7
  • \$\begingroup\$ How is this a code review? Please read how-to-answer \$\endgroup\$ Commented Dec 19, 2016 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\$ Commented Dec 19, 2016 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\$ Commented Dec 19, 2016 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\$ Commented Dec 19, 2016 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\$ Commented Dec 20, 2016 at 10:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.