Need to learn Prolog, Haskell for a C# programmer
There are very few languages X, if any for which you could not write a Reg Braithwaite approved post of the form "What I learned from Language X that makes me a better programmer when I use Language Y"
C# itself is accumulating a number of functional constructs -- lambda expressions and the System.Linq extension methods -- so learning to think functionally will definitely help you get the best out of the day-job language, as well as being fun in and of itself. As it happened Erlang was the first functional/pattern-matching language I picked up after C#, but that alone was enough to make me look again at my C# style and how I approached problems.
FP is becoming the next big thing, and there's no dearth of languages to look at and decide which suits you most for learning -- Haskell, Erlang, as well as newcomers F#, Scala & Clojure are all riding this wave.
Like the first time you went from imperative to object-oriented, working with functional programming requires a rewiring of how you think things out. The first time you tend to do things in a hybrid fashion until you get the gist of it all. Since you are coming from C# background, I would suggest trying F# as you are likely to get used to it much more quickly since the .net languages share a common framework which is good enough to get you started.
That said going directly to Prolog and Haskell is not a bad idea but you might have to first adjust to the different syntax and libraries of the languages when compared to the leap between C# and F#. Personally, I went from C#/Java to Haskell by means of 2 books: RealWorldHaskell and The Craft of Functional Programming, and managed fine, so there is no reason for you not to be able to do so. :)
Learning F# and then Haskell still requires some work because F# and Haskell are different: the first is "impure" while the second is "pure". Impurity means that certain "side-effects" such as state and IO are intrinsically allowed, while purity means that you don't get them immediately but have to use certain methods (such as monads). Coming from C# it would be perhaps easier to try F# and then Haskell cause of this.
I believe (personal opinion warning), that if you want to become a better C# programmer, learning about F# and Haskell (or anything for that matter) can never hurt! Especially in the case of F# which can be integrated with C#. Functional programming may facilitate certain things for you and knowing it might become useful sooner or later especially since it seems, like the others said, that there is a current trend towards functional language programs.
Learning functional programming coming from an imperative language like C# is very hard, its a completely new way of thinking (for me at least, you may find functional languages easier to understand! depends how your brain works ;))
F# would be a good choice because it sits on the CLR, this means you can use F# libraries you write from your C# code with ease.
F# is typically better suited to "functional" (mathematical) problems.
Im looking at rewriting some complex algorithms in my C# code with F# to make them faster and more succinct.
As Ahmed mentions. Learning to think about problems in a new way can only be beneficial!