"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?

• Mason Wheeler: If you want your example to be taken seriously, have it solve a practical problem rather than a math problem. It's sort of a cliche among developers that "all FP is good for is solving math problems," and if your example is Yet Another Mathematical Function you're only reinforcing the stereotype, instead of making what you're doing look useful.
• 8bittree: Your attempt is actually pretty good when taking into account real world considerations. All of your recursive calls are tail calls, that is, the function does nothing else after calling them. That means that a compiler or interpreter that supports it can optimize them so your recursive function uses a fixed amount of stack memory, rather than an amount proportional to y.
• Ucenna: Thanks a lot for the support! I'm still very new at this, so my pseudocode isn't perfect. @MasonWheeler I guess, in this case my code isn't really meant to be taken seriously. I'm still learning, and the reason I love FP is because it is Math-y. The whole point of my example is to explain to my teacher why I'm using FP. He doesn't really understand what it is, so this seemed like a good way to show him the advantages.
• Carsten S: In which language do you plan to write the code? Don't try to use a style that is not suitable for the language that you are using.
• Ethan Bolker: Possibly useful: en.wikipedia.org/wiki/Memoization

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.

• 8bittree: Your recursive pow isn't quite right. As it is, pow 3 3 returns 81, instead of 27. It should be else x * pow x (y-1).
• gardenhead: Whoops, writing correct code is hard :) Fixed, and I also added type annotations. @Ucenna It's supposed to be SML, but I haven't used it in a while so I might have the syntax slightly wrong. There's too many darn ways to declare a function, I can never remember the right keyword. Besides syntax changes, the code is identical in JavaScript.
• Kasper van den Berg: @jwg Javascript does have some functional aspects: functions can define nested functions, return functions, and accept functions as parameters; it supports closures with lexical scope (no lisp dynamic scope though). It's up to the programmer's discipline to refrain from changing state and mutating data.
• gardenhead: @jwg There is no agreed-upon definition of "functional" language (nor for "imperative", "object-oriented", or "declarative"). I try to refrain from using these terms whenever possible. There are too many languages under the sun to be categorized into four neat groups.
• gardenhead: Popularity is an awful metric, which is why whenever someone mentions that language or tool X must be better because it's so widely used I know continuing the argument would be pointless. I'm more familiar with the ML family of languages than Haskell personally. But I'm also not sure if it's true; my guess would be the vast majority of developers haven't tried Haskell in the first place.

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.

• Carcigenicate: Definitely learn to spot when a problem can be solved by a fold or a map. In FP, nearly all loops can be expressed as fold or a map; so explicit recursion usually isn't necessary.
• Stack Exchange Broke The Law: In some languages, you can just write fold(repeat(base, power), 1, *)
• Jack: Rico Kahler: scan is essentially a fold where instead of just combining the list of values into one value, it is combined and each intermediate value is spit back out along the way, producing a list of all the intermediate states the fold created instead of just producing the final state. It's implementable in terms of fold (every looping operation is).
• Carcigenicate: @RicoKahler And, as far as I can tell, reductions and folds are the same thing. Haskell uses the term "fold", while Clojure prefers "reduce". Their behaviour seem the same to me.
• Jack: @Ucenna: It is both a variable and a function. In functional programming, functions are values just like numbers and strings - you can store them in variables, pass them as arguments to other functions, return them from functions, and generally treat them like other values. So combiner_func is an argument, and sum_all is passing an anonymous function (that's the lambda bit - it creates a function value without naming it) that defines how it wants to combine two items together.

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.

• Carcigenicate: @Ucenna @Ucenna There's a couple flaws with your code (like i never being defined), but I think you have the right idea. One problem with your example is: the function (x), is passed only one element of the list at a time, not the entire list. The first time x is called, it's passed your initial accumulator (y) as it's first argument, and the first element as it's second argument. The next time it's run, x will be passed the new accumulator on the left (whatever x returned the first time), and the second element of the list as it's second argument.
• Carcigenicate: @Ucenna Now that you have the basic idea, look at Jack's implementation again.
• Jack: @Ucenna: Different langs have different preferences for whether the function given to fold takes the accumulator as the first or second argument, unfortunately. One of the reasons it's nice to use a commutative operation like addition to teach folds.
• Jörg W Mittag: "Use a fold when you want to turn a list into a single value (like summing a list of numbers)." – I just want to note that this "single value" can be arbitrarily complex ... including a list! Actually, fold is a general method of iteration, it can do everything iteration can do. E.g. map can be trivially expressed as func map(f, l) = fold((xs, x) => append(xs, f(x)), [], l) Here, the "single value" computed by fold is actually a list.
• Jörg W Mittag: ... possibly want to do with a list, can be done with fold. And it doesn't have to be a list, every collection that can be expressed as empty/not empty will do. Which basically means that any iterator will do. (i guess throwing the word "catamorphism" in there would be too much for a beginner's introduction, though :-D )

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.

• Periata Breatta: In order to logically link this answer to the others, it should be noted that product is just a shortcut function to fold with multiplication as its function and 1 as its initial argument, and that replicate is a function that produces an iterator (or list; as I noted above the two are essentially indistinguishable in haskell) that gives a given number of identical outputs. It should be easy to understand now how this implementation does the same thing as @Jack's answer above, just using predefined special-case versions of the same functions to make it more succinct.