I second the recommendation for The Nature of Computation; very well written with interesting problems.

I would also recommend Higher Order Perl. I went through it this summer after a recommendation. I don't know Perl, and found it was more focused on practical functional programming techniques, and provides creative and interesting justification for its topics, which can be rewritten in other languages too. Great book.