Having spent decades writing imperative, i.e. If and While statements, and logical, i.e. PROLOG, programs and having spent the last few months learning F# I will give you some advice from my perspective.
During those decades I have brushed against functional languages such as LISP, and Mercury, with enough understanding to read the code and write simple programs but only until using F# did I learn functional programming with enough detail to write production quality code.
Since you specifically mention the imperative languages Java and C# and the functional language F# I will used them as the basis for my answer. Since you use the term imperative and Object-Oriented in your question and specifically mention Java and C# which are Object-Oriented, I will tend you reference Object-Oriented instead of imperative.
Advise
How do I best make the transition from object-oriented programming
to functional programming?
The first advise I will give is to NOT try and translate any imperative programs you already have into a functional language. This probably goes against most of the advise you will see, but I firmly believe that you need to build up the constructs of how functional programming works in a simple manner rather than continuously trying to think in imperative and then try to think in functional. The reason is, is that functional programming relies heavily on recursion, matching, discriminated unions, functions and first class, let binding, and is function-level programming, while Object-Oriented code relies heavily on objects, polymorphism, inheritance, encapsulation, interfaces, and is object-oriented. The point here is that while they are both programming languages they really on two different ways of thinking. The best analogy I can think of, all be it a bad one is, it would be like trying to translate poetry into math. While I am sure you could do it and lay claim that it could be done, they both have very different uses and are well regarded by those who use it.
The second advise is to get one or two good books on F#. I have most of the books of F# and find that most of them are more reference than reading books which is good for the first few weeks, but after that you need to tie the concepts together and don't want a reference book. If I had to chose two books they would be "Expert F# 2.0" by Syme, Granicz, and Cisternino, and "Real-World Functional Programming With examples in F# and C#" by Tomas Petricek and Jon Skeet. "Expert F# 20" is more of a reference book and "Real-World Functional Programming With examples in F# and C#" is a book you read from start to end; don't use it as a refrence book. If "Expert F# 2.0" is not your style then as a substitute I would look at "Beginning F#" by Robert Pickering, or "Programming F#" by Chris Smith.
The third advise is to get a good IDE, e.g. Visual Studio 2010, for using F#. Don't think of this as learning a new programming language but learning a new way of thinking. Most of the errors you get back will be unlike anything from OO and the more you can use an IDE as a crutch, the faster you can hobble along; believe me, you will be hobbling along unless you already know a functional language. In particular, F# uses type inference which causes you to understand this concept to fix the errors.
The fourth advise is to get a mentor. Functional programming relies heavily on recursion and one has to think naturally in recursion to be effective. Luckily for me I learned this when learning PROLOG in college; I can't imagine how hard this would be without a mentor. While it would be possible, it will take longer. If you don't have some one who can mentor you, then use SO. Most of the authors I mentioned answer questions here.
The fifth advise is to learn these concepts: Let binding, F# List, recursion, discriminated unions and pattern matching. I probably use these concepts for more than 80% of the F# code I write. The reason you need F# list is that you will see code that traverse list building a second list of results and then reversing the list before returning the list of results. Because accessing the head of a list is O(1), this is both very fast and effective. The reason you need recursion is because functional programming does not use loops but recursion to preform looping. If you use a tail-call, you have effectively made a loop which does not cause stack overflows. The reason you need discriminated unions and pattern matching is because you can create a single data type, i.e. discriminated union, that holds all of the information for a function, and when combined with matching this is very effective. Microsoft's Introduction to F# is pretty good for these topics.
The sixth advise is don't rush ahead. If you can not explain a part of F# to someone else with enough confidence and clarity to understand it, then you need to keep learning.
The seventh advise is to understand that functional programming is not a solution to all problems. While F# adds OO concepts to functional programming, I try to avoid the use of those concepts when programming with F#. Yes I try to be a purest. By doing this, it keeps me focused on doing with F# what functional programming is best.
The eighth advise is that once you feel comfortable with many portions of functional programming, write a real program based on a real world problem. I find myself learning more about F# from working on a particular problem than working on made up problems. I have learned so much in the last few months, I won't even try and list it all here. One big benefit has been learning FParsec and a lot about LISP. Since my problem deals with AI, a lot of the books I read give sample code in LISP which I have to translate into F#. Since LISP people like to enter data as S-expressions and LISP can process S-expressions, they tend to get away with skiping parsing; thus a reason to learn FParsec.
I could list more items of advise, but at this point it becomes more of a list than sound advise.
Examples
Can you provide some tips or perhaps provide some literature
that can help one to think "in functions" in general?
Probably the easist way to identify problems that can be solved with functional programming is to look at the data structure definitions.
If you have a class or structure that has a reference back to the same class or structure and you traverse from one object to next using the reference then you should consider using functional programming for the solution.
A simple example is a linked list where you have to process all of the items in the list. You start on the first item in the list, then process then next item in the list until you reach the end of the list.
A more advanced example is a tree where you have to process all of the items in the tree. You start at the root of the tree, then process each child in the tree until you have no more children left. See: tree traversal
An even more advanced example is a graph where you have to process all of the nodes in the graph. You start with a node, then process each adjacent node, keeping track of visited nodes, until you have no more unvisited nodes left.
Also if you have a sequence of data that needs to be generated from a starting value then consider using functional programming for the solution.
Another large area where functional programming is useful is with Catamorphisms. While this is an advanced concept, think of it simply as a set of data that can be enumerated. You can map the data, e.g. an indentity number into and name, and fold the data, e.g. sum up all of the values in a list. Any time you see an enumeration in an OO language, see if it can be solved with a recursive function.
Other more advanced ares were functional programing is used often is with parsing, theorem provers and AI.
If you can find code written in other functional languages, then try and translate that to F#.
Good luck.
