July 21, 2007

Peano's Axioms Part III: Making use of Haskell's Powerful Polymorphism

This time, we'll be looking at making use of the polymorphic capabilties of Haskell's type system.

In Haskell, Polymorphism is provided via type variables. That is, you may have a function



foo :: (a -> b) -> [a] -> [b]



which requires a function of any type to any other type, and a list of elements of the first type, and it returns a list of elements of the second type. Most people call this function map, though it can represent others.

So in addition to getting the functions defined in the typeclass, we get all the prelude functions with variable type signatures.

But wait- theres more. When we define certain types of functions, we often want to limit the scope of the function to only operate on certain variables. Like defining an instance of an interface in Java, we can specify a "scope" (though thats an abuse of the term) for a type variable. As in the following:



foo2 :: Ord a => a -> a -> a



Here, we state that a must be an instance of the typeclass Ord (and by inheritance, an instance of Eq too.) So now we know that foo2 takes two comparable elements and returns a comparable element.

Polymorphism is nothing new to any language. However, I think that Haskell really has an advantage not in the area of semantics, which are pretty much uniform -- at least in the case of polymorphism. I think that Haskell's advantage is in the syntax of polymorphism. Type signatures are easily wonderfully simple ways to express polymorphism. Both this basic kind of polymorphism (called rank-1 polymorphism), as well as higher order polymorphism (rank-2, rank-3, rank-n).

The point of this post is to show the rich library of polymorphic functions which become available with just a few (I think we're up to 7, one derived, 6 implemented) type classes. This, as always, is a literate file, just cut and paste to a .lhs and run


$> ghci .lhs






> module Peano2 (Nat(..)) where
> import Peano
> import Data.Ratio




==============================================================
Continuing on which defining math in terms of Peano's axioms
==============================================================

Last time I noted that we'd be working on exp, div, mod, and some other
higher-level functions. I also mentioned that we "sortof" got exp for free, in
that

S(S(S(Z)))^k,

where k is an integer, works fine, but what if we k be a natural. we'll notice
readily that this will fail, with the error that theres no instance of
Integral Nat.

Why is that a problem? because (^) isn't in Num, its defined elsewhere, its
signature is



(^) :: (Num a, Integral b) => a -> b -> a



Okay, so now what we should do is define Nat to be an Integral Type. So, lets go
for it.


=======================================

so, for Integral, we need quot, rem, and toInteger. We have the last of these, from the last time. Its quot and rem that we need. So, how do we define these?

well, we know that quot and rem are (effectively) just mod and div, in fact, not having negative numbers means that they are exactly the same. Lets then realize that mod is just repeated subtraction until we hit modulus > remnant. further, we relize that div is just the same, but the count of times we subtracted till we met that condition.



> quotNat :: Nat -> Nat -> Nat
> quotNat k m
> | k == m = 1
> | k < m = 0
> | otherwise = 1 + (quotNat (k-m) m)

> remNat :: Nat -> Nat -> Nat
> remNat k m
> | k == m = 0
> | k < m = k
> | otherwise = remNat (k-m) m

> quotRemNat :: Nat -> Nat -> (Nat, Nat)
> quotRemNat k m = ((quotNat k m), (remNat k m))



now, we just instantiate integral



> instance Integral Nat where
> toInteger = ntoi
> quotRem = quotRemNat
> -- this fixes a problem that arises from Nats not having
> -- negative numbers defined.
> divMod = quotRemNat



=======================================

but now we need to instantiate Enum and Real, oh my. Lets go for Enum first.

Enum requires just toEnum and fromEnum, thats pretty easy, to and from enum are just to and from Integer, which we have.



> instance Enum Nat where
> toEnum = integerToNat
> fromEnum = natToInteger



Real is actually relatively easy, we're just projecting into a superset of the
Naturals, notably, the Rationals, so we do this simply by pushing the value
into a ratio of itself to 1, that is

toRational S(S(S(S(Z)))) ==> S(S(S(S(Z)))) % 1



> instance Real Nat where
> toRational k = (ntoi k) % 1


=======================================

Next time, we'll go for primes.

oh- and by the way, pushing Nat into Integral gave us lots of neat things, notably even/odd, gcd/lcm, the ability to do ranges like [(Z)..], and all the appropriate functions that go with that.

So far, I've spent about 1 hour making all this work, you can imagine how this speed could be useful if you have defined your problem as having certain properties. Type classes are an extremely powerful tool, which can help make your code both clean, as well as powerful. In one hour, I've managed to build up a simple bit of code, based on some fairly primitive axioms, and create a huge amount of powerful math around it.

Imagine if you could define these same relations around data? What if you were able to define strings as having properties of numbers, heres an Idea:

Imagine you have some strings, you can define the gcd of two strings as the least common substring of two strings. If you can sensically define the product of two strings, then you can get a concept of lcm as well. Granted, the may not be the best example. But you can just imagine the power you can push into your data by defining an arithmetic, (not even an algebra!) on them. Imagine creating an arithmetic of music (been done, sortof, check out Haskore) or pictures? I use
arithmetic,because what I'm implementing here is only a little peice of the power you can instill. _This_ is why Haskell is powerful. Not because its purely functional, not even because its lazy. It's the _math_ that makes Haskell capable of doing this. The type theory upon which Haskell rests makes Haskell powerful.

Remember, next time, Primes and Totients and Number Theory, and a datatype
representing the Integers,
Oh my!

26 comments:

Anonymous said...

I got this site from my buddy who shared with me regarding this web site and at the moment this time I am visiting this website and reading very
informative articles at this time.

Take a look at my site - la martina outlet

Anonymous said...

I love it when people get together and share views.
Great website, continue the good work!

Here is my website banken kredit ohne schufa
Also see my page :: kleinkredit ohne schufaauskunft

Anonymous said...

Saved as a favorite, I love your web site!


My page: all inclusive us virgin island vacations

Anonymous said...

I'm more than happy to discover this great site. I want to to thank you for ones time for this particularly wonderful read!! I definitely loved every little bit of it and I have you saved as a favorite to look at new information in your site.

Feel free to visit my web-site: kündigung private krankenkasse

Anonymous said...

You really make it appear really easy with your presentation however I find this matter
to be actually something that I believe I would never understand.
It kind of feels too complex and very wide for me.
I'm having a look forward in your next post, I will attempt to get the grasp of it!

Here is my site ... krankenversicherung selbständige vergleich

Anonymous said...

I am now not certain the place you're getting your info, however good topic. I needs to spend a while learning much more or figuring out more. Thanks for excellent info I used to be on the lookout for this info for my mission.

Also visit my web page fha home loan bad credit

Anonymous said...

Thanks in favor of sharing such a fastidious idea, piece of writing is fastidious, thats why
i have read it entirely

my page ... improve search engine ranking

Anonymous said...

Thanks in favor of sharing such a fastidious
idea, piece of writing is fastidious, thats why i have read it entirely

Also visit my website :: improve search engine ranking
my website - search engine optimisation experts

Anonymous said...

Hello, this weekend is pleasant designed for me, because this point in time i am reading this impressive informative piece of writing here at my
house.

Feel free to surf to my blog post aigner Outlet Online

Anonymous said...

Hi there! This post couldn't be written any better! Reading this post reminds me of my good old room mate! He always kept talking about this. I will forward this write-up to him. Pretty sure he will have a good read. Many thanks for sharing!

my web blog: compare home equity loan

Anonymous said...

There's certainly a great deal to know about this subject. I like all the points you have made.

Feel free to surf to my homepage ... student private krankenversicherung
my page > beitragssätze krankenkassen

Anonymous said...

When I originally commented I appear to have clicked the -Notify
me when new comments are added- checkbox and now each time a comment is added I get 4 emails with
the same comment. Is there an easy method you can remove me from
that service? Thank you!

my web-site :: Stay At home work opportunities

Anonymous said...

Can I simply say what a relief to discover someone who genuinely knows what they are talking about on the internet.
You certainly know how to bring an issue to light and make it important.

A lot more people should read this and understand this side of your story.
I was surprised that you are not more popular since you most certainly possess the
gift.

Review my site fed student loans

Anonymous said...

Usually I do not read post on blogs, however I wish to say that
this write-up very forced me to take a look at and do it!
Your writing taste has been surprised me. Thank you,
very nice post.

Here is my web-site ... http://www.xfire.com/blog/juanitafin/4581237

Anonymous said...

Hi to every body, it's my first pay a visit of this webpage; this web site contains amazing and truly excellent information in support of readers.

Here is my weblog - how can i refinance my home With bad credit
my website > home equity loan with bad credit

Anonymous said...

It's in reality a great and useful piece of info. I'm glad that
you shared this useful information with us. Please keep us up to date like this.
Thanks for sharing.

Take a look at my homepage - Benutzer:EarlJFJ – Science impuls

Anonymous said...

Hello, yes this article is truly pleasant and I have learned lot of things from
it regarding blogging. thanks.

Have a look at my web page; private krankenkasse kündigen

Anonymous said...

Nice post. I was checking constantly this blog and I am impressed!
Very useful info specially the last part :) I care for such information a lot.

