Book recommendations on underlying theory
grimey
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
Paul Rubin
> 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":
grimey
> > 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
Shyamal Prasad
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
jon.gallagher.04
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.
Arved Sandstrom
[ 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
Benjamin L. Russell
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^
Benjamin L. Russell
<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.
Dirk Thierbach
> 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
grimey
> > > 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