Já foram dadas boas respostas, mas ainda faltou responder a algumas dúvidas do OP, que tentarei tratar aqui
Quais os prós e contras da programação funcional [em relação a paralelismo e threading]?
A questão aqui não é tanto o funcional vs. imperativo, e sim mutabilidade vs. imutabilidade.
Linguagens imperativas tendem a fazer um grande uso de estruturas e objetos mutáveis, com alteração de estado. Uma propriedade de um objeto, encapsulada por um par de métodos get e set é um exemplo disto.
Este estilo de programação costuma ser simples, em um ambiente single-threaded, mas ganha ordens de magnitude de complexidade quando se passa a considerar ambientes multi-processados. Pois, se mais de um processo pode ler e alterar uma variável, é necessário controlar os acessos simultâneos de leitura e de escrita à memória (através do uso de semáforos, por exemplo). E este controle, por ser muito complexo, é também muito sucetível a problemas, tais como deadlocks, baixa performance e outros erros de implementação.
Já as linguages funcionais tendem a utilizar somente estruturas e objetos imutáveis. Isso significa que objetos criados nunca mais são alterados (se uma informação precisa ser alterada, isso implica em criar um novo objeto, e não alterar o antigo).
Este estilo é muito mais custoso, do ponto de vista de consumo de memória, mas tem uma grande vantagem: todas as dificuldades associadas ao controle de leitura e escrita de memória deixam de existir (mas, claro, algumas novas dificuldades também surgem).
Vem daí também, em parte, a predileção das linguagens funcionais para com as listas, por serem estruturas que podem ser facilmente manipuláveis, sem abrir mão da imutabilidade (é possível "adicionar" um item a uma lista simplesmente ao criar um novo "head" que aponta para a lista antiga - ou seja, é criado um novo objeto lista, mas sem ser necessário copiar os itens da lista antiga para a nova, poupando processamento).
Porque eu deveria aprender Haskell?
Essa é uma pergunta capciosa, pois eu não acho que você deva aprender Haskell (pelo menos não agora)!
Você (o OP) parece não ter muito conhecimento sobre linguagens funcionais. E Haskell é com toda a certeza uma das mais complexas e difíceis linguagens de programação para se aprender. Além da imutabilidade, você teria que aprender conceitos como lazyness, pureza, type-classes, mônadas, monóides, memória transacional... E, acredite, isso tudo é ainda mais estranho do que o fato dela ser funcional. :P (Na minha opinião, é mais ou menos como querer aprender Física Quântica, sem ter aprendido Física Clássica Newtoniana: é possível, só não é sensato).
Existem opções bem mais acessíveis:
- Scheme é uma linguagem Lisp multi-paradigma, própria para estudantes, que faz uso forte dos conceitos funcionais, e é relativamente fácil de aprender (se você ignorar os parênteses).
- Clojure é mais um dialeto Lisp. Alguns afirmam que ele é ainda mais moderno e mais funcional que Scheme, com a vantagem de rodar na JVM. Pessoalmente ainda não tive a oportunidade de aprender Clojure mais a fundo, mas tudo indica que é uma das linguagens mais interessantes de se utilizar atualmente.
- Scala é uma linguagem que tenho experiência profissional, e que portanto posso falar melhor. À primeira vista parece muito com Java e Ruby, mas por "dentro" dá pra ver que se inspirou muito em Haskell. Não é totalmente funcional, e está longe de ser pura, mas costuma ser uma boa opção para aqueles que tem experiência em linguagens OOP como Java ou C#. Bibliotecas como a Lift (uma framework Web) permitem também ver, na prática, as vantagens (e desvantagens) do estilo funcional em áreas tipicamente dominadas pela orientação a objetos tradicional.
- F# é, assim como Scala, mais um exemplo de híbrido funcional x objetos. Mas F# "pega mais pesado" no lado funcional, por ser um superset de Ocaml. Também pode ajudar em se obter os "pré-requisitos" necessários pra se aprender Haskell (por exemplo, as computation expressions de F# são mônadas, que por sua vez são muito importantes para se entender Haskell).
Fora essas, é possível utilizar o principal conceito funcional, first-class functions, em Ruby, Python e até mesmo em C# (3.0+) e Java (8.0+).