Like kuramayoko10 said, Prolog is the most different language. Functional programming isn't that different to imperative programming for me (you still think the same way, just use functions for everything), but Prolog almost made me cry until I got it. The total lack of imperative programming concepts such as "if" and "for" is going to teach you a lot about recursion. Some things in Prolog are so much simpler and logical that they would be in an imperative language, that you'd wonder why there isn't a hype over it - like around Haskell, for example.
If you use functional programming like you do imperative programming then you are doing it wrong ™, in functional programming you don't have loops (for/while), nor do you have state (Something that throws most imperative programmers for a loop), proper functional programming is extremely similar to logic programming (both are declarative)