I was seeking this particular information for a long time.
Thank you and best of luck.

Also visit my web site ... best web hosting services 2012
Also see my webpage: best hosting plan

Anonymous said...

I was able to find good advice from your blog posts.


Review my web-site :: seo specialist india

Anonymous said...

Thank you a bunch for sharing this with all people you actually realize what
you are talking approximately! Bookmarked. Please additionally talk over with my
website =). We could have a hyperlink change arrangement
among us

Feel free to visit my web blog :: top web hosting reviews

Anonymous said...

Howdy! This post couldn't be written any better! Looking through this post reminds me of my previous roommate! He always kept talking about this. I most certainly will forward this article to him. Pretty sure he's going to have a great read.
I appreciate you for sharing!

Here is my web site: kredite schufa
My web page - Schufa Eintrag

Anonymous said...

We are a group of volunteers and opening a new scheme in our community.
Your website offered us with helpful info to work on.
You've performed an impressive process and our entire neighborhood can be grateful to you.

Also visit my webpage: work from home san diego

Anonymous said...

We stumbled over here by a different web page and thought I
may as well check things out. I like what I see so i
am just following you. Look forward to going over your web page
repeatedly.

Feel free to visit my web blog: Home Loan For People With Bad Credit

Anonymous said...

Sweet blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I've been trying for a while but I never seem to get there! Cheers

Here is my blog post :: click through the next article

Anonymous said...


You have got remarkable information listed here. i SUCK i KNOW

Anonymous said...

Can I simply say what a comfort to find somebody that genuinely knows what they're discussing on the internet. You actually realize how to bring an issue to light and make it important. More and more people really need to look at this and understand this side of your story. I can't believe you
are not more popular because you certainly possess the gift.


My web blog - Read full report