"Remembering" values in functional programming

Question

I've decided to take upon myself the task of learning functional programming. So far it's been a blast, and I've 'seen the light' as it were. Unfortunately, I don't actually know any functional programmer that I can bounce questions off of. Introducing Stack Exchange.

I'm taking a web/software development course, but my instructor isn't familiar with functional programming. He's fine with me using it, and he just asked me to help him understand how it works so he can read my code better.

I decided the best way to do this would be by illustrating a simple mathematical function, like raising a value to a power. In theory I could easily do that with a prebuilt function, but that would defeat the purpose of an example.

Anyway, I'm having some difficulty figuring out how to hold a value. Since this is functional programming I can't change variable. If I were to code this imperatively, it would look something like this:

(The following is all pseudocode)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

In functional programming, I wasn't sure. This is what I came up with:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Is this right? I need to hold a value, z in both cases, but I wasn't sure how to do this in function programming. In theory, the way I did it works, but I wasn't sure if it was 'right'. Is there a better way to do it?

Answer 1

First of all, congratulations on "seeing the light". You've made the software world a better place by expanding your horizons.

Second, there is honestly no way a professor who doesn't understand functional programming is going to be able to say anything useful about your code, other than trite comments such as "the indentation looks off". This isn't that surprising in a web development course, as most web development is done using HTML/CSS/JavaScript. Depending on how much you actually care about learning web development, you might want to put in the effort to learn the tools your professor is teaching (painful though it may be - I know from experience).

To address the stated question: if your imperative code uses a loop, then chances are your functional code is going to be recursive.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Note that this algorithm is actually more or less identical to the imperative code. In fact, one could consider the loop above to be syntactic sugar for iterative recursive processes.

As a side note, there's no need for a value of z in either your imperative or functional code, in fact. You should have written your imperative function like so:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

rather than changing the meaning of the variable x.

Answer 2

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.

Answer 3

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]

I'll be using numbers in my examples because they lead to easy to read code. Remember though, folds can be used for anything a traditional imperative loop can be used for.

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 returns.

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). The accumulator is the data that's passed while looping. The second argument 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.

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, and adding the initial accumulator onto either the left or right (depending on if it's a left or right fold), so:

[1, 2, 3, 4, 5]

Becomes:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Which equals 15.

Use a map when you want to turn one list into another list, of the same length.

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

As @Jorg pointed out in the comments though, the "single value" need not be something simple like a number; it could be any single object, including a list or a tuple! The way I actually had folds click for me was to define a map in terms of a fold. Note how the accumulator is a list:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

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

Answer 4

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.