https://wiki.haskell.org/api.php?action=feedcontributions&user=Felix+stegerman&feedformat=atomHaskellWiki - User contributions [en]2022-08-16T01:30:58ZUser contributionsMediaWiki 1.31.7https://wiki.haskell.org/index.php?title=The_Fibonacci_sequence&diff=24125The Fibonacci sequence2008-11-19T08:20:45Z<p>Felix stegerman: /* With scanl */ fixed definition of fibs using scanl: 0 -> 1</p>
<hr />
<div>Implementing the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci sequence] is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.<br />
<br />
== Naive definition ==<br />
<br />
The standard definition can be expressed directly:<br />
<haskell><br />
fib 0 = 0<br />
fib 1 = 1<br />
fib n = fib (n-1) + fib (n-2)<br />
</haskell><br />
This implementation requires ''O(fib n)'' additions.<br />
<br />
== Linear operation implementations ==<br />
<br />
=== A fairly fast version, using some identities ===<br />
<br />
<haskell><br />
fib 0 = 0<br />
fib 1 = 1<br />
fib n | even n = f1 * (f1 + 2 * f2)<br />
| n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2<br />
| otherwise = (2 * f1 + f2) * (2 * f1 - f2) - 2<br />
where k = n `div` 2<br />
f1 = fib k<br />
f2 = fib (k-1)<br />
</haskell><br />
<br />
=== Using the infinite list of Fibonacci numbers ===<br />
<br />
One can compute the first ''n'' Fibonacci numbers with ''O(n)'' additions.<br />
If <hask>fibs</hask> is the infinite list of Fibonacci numbers, one can define<br />
<haskell><br />
fib n = fibs!!n<br />
</haskell><br />
<br />
==== Canonical zipWith implementation ====<br />
<br />
<haskell><br />
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)<br />
</haskell><br />
<br />
==== With scanl ====<br />
<br />
<haskell><br />
fibs = scanl (+) 0 (1:fibs)<br />
fibs = 0 : scanl (+) 1 fibs<br />
</haskell><br />
The recursion can be replaced with <hask>fix</hask>:<br />
<haskell><br />
fibs = fix (scanl (+) 0 . (1:))<br />
fibs = fix ((0:) . scanl (+) 1)<br />
</haskell><br />
<br />
==== With unfoldr ====<br />
<br />
<haskell><br />
fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)<br />
</haskell><br />
<br />
==== With iterate ====<br />
<br />
<haskell><br />
fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)<br />
</haskell><br />
<br />
== Logarithmic operation implementations ==<br />
<br />
=== Using 2x2 matrices ===<br />
<br />
The argument of <hask>iterate</hask> above is a [http://en.wikipedia.org/wiki/Linear_map linear transformation],<br />
so we can represent it as matrix and compute the ''n''th power of this matrix with ''O(log n)'' multiplications and additions.<br />
For example, using the [[Prelude_extensions#Matrices|simple matrix implementation]] in [[Prelude extensions]],<br />
<haskell><br />
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])<br />
</haskell><br />
This technique works for any linear recurrence.<br />
<br />
=== Another fast fib ===<br />
<br />
(Assumes that the sequence starts with 1.)<br />
<haskell><br />
fib = fst . fib2<br />
<br />
-- | Return (fib n, fib (n + 1))<br />
fib2 0 = (1, 1)<br />
fib2 1 = (1, 2)<br />
fib2 n<br />
| even n = (a*a + b*b, c*c - a*a)<br />
| otherwise = (c*c - a*a, b*b + c*c)<br />
where (a,b) = fib2 (n `div` 2 - 1)<br />
c = a + b<br />
</haskell><br />
<br />
=== Fastest Fib in the West ===<br />
<br />
This was contributed by [http://www.haskell.org/pipermail/haskell-cafe/2005-January/008839.html wli]<br />
(It assumes that the sequence starts with 1.)<br />
<br />
<haskell><br />
import Data.List<br />
<br />
fib1 n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n<br />
where<br />
unfoldl f x = case f x of<br />
Nothing -> []<br />
Just (u, v) -> unfoldl f v ++ [u]<br />
<br />
divs 0 = Nothing<br />
divs k = Just (uncurry (flip (,)) (k `divMod` 2))<br />
<br />
fib' (f, g) p<br />
| p = (f*(f+2*g), f^2 + g^2)<br />
| otherwise = (f^2+g^2, g*(2*f-g))<br />
</haskell><br />
<br />
An even faster version, given later by wli on the [[IRC channel]].<br />
<haskell><br />
import Data.List<br />
import Data.Bits<br />
<br />
fib :: Int -> Integer<br />
fib n = snd . foldl' fib' (1, 0) $ dropWhile not $<br />
[testBit n k | k <- let s = bitSize n in [s-1,s-2..0]]<br />
where<br />
fib' (f, g) p<br />
| p = (f*(f+2*g), ss)<br />
| otherwise = (ss, g*(2*f-g))<br />
where ss = f*f+g*g<br />
</haskell><br />
<br />
== Constant-time implementations ==<br />
<br />
The Fibonacci numbers can be computed in constant time using Binet's formula.<br />
However, that only works well within the range of floating-point numbers<br />
available on your platform. Implementing Binet's formula in such a way that it computes exact results for all integers generally doesn't result in a terribly efficient implementation when compared to the programs above which use a logarithmic number of operations (and work in linear time).<br />
<br />
Beyond that, you can use [http://haskell.org/haskellwiki/Applications_and_libraries/Mathematics#Real_and_rational_numbers unlimited-precision floating-point numbers],<br />
but the result will probably not be any better than the [[#Log-time_implementations|log-time implementations]] above.<br />
<br />
=== Using Binet's formula ===<br />
<br />
<haskell><br />
fib n = round $ phi ** fromIntegral n / sq5<br />
where<br />
sq5 = sqrt 5 :: Double<br />
phi = (1 + sq5) / 2<br />
</haskell><br />
<br />
== See also == <br />
<br />
* [http://cgi.cse.unsw.edu.au/~dons/blog/2007/11/29 Naive parallel, multicore version]<br />
* [[Fibonacci primes in parallel]]<br />
* [http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 Discussion at haskell cafe]<br />
* [http://www.cubbi.org/serious/fibonacci/haskell.html Some other nice solutions]<br />
* In [http://projecteuler.net/ Project Euler], some of the problems involve Fibonacci numbers. There are some solutions in Haskell ('''Spoiler Warning:''' Do not look at solutions to Project Euler problems until you have solved the problems on your own.):<br />
** [[Euler_problems/1_to_10#Problem_2|Problem 2]]<br />
** [[Euler_problems/21_to_30#Problem_25|Problem 25]]<br />
** [[Euler_problems/101_to_110#Problem_104|Problem 104]]<br />
** [[Euler_problems/131_to_140#Problem_137|Problem 137]]<br />
<br />
[[Category:Code]]</div>Felix stegermanhttps://wiki.haskell.org/index.php?title=Books&diff=7068Books2006-10-16T09:33:36Z<p>Felix stegerman: /* Language and library definition */</p>
<hr />
<div>Books and tutorials covering many aspects of Haskell.<br />
<br />
=Language and library definition=<br />
<br />
<DL><br />
<DT>Simon Peyton Jones: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521826144 "Haskell 98 language and libraries: the Revised Report"], Cambridge University Press, 2003, Hardback, 272 pages, ISBN: 0521826144, £45.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library specification]]<br />
</DT><br />
</DL><br />
<br />
= Textbooks=<br />
<br />
<DL><br />
<DT>Paul Hudak: [http://www.haskell.org/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN:<br />
0521644089, Hardback $74.95, ISBN: 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of domain specific languages, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's Web Site contains source files for all programs in the<br />
text, as well as the graphics libraries to run them under Windows and<br />
Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
</blockquote><br />
<DT>Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN<br />
0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN: 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<DT>Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN<br />
0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A website gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt> Cordelia Hall and John O'Donnell: [http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/ <em>Discrete Mathematics Using a Computer</em>],<br />
Springer, 2000, 360 pages. ISBN 1-85233-089-9.<br />
<blockquote><br />
<b>Book description:</b><br><br />
This book introduces the main topics of discrete mathematics with a strong emphasis on<br />
applications to computer science. It uses computer programs to implement and illustrate<br />
the mathematical ideas, helping the reader to gain a concrete understanding of the<br />
abstract mathematics. The programs are also useful for practical calculations, and they<br />
can serve as a foundation for larger software packages. <br />
<br />
Designed for first and second year undergraduate students, the book is also ideally suited<br />
to self-study. No prior knowledge of functional programming is required; the book and<br />
the online documentation provide everything you will need. <br />
</blockquote><br />
<br />
<dt>Kees Doets and Jan van Eijck: [http://www.cwi.nl/~jve/HR <em>The Haskell Road to Logic, Maths and Programming</em>]. King's College Publications, London, 2004. ISBN 0-9543006-9-6 (14.00 pounds, $25.00).<br />
<blockquote><br />
<b>Book description:</b><br><br />
The purpose of this book is to teach logic and mathematical reasoning<br />
in practice, and to connect logical reasoning with computer<br />
programming. Throughout the text, abstract concepts are linked to<br />
concrete representations in Haskell. Everything one has to know about<br />
programming in Haskell to understand the examples in the book is<br />
explained as we go along, but we do not cover every aspect of the<br />
language. Haskell is a marvelous demonstration tool for logic and<br />
maths because its functional character allows implementations to<br />
remain very close to the concepts that get implemented, while the<br />
laziness permits smooth handling of infinite data structures.<br />
<br />
We do not assume that our readers have previous experience with either<br />
programming or construction of formal proofs. We do assume previous<br />
acquaintance with mathematical notation, at the level of secondary<br />
school mathematics. Wherever necessary, we will recall relevant <br />
facts. Everything one needs to know about mathematical<br />
reasoning or programming is explained as we go along. We do assume<br />
that our readers are able to retrieve software from the Internet and<br />
install it, and that they know how to use an editor for constructing<br />
program texts.<br />
<br />
After having worked through the material in the book, i.e., after<br />
having digested the text and having carried out a substantial number<br />
of the exercises, the reader will be able to write interesting<br />
programs, reason about their correctness, and document them in a clear<br />
fashion. The reader will also have learned how to set up mathematical<br />
proofs in a structured way, and how to read and digest mathematical<br />
proofs written by others.<br />
<br />
The book can be used as a course textbook, but since it comes with<br />
solutions to all exercises (electronically available from the authors<br />
upon request) it is also well suited for private study. The source<br />
code of all programs discussed in the text, a list of errata, <br />
further relevant material and an email link to the authors<br />
can be found [http://www.cwi.nl/~jve/HR here].<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: <em>Implementation of Functional Programming Language</em>,Prentice-Hall, 1987. ISBN 0134533259.<br />
<br />
<dt>Simon Peyton Jones, David Lester: <em>Implementing Functional Languages</em>, 1992.<br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
</blockquote><br />
<br />
<dt>Simon Thompson: <em>Type Theory and Functional Programming</em>, Addison-Wesley, 1991. ISBN 0-201-41667-0.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
</DL><br />
<br />
=Tutorials=<br />
<br />
==Introductions to Haskell==<br />
<br />
;[http://www.haskell.org/tutorial/ A Gentle Introduction to Haskell] <br />
:By Paul Hudak, John Peterson, and Joseph H. Fasel. The title is a bit misleading. Some knowledge of another functional programming language is expected. The emphasis is on the type system and those features which are really new in Haskell (compared to other functional programming languages). A classic.<br />
<br />
;[http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf Yet Another Haskell Tutorial]<br />
:By Hal Daume III et al. A recommended tutorial for Haskell that is still under construction but covers already much ground. Also a classic text.<br />
<br />
;[http://www.haskell.org/~pairwise/intro/intro.html Haskell Tutorial for C Programmers]<br />
:By Eric Etheridge. From the intro: "This tutorial assumes that the reader is familiar with C/C++, Python, Java, or Pascal. I am writing for you because it seems that no other tutorial was written to help students overcome the difficulty of moving from C/C++, Java, and the like to Haskell."<br />
<br />
;[http://www-106.ibm.com/developerworks/edu/os-dw-linuxhask-i.html Beginning Haskell] <br />
:From IBM developerWorks. This tutorial targets programmers of imperative languages wanting to learn about functional programming in the language Haskell. If you have programmed in languages such as C, Pascal, Fortran, C++, Java, Cobol, Ada, Perl, TCL, REXX, JavaScript, Visual Basic, or many others, you have been using an imperative paradigm. This tutorial provides a gentle introduction to the paradigm of functional programming, with specific illustrations in the Haskell 98 language. (Free registration required.)<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/teaching/Hskurs_toc.html Online Haskell Course] <br />
:By Ralf Hinze (in German).<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/tutorials.html Tutorial Papers in Functional Programming].<br />
:A collection of links to other Haskell tutorials, from John Hughes.<br />
<br />
;[http://www.cs.ou.edu/cs1323h/textbook/haskell.shtml Two Dozen Short Lessons in Haskell] <br />
:By Rex Page. A draft of a textbook on functional programming, available by ftp. It calls for active participation from readers by omitting material at certain points and asking the reader to attempt to fill in the missing information based on knowledge they have already acquired. The missing information is then supplied on the reverse side of the page. <br />
<br />
;[http://pleac.sourceforge.net/pleac_haskell/t1.html PLEAC-Haskell]<br />
:Following the Perl Cookbook (by Tom Christiansen and Nathan Torkington, published by O'Reilly) spirit, the PLEAC Project aims to gather fans of programming, in order to implement the solutions in other programming languages.<br />
<br />
;[ftp://ftp.geoinfo.tuwien.ac.at/navratil/HaskellTutorial.pdf Haskell-Tutorial] <br />
:By Damir Medak and Gerhard Navratil. The fundamentals of functional languages for beginners. <br />
<br />
;[http://en.wikibooks.org/wiki/Haskell Programming Haskell Wikibook] <br />
:A communal effort by several authors to produce the definitive Haskell textbook. Its very much a work in progress at the moment, and contributions are welcome.<br />
<br />
;[http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung Video Lectures] <br />
:Lectures (in English) by Jürgen Giesl. About 30 hours in total, and great for learning Haskell. The lectures are 2005-SS-FP.V01 through 2005-SS-FP.V26. Videos 2005-SS-FP.U01 through 2005-SS-FP.U11 are exercise answer sessions, so you probably don't want those.<br />
<br />
;[http://www.cs.utoronto.ca/~trebla/fp/ Albert's Functional Programming Course] <br />
:A 15 lesson introduction to most aspects of Haskell.<br />
<br />
;[http://www.iceteks.com/articles.php/haskell/1 Introduction to Haskell]<br />
:By Chris Dutton, An "attempt to bring the ideas of functional programming to the masses here, and an experiment in finding ways to make it easy and interesting to follow".<br />
<br />
;[http://www.csc.depauw.edu/~bhoward/courses/0203Spring/csc122/haskintro/ An Introduction to Haskell]<br />
:A brief introduction, by Brian Howard.<br />
<br />
;[http://web.syntaxpolice.org/lectures/haskellTalk/slides/index.html Introduction to Haskell]<br />
:By Isaac Jones (2003).<br />
<br />
;[http://www.linuxjournal.com/article/9096 Translating Haskell into English]<br />
:By Shannon Behrens, a glimpse of the Zen of Haskell, without requiring that they already be Haskell converts.<br />
<br />
;[http://www.thaiopensource.com/relaxng/derivative.html An algorithm for RELAX NG validation]<br />
:by James Clark (of RELAX NG fame). Describes an algorithm for validating an XML document against a RELAX NG schema, uses Haskell to describe the algorithm. The algorithm in Haskell and Java is then [http://www.donhopkins.com/drupal/node/117 discussed here].<br />
<br />
===Real world tutorials===<br />
<br />
These tutorials examine using Haskell to writing complex real-wrold applications<br />
<br />
;[[Hitchhikers Guide to the Haskell]]<br />
: Tutorial for C/Java/OCaml/... programers by Dmitry Astapov. From the intro: "This text intends to introduce the reader to the practical aspects of Haskell from the very beginning (plans for the first chapters include: I/O, darcs, Parsec, QuickCheck, profiling and debugging, to mention a few)".<br />
<br />
;[http://haskell.org/haskellwiki/IO_inside Haskell I/O inside: Down the Rabbit's Hole]<br />
:By Bulat Ziganshin (2006), a comprehensive tutorial on using IO monad.<br />
<br />
;[http://research.microsoft.com/%7Esimonpj/Papers/marktoberdorf Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell]<br />
:Simon Peyton Jones. Presented at the 2000 Marktoberdorf Summer School. In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96. The standard reference for monadic IO in GHC/Haskell. <br><strong>Abstract:</strong>Functional programming may be beautiful, but to write real applications we must grapple with awkward real-world issues: input/output, robustness, concurrency, and interfacing to programs written in other languages.<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/docs/ffi.html A Guide to Haskell's Foreign Function Interface]<br />
:A guide to using the foreign function interface extension, using the rich set of functions in the Foreign libraries, design issues, and FFI preprocessors.<br />
<br />
===Older tutorials===<br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/manuals/haskeller.dvi.gz The Little Haskeller] <br />
:By Cordelia Hall and John Hughes. 9. November 1993, 26 pages. An introduction using the Chalmers Haskell B interpreter (hbi). Beware that it relies very much on the user interface of hbi which is quite different for other Haskell systems, and the tutorials cover Haskell 1.2 , not Haskell 98.<br />
<br />
;[http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Functional Programming]<br />
:By Jeroen Fokker, 1995. (153 pages, 600 KB). Textbook for learning functional programming with Gofer (an older implementation of Haskell). Here without Chapters&nbsp;6 and&nbsp;7.<br />
<br />
;[http://wiki.python.org/moin/PythonVsHaskell Comparing Haskell and Python]<br />
:A short overview of similarities and differences between Haskell and Python.<br />
<br />
;[http://mult.ifario.us/articles/2006/10/11/first-steps-with-haskell-for-web-applications Haskell + FastCGI versus Ruby on Rails]<br />
:A short blog entry documenting performance results with ruby on rails and Haskell with fastcgi<br />
<br />
==Reference material==<br />
<br />
;[http://undergraduate.csse.uwa.edu.au/units/230.301/lectureNotes/tourofprelude.html A Tour of the Haskell Prelude (basic functions)] <br />
:By Bernie Pope and Arjan van IJzendoorn.<br />
<br />
;[http://cs.anu.edu.au/Student/comp1100/haskell/tourofsyntax.html Tour of the Haskell Syntax] <br />
:By Arjan van IJzendoorn.<br />
<br />
;[http://zvon.org/other/haskell/Outputglobal/index.html Haskell Reference] <br />
:By Miloslav Nic.<br />
<br />
;[http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions]<br />
:By Henk-Jan van Tuyl.<br />
<br />
;[http://www.cse.unsw.edu.au/~en1000/haskell/inbuilt.html Useful Haskell functions]<br />
:An explanation for beginners of many Haskell functions that are predefined in the Haskell Prelude.<br />
<br />
;[http://haskell.org/ghc/docs/latest/html/libraries/ Documentation for the standard libraries]<br />
:Complete documentation of the standard Haskell libraries.<br />
<br />
;[http://www.haskell.org/haskellwiki/Category:Idioms Haskell idioms]<br />
:A collection of articles describing some common Haskell idioms. Often quite advanced.<br />
<br />
;[http://www.haskell.org/haskellwiki/Blow_your_mind Useful idioms]<br />
:A collection of short, useful Haskell idioms.<br />
<br />
;[http://www.haskell.org/haskellwiki/Programming_guidelines Programming guidelines]<br />
:Some Haskell programming and style conventions.<br />
<br />
;[http://haskell.org/haskellwiki/Category:Tutorials A growing list of Haskell tutorials on a diverse range of topics]<br />
:Available on this wiki<br />
<br />
== Motivation for using Haskell ==<br />
<br />
;[http://www.md.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters] <br />
:By [http://www.md.chalmers.se/~rjmh/ John Hughes], The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.<BR> Exposes the advantages of functional programming languages. Demonstrates how higher-order functions and lazy evaluation enable new forms of modularization of programs.<br />
<br />
;[[Why Haskell matters]] <br />
:Discussion of the advantages of using Haskell in particular. An excellent article.<br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/224/index.html Higher-order + Polymorphic = Reusable] <br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. Unpublished, May 1997.<BR> <STRONG>Abstract:</STRONG> This paper explores how certain ideas in object oriented languages have their correspondents in functional languages. In particular we look at the analogue of the iterators of the C++ standard template library. We also give an example of the use of constructor classes which feature in Haskell 1.3 and Gofer.<br />
<br />
;[http://www-128.ibm.com/developerworks/java/library/j-cb07186.html Explore functional programming with Haskell]<br />
:Introduction to the benefits of functional programming in Haskell by Bruce Tate.<br />
<br />
==Analysis and design methods==<br />
<br />
See [[Analysis and design]].<br />
<br />
== Teaching Haskell == <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/208/index.html Where do I begin? A problem solving approach to teaching functional programming]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. In Krzysztof Apt, Pieter Hartel, and Paul Klint, editors, First International Conference on Declarative Programming Languages in Education. Springer-Verlag, September 1997. <br> <STRONG>Abstract:</STRONG> This paper introduces a problem solving method for teaching functional programming, based on Polya's `How To Solve It', an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study. <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1995/214/index.html Functional programming through the curriculum]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]and Steve Hill. In Pieter H. Hartel and Rinus Plasmeijer, editors, Functional Programming Languages in Education, LNCS 1022, pages 85-102. Springer-Verlag, December 1995. <br> <STRONG>Abstract:</STRONG> This paper discusses our experience in using a functional language in topics across the computer science curriculum. After examining the arguments for taking a functional approach, we look in detail at four case studies from different areas: programming language semantics, machine architectures, graphics and formal languages. <br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/CK02a.html The Risks and Benefits of Teaching Purely Functional Programming in First Year]<br />
:By [http://www.cse.unsw.edu.au/~chak Manuel M. T. Chakravarty] and [http://www.cse.unsw.edu.au/~keller Gabriele Keller]. Journal of Functional Programming 14(1), pp 113-123, 2004. An earlier version of this paper was presented at Functional and Declarative Programming in Education (FDPE02). <br> <strong>Abstract</strong> We argue that teaching purely functional programming as such in freshman courses is detrimental to both the curriculum as well as to promoting the paradigm. Instead, we need to focus on the more general aims of teaching elementary techniques of programming and essential concepts of computing. We support this viewpoint with experience gained during several semesters of teaching large first-year classes (up to 600 students) in Haskell. These classes consisted of computer science students as well as students from other disciplines. We have systematically gathered student feedback by conducting surveys after each semester. This article contributes an approach to the use of modern functional<br />
languages in first year courses and, based on this, advocates the use of functional languages in this setting.<br />
<br />
==Using monads==<br />
<br />
See also the [[Monad]] HaskellWiki page with another list of tutorials (should this redundancy be removed? -- not sure...)<br />
<br />
;[http://www.nomaware.com/monads/html/ All About Monads] <br />
:By Jeff Newbern. This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. <br />
<br />
;[http://db.ewi.utwente.nl/Publications/PaperStore/db-utwente-0000003696.pdf The Haskell Programmer's Guide to the IO Monad - Don't Panic.] <br />
:Stefan Klinger. This report scratches the surface of category theory, an abstract branch of algebra, just deep enough to find the monad structure. It seems well written.<br />
<br />
;[http://www-users.mat.uni.torun.pl/~fly/materialy/fp/haskell-doc/Monads.html What the hell are Monads?] <br />
:By Noel Winstanley. A basic introduction to monads, monadic programming and IO. This introduction is presented by means of examples rather than theory, and assumes a little knowledge of Haskell. <br />
<br />
;[http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm Monads for the Working Haskell Programmer -- a short tutorial]<br />
:By Theodore Norvell. <br />
<br />
;[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.)]<br />
:A short tutorial on monads, introduced from a pragmatic approach, with less category theory references <br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/monads.html Systematic Design of Monads]<br />
:John Hughes & Magnus Carlsson. Many useful monads can be designed in a systematic way, by successively adding facilities to a trivial monad. The capabilities that can be added in this way include state, exceptions, backtracking, and output. Here we give a brief description of the trivial monad, each kind of extension, and sketches of some interesting operations that each monad supports.<br />
<br />
;[[Meet Bob The Monadic Lover]]<br />
:by Andrea Rossato. A by-the-author-supposed-to-be funny and short introduction to Monads, with code but without any reference to category theory: what monads look like and what they are useful for, from the perspective of a ... lover. (There is also the slightly more serious [[The Monadic Way]] by the same author.)<br />
<br />
;[http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html Monad Transformers Step by Step]<br />
:Martin Grabm&uuml;ller: a small tutorial on using monad transformers. In contrast to others found on the web, it concentrates on using them, not on their implementation.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
==Using arrows==<br />
<br />
This topic has an own HaskellWiki page: [[Arrow]].<br />
<br />
;[http://www.haskell.org/arrows/ Arrows: A General Interface to Computation]<br />
:Ross Paterson's page on arrows.<br />
<br />
HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows].<br />
<br />
Monad.Reader's [http://www.haskell.org/tmrwiki/ArrowsIntroduction ArrowsIntroduction] article.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
== Attribute grammars ==<br />
<br />
This topic has an own HakellWiki page: [[Attribute grammar]]<br />
<br />
== Categorical programming ==<br />
<br />
See its own HaskellWiki page: [[Category theory#Categorical programming]].<br />
<br />
== Data structures ==<br />
<br />
;[http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.cs.columbia.edu/~cdo/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
<br />
See [[Research papers/Data structures]]<br />
<br />
==Schools on advanced funtional programming==<br />
<br />
<EM>Advanced Functional Programming</EM>, First International Spring<br />
School on Advanced Functional Programming Techniques, Bastad, Sweden, LNCS 925, Springer-Verlag, 1995 (editors: J. Jeuring, E. Meijer).<br />
*<EM>Functional Parsers</EM> by Jeroen Fokker, p.&nbsp;1-23.<br />
*<EM>Monads for functional programming</EM> by Philip Wadler, p.&nbsp;24-52.<br />
*<EM>The Design of a Pretty-printing Library</EM> by John Hughes, p.&nbsp;52-96.<br />
*<EM>Functional Programming with Overloading and Higher-Order Polymorphism</EM>, Mark P. Jones, p.&nbsp;97-136.<br />
*<EM>Programming with Fudgets</EM> by Thomas Hallgren and Magnus Carlsson, p.&nbsp;137-182.<br />
*<EM>Constructing Medium Sized Efficient Functional Programs in Clean</EM> by Marko C.J.D. van Eekelen and Rinus J. Plasmeijer, p.&nbsp;183-227.<br />
*<EM>Merging Monads and Folds for Functional Programming</EM> by Erik Meijer and Johan Jeuring, p.&nbsp;228-266.<br />
*<EM>Programming with Algebras</EM> by Richard B. Kieburtz and Jeffrey Lewis, p.&nbsp;267-307.<br />
*<EM>Graph Algorithms with a Functional Flavour</EM> by John Launchbury, p.&nbsp;308-331.<br />
<br />
[http://www.cse.ogi.edu/PacSoft/conf/summerschool96.html <EM>Advanced Functional Programming</EM>], Second International Summer School on Advanced Functional Programming Techniques, Evergreen State College, WA, USA, LNCS 1126, Springer-Verlag, 1996 (editors: J. Launchbury, E. Meijer, T. Sheard).<br />
*<EM>Composing the User Interface with Haggis</EM> by Sigbjorn Finne and Simon Peyton Jones, p.&nbsp;1-37.<br />
*<EM>Haskore Music Tutorial</EM> by Paul Hudak, p.&nbsp;38-67.<br />
*<EM>Polytypic Programming</EM> by Johan Jeuring and Patrick Jansson, p.&nbsp;68-114.<br />
*<EM>Implementing Threads in Standard ML</EM> by Peter Lee, p.&nbsp;115-130.<br />
*<EM>Functional Data Structures</EM> by Chris Okasaki, p.&nbsp;131-158.<br />
*<EM>Heap Profiling for Space Efficiency</EM> by Colin Runciman and Niklas R&ouml;jemo, p.&nbsp;159-183.<br />
*<EM&gt;Deterministic, Error-Correcting Combinator Parsers</EM> by S. Doaitse Swierstra and Luc Duponcheel, p.&nbsp;184-207.<br />
*<EM>Essentials of Standard ML Modules</EM> by Mads Tofte, p.&nbsp;208-238.<br />
<br />
[http://alfa.di.uminho.pt/~afp98/ Advanced Functional Programming, Third International School, AFP'98], <br />
in Braga, Portugal from 12th to 19th September 1998, LNCS 1608, Springer-Verlag, 1999<br />
(editors: D. Swierstra, P. Henriques and J. Oliveira).<BR><br />
All lecture notes and further material are available from the web site.<br />
<br />
= Foundations =<br />
<br />
Some books and links listed here can be found also in the articles of ''Theoretical foundations'' category<br />
* see [[Mathematics]]<br />
* or browse ''Theoretical foundations'' among [[Special:Categories]].<br />
<br />
;[http://www.dcs.qmul.ac.uk/~pt/Practical_Foundations/ Practical Foundations of Mathematics]<br />
:Paul Taylor. Cambridge University Press, ISBN: 0-521-63107-6, xii+576 pages, September 2000.<br />
<br />
;[http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]<br />
:Michael Barr and Charles Wells. The revised version of their formerly Springer Verlag published book is online for free download. Note that they use the name ''triple'' instead of ''monad''.<br />
<br />
=[[Research papers]]=<br />
<br />
A large collection of research papers published on various aspects of Haskell.<br />
<br />
<br />
[http://haskell.readscheme.org/ An Online Bibliography of Haskell research]<br />
:ReadScheme.org</div>Felix stegermanhttps://wiki.haskell.org/index.php?title=Books&diff=7018Books2006-10-14T11:44:12Z<p>Felix stegerman: </p>
<hr />
<div>Books and tutorials covering many aspects of Haskell.<br />
<br />
=Language and library definition=<br />
<br />
<DL><br />
<DT>Simon Peyton Jones: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521826144 "Haskell 98 language and libraries: the Revised Report"], Cambridge University Press, 2003, Hardback, 272 pages, ISBN: 0521826144, £35.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library specification]]<br />
</DT><br />
</DL><br />
<br />
= Textbooks=<br />
<br />
<DL><br />
<DT>Paul Hudak: [http://www.haskell.org/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN:<br />
0521644089, Hardback $74.95, ISBN: 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of domain specific languages, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's Web Site contains source files for all programs in the<br />
text, as well as the graphics libraries to run them under Windows and<br />
Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
</blockquote><br />
<DT>Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN<br />
0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN: 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<DT>Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN<br />
0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A website gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt> Cordelia Hall and John O'Donnell: [http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/ <em>Discrete Mathematics Using a Computer</em>],<br />
Springer, 2000, 360 pages. ISBN 1-85233-089-9.<br />
<blockquote><br />
<b>Book description:</b><br><br />
This book introduces the main topics of discrete mathematics with a strong emphasis on<br />
applications to computer science. It uses computer programs to implement and illustrate<br />
the mathematical ideas, helping the reader to gain a concrete understanding of the<br />
abstract mathematics. The programs are also useful for practical calculations, and they<br />
can serve as a foundation for larger software packages. <br />
<br />
Designed for first and second year undergraduate students, the book is also ideally suited<br />
to self-study. No prior knowledge of functional programming is required; the book and<br />
the online documentation provide everything you will need. <br />
</blockquote><br />
<br />
<dt>Kees Doets and Jan van Eijck: [http://www.cwi.nl/~jve/HR <em>The Haskell Road to Logic, Maths and Programming</em>]. King's College Publications, London, 2004. ISBN 0-9543006-9-6 (14.00 pounds, $25.00).<br />
<blockquote><br />
<b>Book description:</b><br><br />
The purpose of this book is to teach logic and mathematical reasoning<br />
in practice, and to connect logical reasoning with computer<br />
programming. Throughout the text, abstract concepts are linked to<br />
concrete representations in Haskell. Everything one has to know about<br />
programming in Haskell to understand the examples in the book is<br />
explained as we go along, but we do not cover every aspect of the<br />
language. Haskell is a marvelous demonstration tool for logic and<br />
maths because its functional character allows implementations to<br />
remain very close to the concepts that get implemented, while the<br />
laziness permits smooth handling of infinite data structures.<br />
<br />
We do not assume that our readers have previous experience with either<br />
programming or construction of formal proofs. We do assume previous<br />
acquaintance with mathematical notation, at the level of secondary<br />
school mathematics. Wherever necessary, we will recall relevant <br />
facts. Everything one needs to know about mathematical<br />
reasoning or programming is explained as we go along. We do assume<br />
that our readers are able to retrieve software from the Internet and<br />
install it, and that they know how to use an editor for constructing<br />
program texts.<br />
<br />
After having worked through the material in the book, i.e., after<br />
having digested the text and having carried out a substantial number<br />
of the exercises, the reader will be able to write interesting<br />
programs, reason about their correctness, and document them in a clear<br />
fashion. The reader will also have learned how to set up mathematical<br />
proofs in a structured way, and how to read and digest mathematical<br />
proofs written by others.<br />
<br />
The book can be used as a course textbook, but since it comes with<br />
solutions to all exercises (electronically available from the authors<br />
upon request) it is also well suited for private study. The source<br />
code of all programs discussed in the text, a list of errata, <br />
further relevant material and an email link to the authors<br />
can be found [http://www.cwi.nl/~jve/HR here].<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: <em>Implementation of Functional Programming Language</em>,Prentice-Hall, 1987. ISBN 0134533259.<br />
<br />
<dt>Simon Peyton Jones, David Lester: <em>Implementing Functional Languages</em>, 1992.<br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
</blockquote><br />
<br />
<dt>Simon Thompson: <em>Type Theory and Functional Programming</em>, Addison-Wesley, 1991. ISBN 0-201-41667-0.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
</DL><br />
<br />
=Tutorials=<br />
<br />
==Introductions to Haskell==<br />
<br />
;[http://www.haskell.org/tutorial/ A Gentle Introduction to Haskell] <br />
:By Paul Hudak, John Peterson, and Joseph H. Fasel. The title is a bit misleading. Some knowledge of another functional programming language is expected. The emphasis is on the type system and those features which are really new in Haskell (compared to other functional programming languages). A classic.<br />
<br />
;[http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf Yet Another Haskell Tutorial]<br />
:By Hal Daume III et al. A recommended tutorial for Haskell that is still under construction but covers already much ground. Also a classic text.<br />
<br />
;[http://www.haskell.org/~pairwise/intro/intro.html Haskell Tutorial for C Programmers]<br />
:By Eric Etheridge. From the intro: "This tutorial assumes that the reader is familiar with C/C++, Python, Java, or Pascal. I am writing for you because it seems that no other tutorial was written to help students overcome the difficulty of moving from C/C++, Java, and the like to Haskell."<br />
<br />
;[http://www-106.ibm.com/developerworks/edu/os-dw-linuxhask-i.html Beginning Haskell] <br />
:From IBM developerWorks. This tutorial targets programmers of imperative languages wanting to learn about functional programming in the language Haskell. If you have programmed in languages such as C, Pascal, Fortran, C++, Java, Cobol, Ada, Perl, TCL, REXX, JavaScript, Visual Basic, or many others, you have been using an imperative paradigm. This tutorial provides a gentle introduction to the paradigm of functional programming, with specific illustrations in the Haskell 98 language. (Free registration required.)<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/teaching/Hskurs_toc.html Online Haskell Course] <br />
:By Ralf Hinze (in German).<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/tutorials.html Tutorial Papers in Functional Programming].<br />
:A collection of links to other Haskell tutorials, from John Hughes.<br />
<br />
;[http://www.cs.ou.edu/cs1323h/textbook/haskell.shtml Two Dozen Short Lessons in Haskell] <br />
:By Rex Page. A draft of a textbook on functional programming, available by ftp. It calls for active participation from readers by omitting material at certain points and asking the reader to attempt to fill in the missing information based on knowledge they have already acquired. The missing information is then supplied on the reverse side of the page. <br />
<br />
;[http://pleac.sourceforge.net/pleac_haskell/t1.html PLEAC-Haskell]<br />
:Following the Perl Cookbook (by Tom Christiansen and Nathan Torkington, published by O'Reilly) spirit, the PLEAC Project aims to gather fans of programming, in order to implement the solutions in other programming languages.<br />
<br />
;[ftp://ftp.geoinfo.tuwien.ac.at/navratil/HaskellTutorial.pdf Haskell-Tutorial] <br />
:By Damir Medak and Gerhard Navratil. The fundamentals of functional languages for beginners. <br />
<br />
;[http://en.wikibooks.org/wiki/Haskell Programming Haskell Wikibook] <br />
:A communal effort by several authors to produce the definitive Haskell textbook. Its very much a work in progress at the moment, and contributions are welcome.<br />
<br />
;[http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung Video Lectures] <br />
:Lectures (in English) by Jürgen Giesl. About 30 hours in total, and great for learning Haskell. The lectures are 2005-SS-FP.V01 through 2005-SS-FP.V26. Videos 2005-SS-FP.U01 through 2005-SS-FP.U11 are exercise answer sessions, so you probably don't want those.<br />
<br />
;[http://www.cs.utoronto.ca/~trebla/fp/ Albert's Functional Programming Course] <br />
:A 15 lesson introduction to most aspects of Haskell.<br />
<br />
;[http://www.iceteks.com/articles.php/haskell/1 Introduction to Haskell]<br />
:By Chris Dutton, An "attempt to bring the ideas of functional programming to the masses here, and an experiment in finding ways to make it easy and interesting to follow".<br />
<br />
;[http://www.csc.depauw.edu/~bhoward/courses/0203Spring/csc122/haskintro/ An Introduction to Haskell]<br />
:A brief introduction, by Brian Howard.<br />
<br />
;[http://web.syntaxpolice.org/lectures/haskellTalk/slides/index.html Introduction to Haskell]<br />
:By Isaac Jones (2003).<br />
<br />
;[http://www.linuxjournal.com/article/9096 Translating Haskell into English]<br />
:By Shannon Behrens, a glimpse of the Zen of Haskell, without requiring that they already be Haskell converts.<br />
<br />
;[http://www.thaiopensource.com/relaxng/derivative.html An algorithm for RELAX NG validation]<br />
:by James Clark (of RELAX NG fame). Describes an algorithm for validating an XML document against a RELAX NG schema, uses Haskell to describe the algorithm. The algorithm in Haskell and Java is then [http://www.donhopkins.com/drupal/node/117 discussed here].<br />
<br />
===Real world tutorials===<br />
<br />
These tutorials examine using Haskell to writing complex real-wrold applications<br />
<br />
;[[Hitchhikers Guide to the Haskell]]<br />
: Tutorial for C/Java/OCaml/... programers by Dmitry Astapov. From the intro: "This text intends to introduce the reader to the practical aspects of Haskell from the very beginning (plans for the first chapters include: I/O, darcs, Parsec, QuickCheck, profiling and debugging, to mention a few)".<br />
<br />
;[http://haskell.org/haskellwiki/IO_inside Haskell I/O inside: Down the Rabbit's Hole]<br />
:By Bulat Ziganshin (2006), a comprehensive tutorial on using IO monad.<br />
<br />
;[http://research.microsoft.com/%7Esimonpj/Papers/marktoberdorf Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell]<br />
:Simon Peyton Jones. Presented at the 2000 Marktoberdorf Summer School. In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1 58603 1724, 2001, pp47-96. The standard reference for monadic IO in GHC/Haskell. <br><strong>Abstract:</strong>Functional programming may be beautiful, but to write real applications we must grapple with awkward real-world issues: input/output, robustness, concurrency, and interfacing to programs written in other languages.<br />
<br />
;[http://www.reid-consulting-uk.ltd.uk/docs/ffi.html A Guide to Haskell's Foreign Function Interface]<br />
:A guide to using the foreign function interface extension, using the rich set of functions in the Foreign libraries, design issues, and FFI preprocessors.<br />
<br />
===Older tutorials===<br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/manuals/haskeller.dvi.gz The Little Haskeller] <br />
:By Cordelia Hall and John Hughes. 9. November 1993, 26 pages. An introduction using the Chalmers Haskell B interpreter (hbi). Beware that it relies very much on the user interface of hbi which is quite different for other Haskell systems, and the tutorials cover Haskell 1.2 , not Haskell 98.<br />
<br />
;[http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Functional Programming]<br />
:By Jeroen Fokker, 1995. (153 pages, 600 KB). Textbook for learning functional programming with Gofer (an older implementation of Haskell). Here without Chapters&nbsp;6 and&nbsp;7.<br />
<br />
;[http://wiki.python.org/moin/PythonVsHaskell Comparing Haskell and Python]<br />
:A short overview of similarities and differences between Haskell and Python.<br />
<br />
;[http://mult.ifario.us/articles/2006/10/11/first-steps-with-haskell-for-web-applications Haskell + FastCGI versus Ruby on Rails]<br />
:A short blog entry documenting performance results with ruby on rails and Haskell with fastcgi<br />
<br />
==Reference material==<br />
<br />
;[http://undergraduate.csse.uwa.edu.au/units/230.301/lectureNotes/tourofprelude.html A Tour of the Haskell Prelude (basic functions)] <br />
:By Bernie Pope and Arjan van IJzendoorn.<br />
<br />
;[http://cs.anu.edu.au/Student/comp1100/haskell/tourofsyntax.html Tour of the Haskell Syntax] <br />
:By Arjan van IJzendoorn.<br />
<br />
;[http://zvon.org/other/haskell/Outputglobal/index.html Haskell Reference] <br />
:By Miloslav Nic.<br />
<br />
;[http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions]<br />
:By Henk-Jan van Tuyl.<br />
<br />
;[http://www.cse.unsw.edu.au/~en1000/haskell/inbuilt.html Useful Haskell functions]<br />
:An explanation for beginners of many Haskell functions that are predefined in the Haskell Prelude.<br />
<br />
;[http://haskell.org/ghc/docs/latest/html/libraries/ Documentation for the standard libraries]<br />
:Complete documentation of the standard Haskell libraries.<br />
<br />
;[http://www.haskell.org/haskellwiki/Category:Idioms Haskell idioms]<br />
:A collection of articles describing some common Haskell idioms. Often quite advanced.<br />
<br />
;[http://www.haskell.org/haskellwiki/Blow_your_mind Useful idioms]<br />
:A collection of short, useful Haskell idioms.<br />
<br />
;[http://www.haskell.org/haskellwiki/Programming_guidelines Programming guidelines]<br />
:Some Haskell programming and style conventions.<br />
<br />
;[http://haskell.org/haskellwiki/Category:Tutorials A growing list of Haskell tutorials on a diverse range of topics]<br />
:Available on this wiki<br />
<br />
== Motivation for using Haskell ==<br />
<br />
;[http://www.md.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters] <br />
:By [http://www.md.chalmers.se/~rjmh/ John Hughes], The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.<BR> Exposes the advantages of functional programming languages. Demonstrates how higher-order functions and lazy evaluation enable new forms of modularization of programs.<br />
<br />
;[[Why Haskell matters]] <br />
:Discussion of the advantages of using Haskell in particular. An excellent article.<br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/224/index.html Higher-order + Polymorphic = Reusable] <br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. Unpublished, May 1997.<BR> <STRONG>Abstract:</STRONG> This paper explores how certain ideas in object oriented languages have their correspondents in functional languages. In particular we look at the analogue of the iterators of the C++ standard template library. We also give an example of the use of constructor classes which feature in Haskell 1.3 and Gofer.<br />
<br />
;[http://www-128.ibm.com/developerworks/java/library/j-cb07186.html Explore functional programming with Haskell]<br />
:Introduction to the benefits of functional programming in Haskell by Bruce Tate.<br />
<br />
==Analysis and design methods==<br />
<br />
See [[Analysis and design]].<br />
<br />
== Teaching Haskell == <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/208/index.html Where do I begin? A problem solving approach to teaching functional programming]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. In Krzysztof Apt, Pieter Hartel, and Paul Klint, editors, First International Conference on Declarative Programming Languages in Education. Springer-Verlag, September 1997. <br> <STRONG>Abstract:</STRONG> This paper introduces a problem solving method for teaching functional programming, based on Polya's `How To Solve It', an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study. <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1995/214/index.html Functional programming through the curriculum]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]and Steve Hill. In Pieter H. Hartel and Rinus Plasmeijer, editors, Functional Programming Languages in Education, LNCS 1022, pages 85-102. Springer-Verlag, December 1995. <br> <STRONG>Abstract:</STRONG> This paper discusses our experience in using a functional language in topics across the computer science curriculum. After examining the arguments for taking a functional approach, we look in detail at four case studies from different areas: programming language semantics, machine architectures, graphics and formal languages. <br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/CK02a.html The Risks and Benefits of Teaching Purely Functional Programming in First Year]<br />
:By [http://www.cse.unsw.edu.au/~chak Manuel M. T. Chakravarty] and [http://www.cse.unsw.edu.au/~keller Gabriele Keller]. Journal of Functional Programming 14(1), pp 113-123, 2004. An earlier version of this paper was presented at Functional and Declarative Programming in Education (FDPE02). <br> <strong>Abstract</strong> We argue that teaching purely functional programming as such in freshman courses is detrimental to both the curriculum as well as to promoting the paradigm. Instead, we need to focus on the more general aims of teaching elementary techniques of programming and essential concepts of computing. We support this viewpoint with experience gained during several semesters of teaching large first-year classes (up to 600 students) in Haskell. These classes consisted of computer science students as well as students from other disciplines. We have systematically gathered student feedback by conducting surveys after each semester. This article contributes an approach to the use of modern functional<br />
languages in first year courses and, based on this, advocates the use of functional languages in this setting.<br />
<br />
==Using monads==<br />
<br />
See also the [[Monad]] HaskellWiki page with another list of tutorials (should this redundancy be removed? -- not sure...)<br />
<br />
;[http://www.nomaware.com/monads/html/ All About Monads] <br />
:By Jeff Newbern. This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. <br />
<br />
;[http://db.ewi.utwente.nl/Publications/PaperStore/db-utwente-0000003696.pdf The Haskell Programmer's Guide to the IO Monad - Don't Panic.] <br />
:Stefan Klinger. This report scratches the surface of category theory, an abstract branch of algebra, just deep enough to find the monad structure. It seems well written.<br />
<br />
;[http://www-users.mat.uni.torun.pl/~fly/materialy/fp/haskell-doc/Monads.html What the hell are Monads?] <br />
:By Noel Winstanley. A basic introduction to monads, monadic programming and IO. This introduction is presented by means of examples rather than theory, and assumes a little knowledge of Haskell. <br />
<br />
;[http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm Monads for the Working Haskell Programmer -- a short tutorial]<br />
:By Theodore Norvell. <br />
<br />
;[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.)]<br />
:A short tutorial on monads, introduced from a pragmatic approach, with less category theory references <br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/monads.html Systematic Design of Monads]<br />
:John Hughes & Magnus Carlsson. Many useful monads can be designed in a systematic way, by successively adding facilities to a trivial monad. The capabilities that can be added in this way include state, exceptions, backtracking, and output. Here we give a brief description of the trivial monad, each kind of extension, and sketches of some interesting operations that each monad supports.<br />
<br />
;[[Meet Bob The Monadic Lover]]<br />
:by Andrea Rossato. A by-the-author-supposed-to-be funny and short introduction to Monads, with code but without any reference to category theory: what monads look like and what they are useful for, from the perspective of a ... lover. (There is also the slightly more serious [[The Monadic Way]] by the same author.)<br />
<br />
;[http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html Monad Transformers Step by Step]<br />
:Martin Grabm&uuml;ller: a small tutorial on using monad transformers. In contrast to others found on the web, it concentrates on using them, not on their implementation.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
==Using arrows==<br />
<br />
This topic has an own HaskellWiki page: [[Arrow]].<br />
<br />
;[http://www.haskell.org/arrows/ Arrows: A General Interface to Computation]<br />
:Ross Paterson's page on arrows.<br />
<br />
HaWiki's [http://haskell.org/hawiki/UnderstandingArrows UnderstandingArrows].<br />
<br />
Monad.Reader's [http://www.haskell.org/tmrwiki/ArrowsIntroduction ArrowsIntroduction] article.<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
== Attribute grammars ==<br />
<br />
This topic has an own HakellWiki page: [[Attribute grammar]]<br />
<br />
== Categorical programming ==<br />
<br />
See its own HaskellWiki page: [[Category theory#Categorical programming]].<br />
<br />
== Data structures ==<br />
<br />
;[http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.cs.columbia.edu/~cdo/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
<br />
See [[Research papers/Data structures]]<br />
<br />
==Schools on advanced funtional programming==<br />
<br />
<EM>Advanced Functional Programming</EM>, First International Spring<br />
School on Advanced Functional Programming Techniques, Bastad, Sweden, LNCS 925, Springer-Verlag, 1995 (editors: J. Jeuring, E. Meijer).<br />
*<EM>Functional Parsers</EM> by Jeroen Fokker, p.&nbsp;1-23.<br />
*<EM>Monads for functional programming</EM> by Philip Wadler, p.&nbsp;24-52.<br />
*<EM>The Design of a Pretty-printing Library</EM> by John Hughes, p.&nbsp;52-96.<br />
*<EM>Functional Programming with Overloading and Higher-Order Polymorphism</EM>, Mark P. Jones, p.&nbsp;97-136.<br />
*<EM>Programming with Fudgets</EM> by Thomas Hallgren and Magnus Carlsson, p.&nbsp;137-182.<br />
*<EM>Constructing Medium Sized Efficient Functional Programs in Clean</EM> by Marko C.J.D. van Eekelen and Rinus J. Plasmeijer, p.&nbsp;183-227.<br />
*<EM>Merging Monads and Folds for Functional Programming</EM> by Erik Meijer and Johan Jeuring, p.&nbsp;228-266.<br />
*<EM>Programming with Algebras</EM> by Richard B. Kieburtz and Jeffrey Lewis, p.&nbsp;267-307.<br />
*<EM>Graph Algorithms with a Functional Flavour</EM> by John Launchbury, p.&nbsp;308-331.<br />
<br />
[http://www.cse.ogi.edu/PacSoft/conf/summerschool96.html <EM>Advanced Functional Programming</EM>], Second International Summer School on Advanced Functional Programming Techniques, Evergreen State College, WA, USA, LNCS 1126, Springer-Verlag, 1996 (editors: J. Launchbury, E. Meijer, T. Sheard).<br />
*<EM>Composing the User Interface with Haggis</EM> by Sigbjorn Finne and Simon Peyton Jones, p.&nbsp;1-37.<br />
*<EM>Haskore Music Tutorial</EM> by Paul Hudak, p.&nbsp;38-67.<br />
*<EM>Polytypic Programming</EM> by Johan Jeuring and Patrick Jansson, p.&nbsp;68-114.<br />
*<EM>Implementing Threads in Standard ML</EM> by Peter Lee, p.&nbsp;115-130.<br />
*<EM>Functional Data Structures</EM> by Chris Okasaki, p.&nbsp;131-158.<br />
*<EM>Heap Profiling for Space Efficiency</EM> by Colin Runciman and Niklas R&ouml;jemo, p.&nbsp;159-183.<br />
*<EM&gt;Deterministic, Error-Correcting Combinator Parsers</EM> by S. Doaitse Swierstra and Luc Duponcheel, p.&nbsp;184-207.<br />
*<EM>Essentials of Standard ML Modules</EM> by Mads Tofte, p.&nbsp;208-238.<br />
<br />
[http://alfa.di.uminho.pt/~afp98/ Advanced Functional Programming, Third International School, AFP'98], <br />
in Braga, Portugal from 12th to 19th September 1998, LNCS 1608, Springer-Verlag, 1999<br />
(editors: D. Swierstra, P. Henriques and J. Oliveira).<BR><br />
All lecture notes and further material are available from the web site.<br />
<br />
= Foundations =<br />
<br />
Some books and links listed here can be found also in the articles of ''Theoretical foundations'' category<br />
* see [[Mathematics]]<br />
* or browse ''Theoretical foundations'' among [[Special:Categories]].<br />
<br />
;[http://www.dcs.qmul.ac.uk/~pt/Practical_Foundations/ Practical Foundations of Mathematics]<br />
:Paul Taylor. Cambridge University Press, ISBN: 0-521-63107-6, xii+576 pages, September 2000.<br />
<br />
;[http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]<br />
:Michael Barr and Charles Wells. The revised version of their formerly Springer Verlag published book is online for free download. Note that they use the name ''triple'' instead of ''monad''.<br />
<br />
=[[Research papers]]=<br />
<br />
A large collection of research papers published on various aspects of Haskell.<br />
<br />
<br />
[http://haskell.readscheme.org/ An Online Bibliography of Haskell research]<br />
:ReadScheme.org</div>Felix stegerman