HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Generating smooth numbers in Haskell

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
smoothgeneratinghaskellnumbers

Problem

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 (>= 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?

Solution

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.

Code Snippets

smooth limit = foldlM (`repeatMul` limit) 1
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
smooth limit = foldr (foldMap . repeatMul limit) (singleton 1)

Context

StackExchange Code Review Q#150299, answer score: 4

Revisions (0)

No revisions yet.