CODEWITHSUNDEEP
f#recursion
Yabert Yanuar
Yabert Yanuar

Reputation: 1027

help me explain this F# recursive example program

let rec aggregateList (f:int->int->int) init list = 
    match list with
    | [] -> init
    | hd::tl -> 
        let rem = aggregateList f init tl
        f rem hd

let add a b = a + b
let mul a b = a * b

//to use in F# Interactive:
//aggregateList add 0 [1..5];;

Got this example from "Functional Programming for the Real world" by Thomas Petricek

I don't understand in second branch in that pattern matching: f rem hd. Could somebody help me?

Upvotes: 1

Views: 461

Answers (3)

Lee
Lee

Reputation: 18747

Let's break down the aggregateList function declaration first. The function takes three parameters:

  1. A function, named f, that takes two ints and returns a third int.
  2. The initial value to start aggregating with.
  3. A list of values.

The function then matches the list it is supplied with one of two possibilities:

  1. The list is empty, in which case it returns the value of init.
  2. The list is not empty, in which case it takes the first item and assigns it to hd (or head) and the rest of the list and assigns it to tl (or tail). Then it performs the recursive call aggregateList f init tl. When that returns, it takes the result and assigns it to rem. Then it calls f on rem and hd.

As other people have pointed out, this does the same thing as the List.foldback function in the basic F# library.

Be careful, of course, to choose the init value properly because if you executed aggregateList mul 0 somelist;; you'll just get 0 no matter what list you supply.

Upvotes: 4

Juliet
Juliet

Reputation: 81526

Just for fun, let's do some printf style debugging:

> aggregateList (fun acc x -> printf "%i " x; acc + x) 0 [1..10];;
10 9 8 7 6 5 4 3 2 1 val it : int = 55

It looks like the function is equivalent to List.foldBack (or fold_right in other languages): it walks each item in the list from right to left and invokes a function f on them.

Let's re-write the function in a few different ways:

// functional version
let rec foldBack f seed = function
    | [] -> seed
    | x::xs -> let res = foldBack f seed xs in f res x

// imperative version
let foldBack f seed xs =
    let mutable result = seed
    for x in List.rev xs do
        result <- f result x
    result

// C# equivalent
public static U FoldBack<T, U>(Func<T, U> f, U seed, IEnumerable<T> xs) {
    foreach(T x in xs.Reverse())
        seed = f(seed, x);
    return seed;
}

You'd use the function like this:

let sum = foldBack (+) 0 [1..10] // returns 55
let sumOfSquares = foldBack (fun acc x -> acc + x * x) 0 [1..10];; // 385

I don't understand in second branch in that pattern matching: f rem hd. Could somebody help me?

So let's start with what we already know about F# functions:

  • f is a function with the type int -> int -> int. You pass functions around as if they were any other variable like ints or strings.
  • You call functions by passing a space-separated list of arguments. f rem hd invokes the function f with two arguments, rem and hd.
  • The last expression evaluated in a function is treated as the function's return value.

So going back to the original function:

let rec aggregateList (f:int->int->int) init list = 
    match list with
    | [] -> init
    | hd::tl -> 
        let rem = aggregateList f init tl   // 1
        f rem hd                            // 2

In line 1, we call aggregateList recusively with tl. Since the list gets smaller and smaller, we're eventually going to hit the nil case, which returns init.

In line 2, f rem hd is the function's return value. However, since we recursed down the stack as we made our way to end of the list, we're going to call this function one for each element (in right-to-left order) as we walk back up the stack trace.

Given aggregateList (+) 0 [1..10], the nil case returns 0, so we call:

  • return value = f rem hd = f 0 10 = 0 + 10 = 10
  • return value = f rem hd = f 10 9 = 9 + 10 = 19
  • return value = f rem hd = f 19 8 = 19 + 8 = 27
  • return value = f rem hd = f 27 7 = 27 + 7 = 34
  • return value = f rem hd = f 34 6 = 34 + 6 = 40
  • return value = f rem hd = f 40 5 = 40 + 5 = 45
  • return value = f rem hd = f 45 4 = 45 + 4 = 49
  • return value = f rem hd = f 49 3 = 49 + 3 = 52
  • return value = f rem hd = f 52 2 = 52 + 2 = 54
  • return value = f rem hd = f 54 1 = 54 + 1 = 55

No more items in the list, so the whole function returns 55.

As you can imagine, the nested calls in aggregateList evaluate like this for a list of length n:

f (f (f (f (f (f (f (f init hdn) hdn-1) hdn-2) hdn-3) ... hd2) hd1) hd0

Upvotes: 1

Guvante
Guvante

Reputation: 19203

It calls the function f (one of the parameters) giving it the result of the recursive call and the next item.

rem is the remainder, or in this case the result of the remainder of the values.

hd is the next item, as seen in the | hd::tl -> part of the pattern matching.

Effectively this aggregate function takes a function, a starting point, and a list. A way of representing the example line is:

(1 + (2 + (3 + (4 + (5 + 0)))))

Upvotes: 1

Related Questions