Path: g2news1.google.com!postnews.google.com!t54g2000hsg.googlegroups.com!not-for-mail
From: daucl...@gmail.com
Newsgroups: comp.lang.haskell
Subject: Monoids and extending class protocols
Date: Sat, 24 May 2008 21:53:43 -0700 (PDT)
Organization: http://groups.google.com
Lines: 67
Message-ID: <12ccc61e-5495-44c7-a3a9-d8482ba660b6@t54g2000hsg.googlegroups.com>
NNTP-Posting-Host: 72.196.240.248
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1211691223 12269 127.0.0.1 (25 May 2008 04:53:43 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 25 May 2008 04:53:43 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: t54g2000hsg.googlegroups.com; posting-host=72.196.240.248; 
	posting-account=5zctWQoAAAApbE9IYP78UiU8GW_2gnlE
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X; en-US; 
	rv:1.8.1.14) Gecko/20080404 Firefox/2.0.0.14,gzip(gfe),gzip(gfe)

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?

Thanks for the help!