How to make the transition to functional programming?

How to make the transition to functional programming?

• Lately, I have been very intrigued with F# which I have been working a bit with. Coming mostly from Java and C#, I like how concise and easily understandable it is. However, I believe that my background with these imperative languages disturb my way of thinking when programming in F#. I found a http://msdn.microsoft.com/en-us/library/bb669144.aspx of the imperative and functional approach, and I surely do recognize the "imperative way" of programming, but I also find it difficult to define problems to fit well with the functional approach. So my question is: How do I best make the transition from object-oriented programming to functional programming? Can you provide some tips or perhaps provide some literature that can help one to think "in functions" in general?

• Answer:

  Having spent decades writing http://en.wikipedia.org/wiki/Imperative_programming, i.e. If and While statements, and http://en.wikipedia.org/wiki/Logic_programming, i.e. http://en.wikipedia.org/wiki/Prolog, programs and having spent the last few months learning http://en.wikipedia.org/wiki/F_Sharp_%28programming_language%29 I will give you some advice from my perspective. During those decades I have brushed against functional languages such as http://en.wikipedia.org/wiki/Lisp_%28programming_language%29, and http://en.wikipedia.org/wiki/Mercury_%28programming_language%29, with enough understanding to read the code and write simple programs but only until using http://en.wikipedia.org/wiki/F_Sharp_%28programming_language%29 did I learn http://en.wikipedia.org/wiki/Functional_programming with enough detail to write production quality code. Since you specifically mention the http://en.wikipedia.org/wiki/Imperative_programming languages http://en.wikipedia.org/wiki/Java_%28programming_language%29 and http://en.wikipedia.org/wiki/C_Sharp_%28programming_language%29 and the functional language http://en.wikipedia.org/wiki/F_Sharp_%28programming_language%29 I will used them as the basis for my answer. Since you use the term imperative and http://en.wikipedia.org/wiki/Object-oriented_programming in your question and specifically mention http://en.wikipedia.org/wiki/Java_%28programming_language%29 and http://en.wikipedia.org/wiki/C_Sharp_%28programming_language%29 which are http://en.wikipedia.org/wiki/Object-oriented_programming, I will tend you reference http://en.wikipedia.org/wiki/Object-oriented_programming instead of http://en.wikipedia.org/wiki/Imperative_programming. 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 http://en.wikipedia.org/wiki/Category%3aFunctional_languages. 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 http://en.wikipedia.org/wiki/Recursion_%28computer_science%29, http://stackoverflow.com/questions/2502354/what-is-pattern-matching-in-functional-languages, http://msdn.microsoft.com/en-us/library/dd233226.aspx, http://en.wikipedia.org/wiki/First-class_function, http://msdn.microsoft.com/en-us/library/dd233238.aspx, and is http://en.wikipedia.org/wiki/Function-level_programming, while http://en.wikipedia.org/wiki/Object-oriented_programming code relies heavily on http://en.wikipedia.org/wiki/Object_%28computer_science%29, http://en.wikipedia.org/wiki/Polymorphism_in_object-oriented_programming, http://en.wikipedia.org/wiki/Inheritance_%28object-oriented_programming%29, http://en.wikipedia.org/wiki/Encapsulation_%28object-oriented_programming%29, http://en.wikipedia.org/wiki/Interface_%28computing%29, and is http://en.wikipedia.org/wiki/Object-oriented_programming. 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 http://www.apress.com/9781430224310 by Syme, Granicz, and Cisternino, and http://www.manning.com/petricek/ 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 http://www.apress.com/9781430223894 by Robert Pickering, or http://shop.oreilly.com/product/9780596153656.do by Chris Smith. The third advise is to get a good IDE, e.g. http://www.microsoft.com/visualstudio/en-us/products/2010-editions, 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 http://en.wikipedia.org/wiki/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 http://en.wikipedia.org/wiki/Recursion_%28computer_science%29 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: http://msdn.microsoft.com/en-us/library/dd233238.aspx, http://msdn.microsoft.com/en-us/library/dd233224.aspx, http://en.wikipedia.org/wiki/Recursion_%28computer_science%29, http://msdn.microsoft.com/en-us/library/dd233226.aspx and http://msdn.microsoft.com/en-us/library/dd547125.aspx. 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 http://msdn.microsoft.com/en-us/vs2010trainingcourse_introtofsharp#_Toc281930824 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 http://www.quanttec.com/fparsec/ and a lot about LISP. Since my problem deals with http://en.wikipedia.org/wiki/Artificial_intelligence, 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 http://en.wikipedia.org/wiki/S-expression and LISP can process http://en.wikipedia.org/wiki/S-expression, 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 http://en.wikipedia.org/wiki/Reference_%28computer_science%29 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 http://en.wikipedia.org/wiki/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 http://en.wikipedia.org/wiki/Tree_%28data_structure%29 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: http://en.wikipedia.org/wiki/Tree_traversal An even more advanced example is a http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29 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 http://en.wikipedia.org/wiki/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 http://en.wikipedia.org/wiki/Catamorphism. While this is an advanced concept, think of it simply as a set of data that can be http://en.wikipedia.org/wiki/Enumeration. You can http://en.wikipedia.org/wiki/Map_%28higher-order_function%29 the data, e.g. an indentity number into and name, and http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29 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 http://en.wikipedia.org/wiki/Parsing, http://en.wikipedia.org/wiki/Automated_theorem_prover and http://en.wikipedia.org/wiki/Artificial_intelligence. If you can find code written in other http://en.wikipedia.org/wiki/Category%3aFunctional_languages, then try and translate that to F#. Good luck.