Monoids and extending class protocols
dauc...@gmail.com
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?
Thanks for the help!
Dirk Thierbach
> 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 :-)
- Dirk