56 views

Skip to first unread message

Jan 11, 2009, 6:11:40 PM1/11/09

to

I have been studying Haskell since the summer and have made some

strides in practical use. Unfortunately for me, the fact that I still

don't grasp much of the underlying theory tends to grate on me. So I

am thinking of "biting the bullet" and studying some of the underlying

theory, not necessarily to make me a better programmer, but simply for

the peace of mind that comes with understanding the tools you use.

(Although I suspect that does make one a better programmer in the

end).

strides in practical use. Unfortunately for me, the fact that I still

don't grasp much of the underlying theory tends to grate on me. So I

am thinking of "biting the bullet" and studying some of the underlying

theory, not necessarily to make me a better programmer, but simply for

the peace of mind that comes with understanding the tools you use.

(Although I suspect that does make one a better programmer in the

end).

I should probably say something about my math background.

I studied physics at the undergrad level: My math included: Diff &

Integ. Calc, Linear Algebra, Diff Eq, Advanced (Vector) Calc, Complex

Analysis. Although the Vector Calc class was particularly difficult

for me and sort of "took the wind out of my sails" and leaving me

adrift on the sea of mathematics for a long time. I always wanted to

continue on with more abstract math, like algebra and group theory, to

gain understanding of the beauty behind quantum physics; but for

various reasons, that didn't happen. Anyway years later I still use

Linear Algebra and Diff Eq quite frequently for work, and have a good

practical engineer's grasp of those topics. I use advanced calculus

less frequently and I use quaternions for very practical, non-

theoretical way for rotation sequences in 3D. I am an expert C/C++

programmer.

So I looked around for some books. Here are two that piqued my

interest:

Topics In Algebra, I.N. Herstein (various publishers) - Highly

recommended "classic", seems challenging but not too advanced for my

background, but VERY PRICEY for 2nd Edition ($145 for new paperback);

used first editions can be found for much cheaper - prompting the

question, "how much has Algebra changed since 1964?"

Lambda Calculus & Combinators, Hindley & Seldin (Cambridge) - I see

the name Hindley frequently while puzzling over a paragraph about

Haskell and type theory. The basic idea of the lambda calculus (i.e.

enough to understand how a Haskell or LISP lambda function is

evaluated and the idea of currying, so you can "simulate" functions

with multiple arguments) seems pretty straight forward to me - Still

I'm concerned I might be jumping in the deep end here.

I have always found the responses here thoughtful and helpful. Any

suggestions would be greatly appreciated.

-Chip Grandits

Jan 11, 2009, 6:34:53 PM1/11/09

to

grimey <Bould...@gmail.com> writes:

> I studied physics at the undergrad level: My math included: Diff &

> Integ. Calc, Linear Algebra, Diff Eq, Advanced (Vector) Calc, Complex

> Analysis. Although the Vector Calc class was particularly difficult

> for me and sort of "took the wind out of my sails" and leaving me

> adrift on the sea of mathematics for a long time.

> I studied physics at the undergrad level: My math included: Diff &

> Integ. Calc, Linear Algebra, Diff Eq, Advanced (Vector) Calc, Complex

> Analysis. Although the Vector Calc class was particularly difficult

> for me and sort of "took the wind out of my sails" and leaving me

> adrift on the sea of mathematics for a long time.

There is not much algebra there, especially if your linear algebra

class was of the usual kind found in engineering curricula, where you

mostly concentrate on how to solve linear systems and DE's.

> I always wanted to continue on with more abstract math, like algebra

> and group theory,

You should probably add some mathematical logic to this.

> So I looked around for some books. Here are two that piqued my

> interest:

> Topics In Algebra, I.N. Herstein (various publishers) - Highly

> recommended "classic", seems challenging but not too advanced for my

> background, but VERY PRICEY for 2nd Edition ($145 for new paperback);

> used first editions can be found for much cheaper - prompting the

> question, "how much has Algebra changed since 1964?"

This is one of the greatest books of all time, but that price is

ridiculous. Also, to be realistic, group theory isn't that relevant

to Haskell; logic and category theory are much more so. Finally,

