3

Many books about algorithms and data structures are coded by imperative languages. Is there any book that can show functional programming languages can do the same thing or do them better?

In particular I am interested in sorting, searching, data structures and graph.

Improve this question
2
  • Well unfortunately I don't have any books for you, but some things you could look into further are that many functional programs encourage laziness and this can lead to lazy sorting algorithms where only what is required to be sorted is. It can also lead to easier manipulation of infinite tree/graphs because you the programmer can often just treat them as you'd treat a finite graph.
    – WuHoUnited
    Commented Mar 15, 2012 at 2:05
  • possible duplicate of Is there a canonical tutorial or book on functional programming concepts?
    – gnat
    Commented May 2, 2013 at 19:36

4 Answers 4

Reset to default
2

If you're interested in purely functional data structures (which naturally go hand-in-hand with algorithms) you should check out Okasaki's Purely Functional Data Structures. It's in ML (with examples in Haskell as well) rather than Lisp, but it is still a very good resource for purely functional programming.

Improve this answer
1

I hope I did not understand the question wrong since I saw no suggestion for this book.

In my university we have a course that teaches paradigms of programming languages, they involve prolog, and lisp basically since we already cover Pascal, C, and Java on previous semesters.

The adopted book is available online for free: http://www.gigamonkeys.com/book/

I used this book most for reference, but I think to be a good one. While I as an assistant in this course we suggested the creation of a "LispUnit" a simple program so that students could test their own assignments. The code is available there online, and it was a very interesting experience.

Few students ended up learning how to test using Lisp actually.

On one of the assignments we proposed we emphasized as well how the idea of building from very simple blocks and reusing them on functional programming was more natural than in Java or C. We used few basic natural functions such as +, -, etc. Gave them the successor operation and they ended up creating many of the natural functions on Lisp. I think this is a simple, yet powerful way to mix mathematical concepts, specially since this is covered on Discrete Mathematics for Computer sciences degrees. We did not use LISP for anything like a real application thou, but I believe this book to provide better examples such as the test framework.

Hope this helps.

Improve this answer
1

A very thorough introduction to the core foundations of computer science, e.g.

  • some data structures and algorithms,
  • what's under the hood of a functional programming language,
  • how to use abstraction and modularity

is the classic book Structure and Interpretation of Computer Programs (SICP), which uses the language Scheme.

The book is also online at MIT, where they are using it heavily in teaching.

Improve this answer
1

A Haskell-based book:

Algorithms: A Functional Programming Approach, by Fethi Rabhi and Guy Lapalme

ISBN 0-201-59604-0

http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html

Also, this one seems like a nice little paper. Available online, too:

Jamie Snape, Loopless Functional Algorithms,

Master's thesis, Computing Laboratory, University of Oxford, 2005, advised by Richard S. Bird

http://wwwx.cs.unc.edu/~snape/publications/msc/

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.