“Remembering” values in functional programming

This is really just an addendum to gardenhead's answer, but I'd like to point out there's a name for the pattern you're seeing: folding.

In functional programming, a fold is a way to combine a series of values that "remembers" a value between each operation. Consider adding a list of numbers imperatively:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

We take a list of values xs and an initial state of 0 (represented by total in this case). Then, for each x in xs, we combine that value with the current state according to some combining operation (in this case addition), and use the result as the new state. In essence, sum_all([1, 2, 3]) is equivalent to (3 + (2 + (1 + 0))). This pattern can be extracted into a higher order function, a function that accepts functions as arguments:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

This implementation of fold is still imperative, but it can be done recursively as well:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Expressed in terms of a fold, your function is simply:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

...where repeat(x, n) returns a list of n copies of x.

Many languages, particularly those geared towards functional programming, offer folding in their standard library. Even Javascript provides it under the name reduce. In general, if you find yourself using recursion to "remember" a value across a loop of some sort, you probably want a fold.

This is a supplemental answer to help explain maps and folds. For the examples below, I'll use this list. Remember, this list is immutable, so it will never change!:

var numbers = [1, 2, 3, 4, 5]

A map takes a list of something, and a function, and returns a list that was modified using the function. Each item is passed to the function, and becomes whatever the function returned.

The easiest example of this is just adding a number to each number in a list. I'll use pseudocode to make it language agnostic:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

If you printed numbers2, you would see [3, 4, 5, 6, 7] which is the first list with 2 added to each element. Notice the function add-two was given to map to use.

Folds are similar, except the function you're required to give them must take 2 arguments. The first argument is usually the accumulator (in a left fold, which are the most common), and the second is the current item of the list; just like above for the map function.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

If you printed sum you would see the sum of the list of numbers: 15.

Here are what the arguments to fold do:

1. This is the function that we're giving the fold. The fold will pass the function the current accumulator, and the current item of the list. Whatever the function returns will become the new accumulator, which will be passed to the function the next time. This is how you "remember" values when you're looping FP-style. I gave it a function that takes 2 numbers and adds them. The nice thing about adding numbers like this is the order of the arguments doesn't matter, since you'll get the same result, regardless of which is the accumulator.

2. This is the initial accumulator; what the accumulator starts as before any items in the list are processed. When you're summing numbers, what's the total before you've added any numbers together? 0, which I passed as the second argument.

3. Lastly, as with the map, we also pass in the list of numbers for it to process.

If folds still don't make sense, consider this. When you write:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

You're basically putting the passed function between each item in the list (yes, + is just a function in many FP languages), so:

[1, 2, 3, 4, 5]

Becomes:

1 + 2 + 3 + 4 + 5

Which equals 15.

Use a map when you want to turn one list into another list.

Use a fold when you want to turn a list into a single value (like summing a list of numbers).

Honestly, once you understand each, you'll realize almost any looping can be replaced by a fold or a map.

It's hard to find good problems that can't be solved with build in functionality. And if it is built in, then it should be used to be an example of good style in language x.

In haskell for example you already have the function (^) in Prelude.

Or if you want to do it more programmaticaly product (replicate y x)

What I'm saying is that it is hard to show the strengths of a style/language if you don't use the features it provides. However it might be a good step towards showing how it works behind the scenes, but i think you should code the best way in whatever language you are using and then help the person from there to understand what is going on if needed.