there is so much good material online these days that buying dead tree

books should be considered a last resort.

http://en.wikibooks.org/wiki/Haskell/Category_theory

explains what category theory is about (not in any depth). I don't

know of a good online logic book at a really introductory level.

H. Schwichtenberg's lecture notes

http://www.mathematik.uni-muenchen.de/~schwicht/lectures/logic/ws03/ml.pdf

are very good but maybe

> Lambda Calculus & Combinators, Hindley & Seldin (Cambridge) - I see

> the name Hindley frequently while puzzling over a paragraph about

> Haskell and type theory.

I'm not familiar with this book but it doesn't really sound ideal.

I'd start with Harper's "Practical Foundatations for Programming

Languages":

Jan 11, 2009, 6:51:12 PM1/11/09

to

On Jan 11, 4:34 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:

> > grimey <BoulderC...@gmail.com> writes:

> > I always wanted to continue on with more abstract math, like algebra

> > and group theory,

>

> You should probably add some mathematical logic to this.

Thanks! I'll look into that. I took introductory logic from

Philosophy department but that was all.

> > So I looked around for some books. Here are two that piqued my

> > interest:

> > Topics In Algebra, I.N. Herstein (various publishers) - Highly

> > recommended "classic", seems challenging but not too advanced for my

> > background, but VERY PRICEY for 2nd Edition ($145 for new paperback);

> > used first editions can be found for much cheaper - prompting the

> > question, "how much has Algebra changed since 1964?"

>

> This is one of the greatest books of all time, but that price is

> ridiculous. Also, to be realistic, group theory isn't that relevant

> to Haskell; logic and category theory are much more so. Finally,

> there is so much good material online these days that buying dead tree

> books should be considered a last resort.

Well despite your subsequent disclaimer, the phrase "one of greatest

books of all time" keeps me interested.

Searching around used bookstores online via Alibris uncovered an

excellent-condition used hardcover 2nd Ed. for $30 - much more

reasonable. I went ahead and got it anyway.

> > Lambda Calculus & Combinators, Hindley & Seldin (Cambridge) - I see

> > the name Hindley frequently while puzzling over a paragraph about

> > Haskell and type theory.

>

> I'm not familiar with this book but it doesn't really sound ideal.

> I'd start with Harper's "Practical Foundatations for Programming

> Languages":

>

> http://www.cs.cmu.edu/~rwh/plbook/book.pdf

OK - I'll probably pass on that dead-tree edition until I read the

electronic document you recommended.

Thanks again for all your suggestions and the many links, this was

exactly the kind of response I was looking for.

-Chip

Jan 12, 2009, 12:50:03 AM1/12/09

to

>>>>> "grimey" == grimey <Bould...@gmail.com> writes:

grimey> I have been studying Haskell since the summer and have

grimey> made some strides in practical use. Unfortunately for me,

grimey> the fact that I still don't grasp much of the underlying

grimey> theory tends to grate on me. So I am thinking of "biting

grimey> the bullet" and studying some of the underlying theory,

grimey> not necessarily to make me a better programmer, but simply

grimey> for the peace of mind that comes with understanding the

grimey> tools you use. (Although I suspect that does make one a

grimey> better programmer in the end).

I suspect this may not be the theory that you were thinking of, but I

would personally recommend "The Haskell Road to Logic, Maths, and

Programming";

http://www.collegepublications.co.uk/computing/?00004

This book does not cover "practical" Haskell stuff like Monads and

type theory, but if you are looking for a good (re)introduction to

mathematics for computer science, and also a new look at Haskell this

should probably be on your list.

It's not easy reading; you will have to work through the problems to

really get the most value out of the text. But the problems are fun to

solve and very well chosen, the paperback is cheap, and I found the

text a truly pleasant way to revisit my math classes while improving

my appreciation for Haskell at the same time.

There are very few books I've enjoyed reading more than this one

("Funadmental Algorithms" as a teenager who only knew 8085 assembly

language many years ago, and then SICP some years later, come to

mind...) even though it's made me work at the excercises harder than

anything else I've probably ever read.

Cheers!

Shyamal

