Counting unordered factorizations with distinct parts Trying to solve this combinatorics problem, I wrote some functions to count the number of unordered distinct factorizations of an integer n into k distinct parts.

The following function builds up a list of unordered distinct factorizations of n with largest part at most m.

duf' :: Integer -&gt; Integer -&gt; [[Integer]]
duf' m 1 = [[]]
duf' 1 n = []
duf' 0 n = []
duf' m n | isPrime n = if m &lt; n then [] else [[n]]
         | otherwise = concatMap (\x -&gt; map (\y -&gt; x : y) $ 
             duf' (x-1) (n `div` x) ) $ tail $ 
             takeWhile (&lt;= m) $ toList $ divisors n


It is then used below to generate the list of all unordered distinct factorizations of n.

duf :: Integer -&gt; [[Integer]]
duf n = duf' n n


To count the number of factorizations of k parts only I use a simple (and inefficient ?) filter.

pd n k = length . filter (\x -&gt; k == length x) $ duf n


As a beginner, I have the feeling this is not really Haskell-ish. Any help to improve the syntax is welcome !

My concern is that I would like to avoid filtering and (if possible) to count without generating an enormous list. Is there a way to "merge" pd and duf' ? Or at least optimizing the thing ?

I use this two external functions : Math.NumberTheory.Primes.Factorisation.divisors and Data.Numbers.Primes.isPrime. Are there better choices ?
I took a couple passes (gist) at this and managed to improve the style a bit, but I couldn't move the needle on performance at all.

Style

My thoughts and justifications on important changes are written as in-line comments below.

module Main where

import qualified Math.NumberTheory.Primes.Factorisation as Factorisation
import           Data.Numbers.Primes                                     (isPrime)
import           Data.Set                                                (toAscList)

duf' :: Integer -&gt; Integer -&gt; [[Integer]]
duf' _ 1 = [[]] -- Underscores in place of unused variable names
duf' 1 _ = [  ]
duf' 0 _ = [  ]
duf' m n | isPrime n = if m &lt; n then [] else [[n]]
         | otherwise = concatMap (\x -&gt; map (x:) $ duf' (x-1) (n `div` x)) -- Sectioning cons operator
                                 (tail . takeWhile (&lt;= m) $ divisors n) -- Reflowed for legibility
  where
    divisors = toAscList . Factorisation.divisors -- Locally bound to decrease datatype mismatch line noise

duf :: Integer -&gt; [[Integer]]
duf n = duf' n n

pd :: Integer -&gt; Int -&gt; Int
pd n k = length . filter ((== k) . length) $ duf n -- Function composition for ordering


Some reorganizing of layout in duf' made it a lot more comprehensible.

Performance

After rewriting duf', I noticed that the inner lists it returns are only ever really used for their length, so I came up with this version that tosses out the actual elements in favor of keeping a tally whenever a new element would be added instead.

duf' :: Integer -&gt; Integer -&gt; [Int]
duf' _ 1 = [0]
duf' 1 _ = [ ]
duf' 0 _ = [ ]
duf' m n | isPrime n = if m &lt; n then [] else [1]
         | otherwise = concatMap (\x -&gt; map (+1) $ duf' (x-1) (n `div` x))
                                 (tail . takeWhile (&lt;= m) $ divisors n)
  where
    divisors = toAscList . Factorisation.divisors

duf :: Integer -&gt; [Int]
duf n = duf' n n

pd :: Integer -&gt; Int -&gt; Int
pd n k = length . filter (== k) $ duf n


Unfortunately, this doesn't net us any wins in run time as I only really smeared out the inner call to length from filter in pd across duf' (this is less idiomatic, in my opinion). One potential positive is that this version may be more space efficient due to not keeping lists of elements around when all we really care about is the list spine anyway. I wasn't testing for that though, so I don't have any cold hard facts at hand and I suspect you'd have to use an argument strict version of (+1) to prevent building up chains of thunks before realizing any real decrease in memory.