...wait, what now? Functional programming is not inherently tied to recursion you know.
The key ideas behind functional programming are:
- Immutability - all variables are final
- Idempotance - a function can be applied multiple times without changing the result
- First Class Functions - You can pass functions as arguments
- Composability - Programs are made by composing functions together to make larger functions
The key goal here is to eliminate state and mutability for code that will always perform the same way. By not having your functions mutate state, you can call functions in any order without worrying about it. This is also a lead in to safe parallelism.
Now in Ruby we have the enumerable module which allows large amounts of functional programming techniques without the need for recursion. Take for example summing an array of numbers:
numbers = [1,2,3,4,5] # or a range, but this is clearer for newbies# Imperativesum = 0for i in numbers sum += iendsum# => 15sum = 0numbers.each { |i| sum += i } # which is funny considering that's an anonymous function, but I digresssum# => 15# Functionalsum = numbers.reduce(0) { |accumulator, i| accumulator + i }# => 15sum = numbers.reduce
+) # Shorthand# => 15Reduce in this case is a prime element of functional programming. It takes a set and reduces it into a single number. To lay that out for you step by step:
Code:
sum = numbers.reduce(0) { |accumulator, i| accumulator + i }# Initial loop (accumulator = 0, i = 1) returns 1, which goes into the value of accumulator for the next loop# (accumulator = 1, i = 2) returns 3# (accumulator = 3, i = 3) returns 6# (accumulator = 4, i = 6) returns 10# (accumulator = 10, i = 5) returns 15# There are no more numbers, the accumulator is returned
Now how does reduce work? Let's demonstrate using recursion:
Code:
reduce = -> collection, fn, accumulator { if collection.empty? # We're out of elements, give back the accumulator accumulator else head = collection.first # Get the first element of the list tail = collection[1..-1] # and the rest of the elements reduce.call( tail, # We send the rest of the list in for the next loop fn, # and the reducing function fn.call(accumulator, head) # while setting the accumulator equal to the result of the function ) end}# And we do the same summation functionreduce.call( [1,2,3,4,5], -> acc, i { acc + i }, 0)#=> 15
The other common staples of functional programming are the map and filter functions. In Ruby, we use:
Code:
numbers = [1,2,3,4,5]# Applies a function to each element of the listnumbers.map { |i| i * 2 }# => [2,4,6,8,10]# Returns a list in which all elements return true when given to the functionnumbers.select { |i| i.even? }# => [2,4]
Shall we implement these ones as well?
Code:
map = -> list, fn { if list.empty? # If it's empty we hit the end [] else head = list.first # Get the first element tail = list[1..-1] # and the rest of them [fn.call(head)].concat map.call(tail, fn) # apply the function to the head, and recur on the tail end}map.call([1,2,3,4,5], -> i { i * 2 })# => 15select = -> list, fn { if list.empty? [] else head = list.first # Get the first element tail = list[1..-1] # and the rest of them matched_element = fn.call(head) # If the function returns true if matched_element [head].concat select.call(tail, fn) # We add the element to the list else [].concat select.call(tail, fn) # We add nothing to the list end end}select.call([1,2,3,4,5], -> i { i.even? })# => [2,4]
Now the nice thing is that Ruby already provides tons of these features, has first class functions, and it uses them widely (what do you think a block is? An anonymous function)Granted those are not concise implementations, I don't mean them to be. They're using tail recursion, something that should be used sparingly in Ruby unless you have the optimization turned on. This won't be an issue in most cases, but you end up with stack level too deep on larger problems. TCO fixes this issue, but I won't delve into that one.
Now what baffles me is that most people think that OO and Functional are opposites. No. They're not. You can still have OO in a functional style, mainly through usage of let and lambda, but that's in the purist kingdom of lambda the ultimate. The point is to eliminate superfluous state, not all of it. That's Haskell's main pull, but it will drive most newbies off a cliff unless they're math types.
RGSS is heavily heavily imperative, uses global variables freely, and in general makes a mess of things. I won't hold punches, it's a mess. That doesn't mean the code you write has to be as well. Avoid mutating variables when possible, keep your functions simple and succinct, and avoid the globals as much as possible.
As far as deep recursion, tree problems, and more complicated issues loops will not work. Dynamic programming is one such task that's impossible without recursion. There are several problems where imperative techniques will gimp you, and most of them happen to come up in job interviews.
