Okay, so I have this generic factorization function, that given an Integer returns the factors of that Integer in the desired manner:
> factors :: Integer -> (Integer -> Integer -> a -> a) -> a -> a > factors x adder ans = factors' 2 (x, adder 1 x ans) > where factors' test (tot, newans) | test >= tot = newans > | otherwise = factors'' (x `divMod` test) test (succ test) (tot, newans) > factors'' (newtot, 0) oldtest test (tot, myans) = factors' test (newtot, adder oldtest newtot myans) > factors'' _ _ test myans = factors' test myans
I don't know if it's the most elegant factorization algorithm in the universe, but it sure beats the heck out of
> slowfactors x = filter (\y -> x `rem` y == 0) [1..x]
for larger x.
Anyway, when I wish to see what the factors are, I call factors with:
> showfactors :: Integer -> [Integer] > showfactors x = factors x (\ y z ans -> if y == z then y:ans else y:z:ans) []
and when I simply wish to know the number of factors, I call:
> countfactors :: Integer -> Integer > countfactors x = factors x (\y z ans -> (if y == z then 1 else 2) + ans) 0
The lambda expressions in these functions are generally adders for their types, so I should be able to further generalize:
> mkAdder :: Eq a => (a -> b) -> (b -> b -> b) -> a -> a -> (b -> b) > mkAdder f g y z = g (if y == z then f y else g (f y) (f z))
Which indeed I've done without problems:
> showfactors x = factors x (mkAdder return mplus) [] > countfactors x = factors x (mkAdder (const 1) (+)) 0
But then I noticed the types I'm using ([Integer] and (Sum) Integer) are Monoidic, so f and g are simply functions under the monoid. But then I have a problem -- f is return for the List monad but (const 1) for the Integer type, and the Monoid doesn't have a return-equivalent, so I attempted to extend Monoid with one:
> class Monoid a => Monoidic a where > mlift :: x -> a > instance Num a => Monoidic (Sum a) where -- Monoidic (Sum Integer) didn't work either > mlift = const 1 > instance Monoidic [a] where > mlift = return
so I could rewrite my mkAdder with the obvious mappend and mlift functions:
> mkAdder :: (Monoidic b, Eq a) => a -> a -> (b -> b) > mkAdder y z = mappend (if y == z then mlift y else mappend (mlift y) (mlift z))
This path opened a whole can of (type-checking) worms, which is rather perplexing for me, as I used the implementation of MonadPlus' extension to Monad as a guide.
So, how do I rewrite my mkAdder, exploiting the fact that (Sum a) and [a] are monoids?
daucl...@gmail.com wrote: > Okay, so I have this generic factorization function, that given an > Integer returns the factors of that Integer in the desired manner: >> factors :: Integer -> (Integer -> Integer -> a -> a) -> a -> a
[snip]
> I don't know if it's the most elegant factorization algorithm in the > universe,
Factorization isn't trivial, there's quite some amount of maths one can use to get efficient answers for large numbers. For starters, having a source a primes helps. The article "The Genuine Sieve of Eratosthenes" by Melissa E. O'Neill might be interesting in this respect.
> Anyway, when I wish to see what the factors are, I call factors with:
>> showfactors :: Integer -> [Integer] >> showfactors x = factors x (\ y z ans -> if y == z then y:ans else y:z:ans) []
> and when I simply wish to know the number of factors, I call:
>> countfactors :: Integer -> Integer >> countfactors x = factors x (\y z ans -> (if y == z then 1 else 2) + ans) 0
If you don't need to squeeze out every last bit of speed, I'd recommend an approach with seperation of concerns: Just return all the factors as a list, and in a second stage, process them with groupBy, or whatever other function you need.
> The lambda expressions in these functions are generally adders for > their types, so I should be able to further generalize:
>> mkAdder :: Eq a => (a -> b) -> (b -> b -> b) -> a -> a -> (b -> b) >> mkAdder f g y z = g (if y == z then f y else g (f y) (f z))
> Which indeed I've done without problems:
>> showfactors x = factors x (mkAdder return mplus) [] >> countfactors x = factors x (mkAdder (const 1) (+)) 0 > But then I noticed the types I'm using ([Integer] and (Sum) Integer) > are Monoidic, so f and g are simply functions under the monoid.
IMHO it's not always a good idea to try to squeeze every monoid one recognizes into the Monoid typeclass. It's possible to have many different monoids over the same base type, and the extra effort required to make the type-based typeclass dispatch work with that often confuses the code more than making it clear.
Especially if folds or direct list processing are an alternative.
> But then I have a problem -- f is return for the List monad but > (const 1) for the Integer type, and the Monoid doesn't have a > return-equivalent, so I attempted to extend Monoid with one: >> class Monoid a => Monoidic a where >> mlift :: x -> a
One can immediately spot the trouble with that: There's a free type variable x which isn't mentioned in the type class, but appears only once in the overloaded function(s). What this says is that for any type x, you can inject a value of this type into the Monoid a. Obviously, this cannot work :-)
So what about
> class Monoid a => MonoidOver x a where > inject :: x -> a
> instance MonoidOver a [a] where > inject x = [x]
> instance Num a => MonoidOver a (Sum a) where > inject x = Sum x
Then you can write
> mkAdder :: (MonoidOver a b, Eq a) => a -> a -> (b -> b) > mkAdder y z = mappend > (if y == z then inject y else inject y `mappend` inject z)
Now if looking again at "inject", one can notice that it doesn't use the Monoid operations. So alternatively, one can define such a property independently. This also gets rid of the two parameters, and uses just the type constructor:
> class Injector m where > inject :: a -> m a
> instance Injector [] where > inject x = [x]
> instance Injector Sum where > inject x = Sum x > mkAdder :: (Monoid (m a), Injector m, Eq a) => a -> a -> (m a -> m a) > mkAdder y z = mappend > (if y == z then inject y else inject y `mappend` inject z) > This path opened a whole can of (type-checking) worms, which is rather > perplexing for me, as I used the implementation of MonadPlus' > extension to Monad as a guide.
You should be able to see the difference now, I hope :-)
|
