# The Salty Economist

Things I Should Have Learned in High School

## F# Net Present Value; List.Fold, Head,Tail Recursion

Today's problem is to calculate the present value of an investment stream.

Suppose you had to pay \$1,000 for an investment that returns the following cash flow over its life:

End of Year  1:  \$100.00
End of Year  2:  \$120.00
End of Year  3:  \$125.00
End of Year  4:  \$150.00
End of Year  5:  \$180.00
End of Year  6:  \$200.00
End of Year  7:  \$220.00
End of Year  8:  \$250.00
End of Year  9:  \$290.00
End of Year 10:  \$300.00

If we use a discount rate of 10%, what is the present value of the cash flow?

For those unfamiliar with present value, the math behind the calculation is:

PV = -1,000 + 100/(1.1^1) + 120/(1.1^2) + 125/(1.1^3) + 150/(1.1^4) + 180/(1.1^5) + 200/(1.1^6) + 220/(1.1^7) + 250/(1.1^8) + 290/(1.1^9)+ 300/(1.1^10)

The present value equals the sum of all the flows in each period "discounted" by the interest rate raised to the power n, where n is the number of years from  present.

This is an interesting problem in F# because it let's us explore recursion, the cons operator, and the fold function.

In F#, I find that the approach to solving a problem starts with the littlest details and working back up to the surface.

-------------------------------------------------------

#light
open System

let vals = [-1000.0; 100.0; 120.0; 125.0; 150.0; 180.0; 200.0; 220.0; 250.0; 290.0; 300.0]

let pv (i : float) (n : float) =
1.0 / Math.Pow( (1.0 + i ), n)

let npv v i n =
v * (pv i n)

-------------------------------------------------------

The vals List is our investment stream

The function pv takes i as the annual interest rate and n as the period and calculates the value of \$1.0 discounted back n years.

The function npv takes a value v (say \$100) and multiplies it the present value of \$1 discounted back to present.

As you can see, the problem now is just to apply the npv function to each item in our vals List and them add them up.

Piece of cake.

The following code snippet is a recursive function that takes our vals list as input and iterates over it to create a new list, where each item in the new list is the item in the vals list discounted by the interest rate over the appropriate number of periods:

let rec valList (aList : List<float>) (ir : float) (n : float) =
match aList with
| [] -> []
| h::t -> npv h ir n :: valList t ir (n+1.0)

The parameters are:
aList : List<float> - Our List of vals
ir : float - the interest rate
n : float - period counter.  Initially pass in with a value of 0.0

The match statement says match the vals list against (1) an empty List (as indicated by []) or (2) ??? what the devil is h::t?

We know that h::t uses the 'cons' operator '::' to prepend a value to the head of a list.  So, the F# compiler sees the pattern h::t which is specifically referred to as the 'Cons' pattern.  Any List will match a 'Cons' pattern because all Lists have a head and a tail.  The interesting thing here is that F# makes the match and then automatically fills your variables for the head (h) and tail (t) with those values from the incoming list.  Bizarre, I know, but that's the language.

Here http://msdn.microsoft.com/en-us/library/dd547125(VS.100).aspx is a really good reference on pattern matching.

So, in our statement:

| h::t -> npv h ir n :: valList t ir (n+1.0)

The match is made and h and t are filled in with the values for head and tail of our list aList.

We see on the return side of the statement two expressions connected with another cons operator.  Again, this says take the value of left side expression (whatever that is) and prepend it to the List on the right.

The left expression:

npv h ir n

returns the present value (from the function npv) for the first entry in the list (h), using the interest rate ir, for the period n.  Now, for the first item on the list, n will be zero.  Therefore, the first item is not discounted.  In our example, the first entry is negative \$1,000, so the npv function just returns -\$1,000.

The right expression:

valList t ir (n+1.0)

makes a recursive call to our valList function, passing in the tail (remaining entries) of the current list, the interest rate ir, and the value of n+1 for the number of periods.  Here is where we increment the period counter so that on the second call, the next list value will be discounted one more period.

In our case, the second value is \$100.  Thus, the second call to the valList function calculates the value

npv h ir n

as equal to: \$100 / (1.1 ^ 1) which equals 90.9090...

We then add it to the return list.  We then call varList again, where the head of the tail is now the third entry in vals and the period n is set to 2.

We keep iterating, until we have reached the end of the list.  Ultimately what we return is a new List, where each entry in our original values List has been discounted by our input interest rate over the relevant number of periods.

The next chore is trivial - just add up the new list.

We could do this:

let aList = valList vals 0.10 0.0

let ret0 = List.fold(+)0.0 aList

First, apply varList to our vals list, using an interest rate of 10%.  And then, use the function 'List.fold' to add up the numbers in the list.

Now a Digression

List.fold is a method of the List module is generally used to reduce a List into a single value.  The big question is how do we reduce a List into a single value?  The simplest method is to add it up, but the reduction could be performed using any rule.

The general format of the List.fold method is:

List.fold(someFunction) initialValue someList

The expression:

List.fold(+)0.0 aList

is interpreted as such:

1.  Apply the function addition using as input parameters the current (initial) value and the first element on the list.  Return the value into the current value.

2.  Use the new current value and the second element on the list as the new as input parameters.

3.  Continue to the end of the list.

So, if we had the List:

10, 30, 60

List.fold(+)0.0 would produce the sequence:

0 + 10 = 10
10 + 30 = 40
40 + 60 = 100

and 100 would be our result.

The cool thing is though, we don't have to use addition, but any function that takes two inputs and returns a value

So, if we have a function:

let aFunc x y =
x/100.0+y

We can write:

List.fold(aFunc)0.0

Note: the first argument will always be the current (or initial) value; the second argument will be the next item in the List.

So, the above would yield:

(0/100) + 10 = 10
(10/100) + 30 = 30.1
(30.1/100) + 60 = 60.301

and 60.301 would be our result.

Back to the Show

So we have seen that

let ret0 = List.fold(+)0.0 aList

will add up our list of discounted values and return them in out final result ret0.

But, ultimately what I want is just a function that I can can with a List and a discount rate and return a present value.  Here is what I have come up with:

let presentValue (vals : List<float>) (ir : float) =
List.fold(+)0.0 <| valList vals ir 0.0

This function just collapses the logic into one function called presentValue.

In the snippet above the '<|' operator passes the result of

valList vals ir 0.0

into the List.fold method, thereby skipping the creation of an intermediate List.

Now, I have what I want.  I can now call my function in an intelligible fashion:

let ret1 = presentValue vals 0.10

I can now get my present value with no hassle (returned in ret1).  The next thing to do is carve out all my code, put it into a math module and stop worrying about the ugly details.

Here the full program:

#light
open System
open System.Collections.Generic
open System.IO

let vals = [-1000.0; 100.0; 120.0; 125.0; 150.0; 180.0; 200.0; 220.0; 250.0; 290.0; 300.0]

let pv (i : float) (n : float) =
1.0 / Math.Pow( (1.0 + i ), n)

let npv x i n =
x * (pv i n)

let rec valList aList (ir : float) (n : float) =
match aList with
| [] -> []
| h::t -> npv h ir n :: valList t ir (n+1.0)

let presentValue vals (ir : float) =
List.fold(+)0.0 <| valList vals ir 0.0

let ret1 = presentValue vals 0.12

Print | posted on Thursday, July 9, 2009 11:54 AM |