patternMinor
Generating smooth numbers in Haskell
Viewed 0 times
smoothgeneratinghaskellnumbers
Problem
I wrote a
For instance:
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
Is it possible to simplify this as well even though the
smooth function that returns a list of all smooth numbers below a certain limit from a list of prime:repeatMul init limit = takeWhile (>= inner xsFor 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 xIs 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) 1Intermediate 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? :PExtra 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) 1smooth 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? :Psmooth limit = foldr (foldMap . repeatMul limit) (singleton 1)Context
StackExchange Code Review Q#150299, answer score: 4
Revisions (0)
No revisions yet.