module Powerset where

{- Expand muliplies of two list of numbers.
   For example:
   mult_expand [1, 2, 4] [1, 5]
   Produces:
   [[1,5],[2,10],[4,20]]
-}
mult_expand p [] = p:[]
mult_expand p lst =
    map (\x -> map (*x) lst) p

{- expand the powers of x from 0 to exp -}
pows x exp = map (\e -> x^e) [0..exp]

{- expand the powers the first item in a pair
   from 0 to the second item in the pair.
-}
powerlst p = pows (fst p) (snd p)

{- One stage of a merge sort -}
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y
                      then x : merge xs (y:ys)
                      else y : merge (x:xs) ys

{- Do multiple merges to get an ordered list. -}
bigmerge lsts =
    foldl merge [] lsts

{- The complete power set of a list of factor/exponent pairs.  For example:
   powerset [(2,3),(5,1)]
Produces:
   [1,2,4,5,8,10,20,40]
-}
powerset [] = []
powerset (x:xs) =
    bigmerge (mult_expand (powerlst x) (powerset xs))

{- Helper function for factor_sqrt.
   Finds the last list value less than or equal to the
   given limit.
-}
fsqrt lim lastgood [] = lastgood
fsqrt lim lastgood (x:xs) =
    if (x > lim) then lastgood
	         else fsqrt lim x xs

{- Find the last divisor less than the square root,
   given the number and its factors
-}
factor_sqrt n factors =
    fsqrt (sqrt n) 0 (powerset factors)