I would strongly back Haskell for this purpose. The reason for this is principally that Haskell is a single install, (whereas Clojure requires the jvm first and then Clojure). Haskell is a single language, Clojure is java with Clojure running on top.
When I started learning to program the greatest joy was code=some result. The greatest misery was installation, configuration and bizzaro error messages. In this regard I think Haskell comes out far far ahead. When I first learned Haskell I remember installing Hugs was simple and the REPL worked immediately.
I think that the number one consideration for a first time programming language is the ease with which you can get working software that does something and gives feedback. Clojure has too many leaky abstractions and is not nearly as simple to get up and running. (Aside, I like Clojure)
I think that what I am reading as an implicit question of "should a programmer be initially exposed to the greatest type system known to man in Haskell or the one-true programming language in Lisp" is taking the wrong approach. We should ask "how can I expose a programmer to the joy of making things using only a brain and a keyboard". I suspect that many of the best Haskell and Lisp hackers we have got started on Visual Basic because it was so accessible.
I apologise if my characterisation of your question was wrong. It's not my intention to be offensive or stir up trouble. Those are two great languages to choose from, if you can capture the mind and imagination of a first time programmer with either of them they will be off to a great start.
I learned scheme first, then haskell, then (now) clojure. I think haskell is best for teaching functional programming because it's purely functional and puts focus on that aspect rather than on performance benefits of being functional. after ~1 year with it, I've decided that haskell, while great, is not for me, and I'm switching over to clojure. Clojure is very nice as a language; what it lacks in terms of a type system it makes up for with the presence of macros.
However, I don't think that clojure is quite as great for teaching functional programming, because it is an eager language unless you explicitly tell it to be lazy exactly where you want it to be, so it doesn't have the performance optimizations that haskell has with recursion (as opposed to tail-call recursion) and it's therefore discouraged to not use tail-call recursion.
Now that's my recommendation for a first functional programming language. For a first language in general, I'd recommend the reverse because with clojure you can actually start doing something practical as soon as you get started, where with haskell it takes a while to get to that point.
But the installation process is different with the two. With clojure, the language is designed around being used with a build system as part of java tradition, which means that you normally can't just type `clj` and get a REPL (at least not with the official distribution). Generally the best way to go about doing that is to install leiningen and make a new project and do `lein repl` in the project directory.
In Haskell on the other hand (with the Haskell platform installer) you can just run the installer and type `ghci` and get a REPL. If you want to run a Haskell program to test it, it's just `runhaskell file.hs` and to compile, it's as simple as `ghc --make file.hs`. But when things get more complicated, even slightly so, Haskell can be an incredible pain to deal with (in terms of compiling and such) whereas clojure, being designed around build systems for large project, scales up just fine.
Great question. I would suggest first learning a Lisp (Elisp, Clojure, Scheme, Arc, etc) and then moving to Haskell.
With Haskell, you'll be learning more than basic lambda calculus. Haskell has a lot of new concepts that traditional-language programmers may have to rewire their brains to think about. Things like lazy evaluation by default, automatic currying, a more advanced type system than most other languages and the concepts that brings like Functors, Monads, and Iteratees. Lazy IO is rough edge which is, as we speak, in the process of being cleaned up by Iteratees.
With a Lisp, you can learn the basic concepts of lambda calculus without having to learn more advanced language features at the same time. You'll tackle things like programming in a declarative language and leveraging first-order functions. Remember, you're trading for-loops for recursion, and for some, that's enough brain rewiring without also worrying about lazy IO.
Lisp allows you to divide and conquer the multitude of language features functional languages have to offer. Why take them all on at once? Once you're comfortable with Lisp, Haskell's true benefits really start to shine. Haskell is by far my favorite language and I find myself hating programming without the features it offers but I'm not sure I would have made it far enough to see it's benefits without learning Scheme first. And learning Lisp is easy. It's a terse language which one could write a small project in in a few weeks and be ready for Haskell.
Haskell is challenging but there's a reason which I'll try to illustrate with an analogy: Calculus is more complex than arithmetic and without a more advanced problem to solve, the added complexity may not be a clear advantage. But you get to a certain point in physics where it simply becomes harder to work in only arithmetic and learning the abstraction of calculus up front pays dividends. Haskell is the same way. I'll end with PG's "The Blub Paradox" http://www.paulgraham.com/avg.html (scroll down).
I think it is worth learning both. Clojure is more "practical" in the sense that it is dynamic, impure and gives you access to the huge JVM library ecosystem, which is a huge advantage for real world projects. Haskell is pure and extremely elegant in an almost mathematical sense - if you want to learn the "true essence" of functional programming then it is ideal. Overall, Clojure is my favourite because of the practicality and the fact that it is compelling for other reasons (Lisp-style metaprogramming, interactive REPL development, code-as-data philosophy, concurrency features etc.)
Haskell is "cleaner" and "purer" if you're coming from a mathematical background its also probably going to be easier. Since this is going to be your first programming language I'd suggest Haskell since its cetianly more elegant (in my opinion). I'm a biased Haskell enthusiasist so that's my suggestion :)
Without taking sides, I would say look at some books on each. Kinda like comparing plutonium and uranium, or a cello to a guitar. Maybe these comparisons are silly. While youre at it look at scala and O'Caml.
You can look at the Yesod book, Real World Haskell and "Learn You a" online, i.e. read the complete, updated texts. Thompson's orange "Craft of FP" is a good read also, with methodical (and relatively slow-paced) coverage of all the basics. GHC is piling on language features and libs at a breathless pace, from deferred type checks, limited forms of dependent types, concurrency (async loops, STM, updated thread manager), IO abstractions (conduits), web apps (Yesod)
Clojure is an incredibly well documented (in books) language. I'm looking at the excellent O'reilly and Pragmatic books, and the 2 Manning books ("Joy of" is terrific), all of which came out in the last 4 months and target 1.3. And i will wager that Marick's book will be top notch as well. Unfortunately, these don't have texts online.
Neither is a bad choice. I'm partial to Clojure, specifically because it does integrate well with every Java library known to man. Starting out, there's a real Pavlovian benefit in being able to do something cool that "just works", and figure out the underlying principles later. It's fairly easy to take Clojure and integrate it with your machine learning library of choice, or a web framework, or Hadoop. Haskell has some of those libraries as well, but the advantage is that from the beginning you're exposing yourself to polyglot programming and it's easier to mix in some raw Java, or JRuby, or Jython...
I'd have to disagree here. I don't think its entirely unimportant which language a programmer begins with. Every language has its own community, resources, paradigms, general practices, etc. and if you start with a "rather lawless" language like PHP, you could be in for useless headaches. I started with C and initially it was difficult to grasp the OOP paradigm. I actually think starting with a functional language would be quite interesting since one is immediately confonted with the bridge between mathematical theory applied.