Jan 12, 2009, 2:05:44 PM1/12/09

to

Me too. I started on the Haskell Road, but had to stop when school

started up again. I actually got a copy of Introduction to functional

programming using Haskell very recently, and it seems to cover some of

the more subtleties of the language basics, but for the most part

covers the kind of typical programming in haskell tutorial stuff. So

I decided to struggle through two papers: one by Varmo Vene called

"Categorical Programming with Inductive and Coinductive types", and

also "Functional programming with overloading and higher-order

polymorphism" by Mark Jones. I made the mistake of learning Haskell

the way I learned java, which is fast. In Haskell, you can get things

done, sure, but the fun part is playing with ideas, and seeing such

elegance in the construction. So now, I am slowly going through these

papers with the kind of deliberate reading that I approach classes

like Real analysis with, and I think things are starting, very slowly

to click. I also found a paper which I may add to my list if I can

figure out the conventions used "functional programming with bananas

lenses, envelopes and barbed wire" by Erik Meijer, which seems to be

in the citation list of so many papers, that I feel, I had better.

started up again. I actually got a copy of Introduction to functional

programming using Haskell very recently, and it seems to cover some of

the more subtleties of the language basics, but for the most part

covers the kind of typical programming in haskell tutorial stuff. So

I decided to struggle through two papers: one by Varmo Vene called

"Categorical Programming with Inductive and Coinductive types", and

also "Functional programming with overloading and higher-order

polymorphism" by Mark Jones. I made the mistake of learning Haskell

the way I learned java, which is fast. In Haskell, you can get things

done, sure, but the fun part is playing with ideas, and seeing such

elegance in the construction. So now, I am slowly going through these

papers with the kind of deliberate reading that I approach classes

like Real analysis with, and I think things are starting, very slowly

to click. I also found a paper which I may add to my list if I can

figure out the conventions used "functional programming with bananas

lenses, envelopes and barbed wire" by Erik Meijer, which seems to be

in the citation list of so many papers, that I feel, I had better.

Jan 15, 2009, 8:36:50 PM1/15/09

to

On Sun, 11 Jan 2009 15:34:53 -0800, Paul Rubin wrote:

[ SNIP ]

> I'm not familiar with this book but it doesn't really sound ideal. I'd

> start with Harper's "Practical Foundatations for Programming Languages":

>

> http://www.cs.cmu.edu/~rwh/plbook/book.pdf

