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:

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

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 schufaauskunftSaved as a favorite, I love your web site!

My page: all inclusive us virgin island vacations

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

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

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

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

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 expertsHello, 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

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

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 krankenkassenWhen 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

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

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

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 creditIt'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

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

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 planI was able to find good advice from your blog posts.

Review my web-site :: seo specialist india

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

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 EintragWe 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

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

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

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

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

Post a Comment