I downloaded this and it looks good to me (although I am pretty close to

being in the same boat as Chip as far as background goes...although I was

lucky enough to delve into really neat stuff in quantum mechanics, and an

excellent mathematical physics course, none of the physics math bears the

remotest resemblance to anything I see in the Harper book, nor in

Schwichtenberg's paper).

More out of curiosity than anything else, at what level would a bright CS

student expect to confront something like Harper's text?

AHS

Jan 16, 2009, 3:48:35 AM1/16/09

to

You may wish to read this related thread from the Haskell mailing

list:

[Haskell] Teach theory then Haskell as example

http://www.haskell.org/pipermail/haskell/2009-January/020929.html

(Be sure to read the related following three responses as well, since

they contain the bulk of the references.)

A possible issue with _The

Haskell Road to Logic, Maths and Programming_ (which I had actually

suggested in that thread), by Kees Doets and Jan van Eijck, is that it

isn't really related to category theory, which forms the theoretical

basis for Haskell. It's more of a book that covers the prerequisite

background for building sufficient mathematical sophistication for

understanding the kind of mathematics that appears in category theory,

even though the book isn't really related to category theory. In

particular, in the above-mentioned thread, Andrzej Jaworski responded

(see

http://www.haskell.org/pipermail/haskell/2009-January/020934.html) as

follows:

On Thu, 15 Jan 2009 05:12:19 +0100, "Andrzej Jaworski"

<him...@poczta.nom.pl> wrote:

>Doets and Eijck show good approach but their mathematics is too trivial (e.g.

>combinatorics should be presented via lattice theory like Rota taught). They also miss the boat

>presenting Haskell (no higher gear at all).

He also wrote:

>[T]here are many very good

>articles addressing specific issues of Haskell's theoretical foundations (e.g.

>http://www.cs.ut.ee/~varmo/papers/thesis.pdf). They however always assume more than they target to

>explain making student turn around them like a dog not knowing which ball to catch first.

I agree with this specific point: Many such articles/papers are

dependent on parts of other publications, which can sometimes either

be dependent on other parts of the first publication, or on parts of

other publications.

Regarding this point, one other reader responded in private that the

problem "comes from trying to use academic papers as textbooks, a

purpose for which they're not usually designed." As soon as I read

this, I thought, "Aha! Exactly: That is the problem." Such academic

papers usually target other researchers, but not beginner students of

Haskell or even category theory, so they often assume material not

covered.

One solution seems to be to focus on books specifically targeting

beginner students of Haskell, or at least beginner students of

category theory. The above-mentioned reader who responded in private

recommended the following lecture notes:

> Lambert Meertens' "Category Theory for Program Construction":

>

> http://www.kestrel.edu/home/people/meertens/diverse/ct4pc.ps.gz

> http://www.kestrel.edu/home/people/meertens/

(Note: It can be convenient to use http://www.ps2pdf.com/convert.htm

to convert the PostScript file above, once gunzipped, to PDF format.)

Apparently, this paper is based on the paper "A Gentle Introduction to

Category Theory - the calculational approach," by Maarten M. Fokkinga

(see http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.pdf).

Apparently, Meertens has designed the exercises so that each one is

designed to be doable if all the previous ones have been done, and

some parts of the main text depend on the exercises, so this book may

take a long time to read.

However, he has chosen not to use commutative diagrams. Every other

text on category theory that I have seen so far uses them in

abundance, but as Meertens explains, each one only relates to a

specific category, so they may be difficult to use in meta-categorical

discussion. Also, it is refreshing to see an alternative approach.

One other set of lecture notes that I have also found to be accessible

is the following:

Category Theory Lecture Notes for ESSLLI

by Michael Barr and Charles Wells

http://www.math.upatras.gr/~cdrossos/Docs/B-W-LectureNotes.pdf

The main problem with such lecture notes is their length: Meerten's

notes span 122 pages, and Barr and Wells' notes span 133 pages. It is

difficult to find time to read and do all the exercises in over a

hundred pages of category theory while working full-time.

(Further, in my case, it would be easier if the exercises could be

done on a keyboard, instead of on pencil and paper, because I usually

use my spare time after work hours during lunch or at work to study

category theory, and don't have much table space. However, writing

mathematical equations and proofs tends to be done much easier on

pencil and paper instead of on a keyboard. I live about two and a

half hours from work, and don't have enough time or desk space to do

them at home, even on weekends.)

One especially elementary book on category theory that I could

recommend, which unfortunately is apparently only available in a

dead-tree version, is the following:

Conceptual Mathematics: A First Introduction to Categories (Paperback)

by F. William Lawvere and Stephen Hoel Schanuel

http://www.amazon.com/Conceptual-Mathematics-First-Introduction-Categories/dp/0521478170

This book is reputed to be interesting even to non-mathematicians at a

philosophical level. I myself have purchased a copy.

If anybody knows any other books or lecture notes on category theory

that specifically target beginner students of Haskell or category

theory, I would be interested. In particular, I would be especially

interested in books for non-mathematicians that provide an elementary

discussion of category theory without requiring the student to use

pencil and paper to work through the exercises (requiring a keyboard

and editor to work through the exercises is acceptable).

-- Benjamin L. Russell

--

Benjamin L. Russell / DekuDekuplex at Yahoo dot com

http://dekudekuplex.wordpress.com/

Translator/Interpreter / Mobile: +011 81 80-3603-6725

"Furuike ya, kawazu tobikomu mizu no oto."

-- Matsuo Basho^

Jan 16, 2009, 4:29:11 AM1/16/09

to

On Fri, 16 Jan 2009 17:48:35 +0900, Benjamin L. Russell

<DekuDe...@Yahoo.com> wrote:

<DekuDe...@Yahoo.com> wrote:

>If anybody knows any other books or lecture notes on category theory

>that specifically target beginner students of Haskell or category

>theory, I would be interested. In particular, I would be especially

>interested in books for non-mathematicians that provide an elementary

>discussion of category theory without requiring the student to use

>pencil and paper to work through the exercises (requiring a keyboard

>and editor to work through the exercises is acceptable).

I forgot to mention that books with a philosophical approach, which

approach category theory similarly to the way _The Little Schemer_

(http://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0262560992/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1232097250&sr=8-1),

by Daniel P. Friedman and Matthias Felleisen, approaches Scheme, would

be especially interesting (but perhaps _Conceptual Mathematics: A

First Introduction to Categories, by F. William Lawvere and Stephen

Hoel Schanuel (see

http://www.amazon.com/Conceptual-Mathematics-First-Introduction-Categories/dp/0521478170),

already fulfills this role, since it discusses Galileo and the flight

of a bird as an example).

What would be especially interesting would be an introductory

storybook on category theory: a book similar to, say, Flatland (see

http://www.amazon.com/Flatland-Illustrated-Edwin-Abbot/dp/1406847771/ref=sr_1_2?ie=UTF8&s=books&qid=1232097520&sr=1-2),

by Edwin Abbott Abbott, or even Flatterland (see

http://www.amazon.com/Flatterland-Like-Flatland-Only-More/dp/073820675X/ref=sr_1_1?ie=UTF8&s=books&qid=1232097976&sr=1-1),

by Ian Stewart. These books would elevate category theory out of the

realm of dry equations into a story which would keep me awake with

suspense reading through the night.

Jan 21, 2009, 9:58:50 AM1/21/09

to

Arved Sandstrom <dce...@hotmail.com> wrote:

> On Sun, 11 Jan 2009 15:34:53 -0800, Paul Rubin wrote:

> On Sun, 11 Jan 2009 15:34:53 -0800, Paul Rubin wrote:

>> I'm not familiar with this book but it doesn't really sound ideal. I'd

>> start with Harper's "Practical Foundatations for Programming Languages":

>>

>> http://www.cs.cmu.edu/~rwh/plbook/book.pdf

> More out of curiosity than anything else, at what level would a bright CS

> student expect to confront something like Harper's text?

Browsing through it, I'd say that here in Germany the basic stuff in

the earlier chapters are at second year level, and the bulk is at

third and fourth year level, if you specialize in that subject.

That would probably correspond to master's courses at English-speaking

universities (students are older when they start studying in Germany,

so the level is a bit different).

YMMV, of course

- Dirk

Jan 22, 2009, 6:30:12 PM1/22/09

to

> > > Topics In Algebra, I.N. Herstein (various publishers) - Highly

> > > recommended "classic", seems challenging but not too advanced for my

> > > background, but VERY PRICEY for 2nd Edition ($145 for new paperback);

> > > used first editions can be found for much cheaper - prompting the

> > > question, "how much has Algebra changed since 1964?"

>

> > This is one of the greatest books of all time, but that price is

> > ridiculous. Also, to be realistic, group theory isn't that relevant

> > to Haskell; logic and category theory are much more so. Finally,

> > there is so much good material online these days that buying dead tree

> > books should be considered a last resort.

>

> Well despite your subsequent disclaimer, the phrase "one of greatest

> books of all time" keeps me interested.

> Searching around used bookstores online via Alibris uncovered an

> excellent-condition used hardcover 2nd Ed. for $30 - much more

> reasonable. I went ahead and got it anyway.

For the record, I actually bought _Abstract Algebra_ not _Topics In

Algebra_.

_Topics In Algebra_ is a pricey volume wherever I looked.

_Abstract Algebra_ is probably a bit more basic, and sufficient for my

purposes

It's not too long, although I find you cannot read it like a dime

store novel;

It takes time for the concepts to sink in.

Nonetheless you can get through it pretty quick if you resist the

temptation to

try the hard problems in the exercises.

Very much helped my understanding of Algebraic Data Type and the

concept of Homomorphism.

I get "slightly less lost" when reading about the theory behind

Haskell.

-Chip

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu