I am still learning about F# and functional programming. In all honesty, I wished I had known about this type of programming a long time ago. Had I started with at least OCaml, F# and Haskell would be no problem at all. But, the past is the past and I am just glad I have the opportunity to work with F# now.
Also, I am almost done reading/working on F# for Scientists and it is a great book. Actually, it helped me bridge some gaps in the material I had to deal with in both Foundations of F# and Expert F#. Right now, I would like to use the Powerset example presented in F# for Scientists to basically explain what is going on, as others looking at this and similar problems may get confused. In all fairness, it took me a little bit to understand what was going on and what the solution was.
First, let us take a look at one implementation to generate a powerset and the results of running the function:
1 let rec powerset = function
2 | [] -> [[]]
3 | h::t ->
4 [ for x in powerset t do
5 for t in [x;h::x] -> t
6 ]
7 // Example: calling powerset on the list [1;2;3]:
8 powerset [1;2;3]
9
10 // Results:
11 // val it : int list list = [[]; [1]; [2]; [1; 2];
12 // [3]; [1; 3]; [2; 3]; [1; 2; 3]]
As you can see, the code is succinct, but may not be as clear on the first glance. Notice we have recursion plus nested for loops which all together can be a bit of an issue to navigate through. So first, I will add some printfn statements to help illustrate how the code is executed. In this case, I will use a simpler list of values because once you can successfully understand a list of two elements, you can extend that to longer lists. I am trying to make this as detailed as possible so that there are no hang ups along he way.
1 let rec powerset = function
2 | [] ->
3 printfn "%s" "Match Pattern 1"
4 [[]]
5 | h::t ->
6 printfn "%s%A%s%A"
7 "Before powerset t/for#1: h = " h "\t t = " t
8 [ for x in powerset t do
9 printfn "%s%A" "After for#1/Before for#2: x = " x
10 for t in [x;h::x] ->
11 printfn "%s%A%s%A"
12 "After for#2: [x;h::x] = " [x;h::x] " t = " t
13 t
14 ]
15 // Example:
16 powerset [1;2]
17
18 // Signature:
19 val powerset : 'a list -> 'a list list
20
21 // Results
22 Before powerset t/for#1: h = 1 t = [2]
23 Before powerset t/for#1: h = 2 t = []
24 Match Pattern 1
25 After for#1/Before for#2: x = []
26 After for#2: [x;h::x] = [[]; [2]] t = []
27 After for#2: [x;h::x] = [[2]; [2; 2]] t = [2]
28 After for#1/Before for#2: x = []
29 After for#2: [x;h::x] = [[]; [1]] t = []
30 After for#2: [x;h::x] = [[1]; [1; 1]] t = [1]
31 After for#1/Before for#2: x = [2]
32 After for#2: [x;h::x] = [[2]; [1; 2]] t = [2]
33 After for#2: [x;h::x] = [[1; 2]; [1; 1; 2]] t = [1; 2]
34 val it : int list list = [[]; [1]; [2]; [1; 2]]
I take it for granted that you understand the basic structure of a function in F# as well as recursion and lists. I will do another post sometime soon to address lists and all that fun stuff.
Let's try to get a general overview of what is going on. Take a look at the first code without the additional markup. We are basically performing a matching operation on the argument passed to the function, and each match produces a different result.
[1] If the user passed in an empty list, denoted by [] as the argument, then the first match statement is executed and the function returns an empty list of lists, denoted by [[]].
[2] If the input is a list containing items, then the second match is executed. The first thing that happens is that the head of the list is removed via the construct h::t and the tail portion is used as the argument to call the function again, i.e. recursion. Once the recursion is done, the for loops are executed and the result is calculated from that.
In this example, we will be using the list [1;2] as the argument to the powerset function and step through each iteration as the function is executed.
Note:
for#1 refers to the outer for loop in Line 8
for#2 refers to the nested for loop in Line 10
- Test if the input is an empty list -> [1;2] is not empty, so go to pattern#2
- Remove the head of the list and return the result of calling powerset on the remaining tail portion of the list
- From Line 22, we have the head, h = 1 and the tail, t = [2], and we want to execute for#1 with the result of calling powerset [2]
- We don't know what the value of powerset [2] is, so recurse
- Test if the input is an empty list -> [2] is not empty, so go to pattern#2
- Remove the head of the list and return the result of calling powerset on the remaining tail portion of the list
- From Line 23, we have the head, h = 2 and the tail, t = [], and we want to execute for#1 with the result of calling powerset []
- We don't know what the value of powerset [] is, so recurse
- Test if the input is an empty list -> [] is an empty list, so go to pattern#1 (Line 24)
- Pattern#1 matches the empty input list and returns an empty list of lists, denoted by [ [] ]
- Now that we know what the value of powerset [] is we can go back to Call 2
- Call 2 basically said that in order to proceed, we need to know what powerset [] is which we do, so the rest of the code can be executed, namely the two for loops
- Begin executing for#1 because we now know the value of powerset [] which is [ [] ]
- Essenitally, at this point Line 8 looks like: for x in [ [] ]and the type of the variable x used to iterate the for loop is a list
- Iteration 1: (Line 25)
Since there is only one list to iterate through, this loop will only execute once and we know that the value of x is just an empty list - Begin executing for#2 (Line 10)
[for i in [1;2;3;4] -> i*i]
// > val it : int list = [1; 4; 9; 16]
// Return a list of integers
// Go through and return the square of each int
[for x in [ []; [3;2]; [0;1;2] ] -> x]
// > val it : int list list = [[]; [3; 2]; [0; 1; 2]]
// Return a list containing lists of integers
// Go through and return each list
- The nested for loop, for#2 bears a similar construct as the previous loop
- The loop variable, t is also of type list and we are using the list returned from for#1 to create a new list with two lists, [x;h::x] to iterate through
- To create the list of lists for for#2 to loop through, we need to know the values of x and h which we can get from Lines 23 & 25
- Build the list that for#2 will loop: [x;h::t] becomes [[]; 2::[]]
- h::t is the cons operator in F# which is just adding an element to the head of a list so 2::[] is adding an element to the head of an empty list, therefore 2::[] becomes [2]
- Essentially, at this point Line 10 looks like:
for x in [[];[2]] do
- for#2 will execute twice since there are two lists to iterate through (Lines 26, 27)
- This is where it gets a bit tricky, because for each of the list in the list of lists, we are creating a new list, based on the pattern [x; h::x] and returning the list the iterator is currently 'pointing' to
- Therefore, when t is pointing to the first list in [x; h::x], which is [x], it creates a new list that looks like [x; h::x]; and when it is pointing to h::x, it creates a new list which looks like [h::x; h::h::x] (Lines 26 & 27)
- Let us examine each iteration of for#2:
Nested Iteration 1.1: (Line 26)- from for#1, we know that x = [] and from Line 23, h = 2 when x = []
- create the pattern [x; h::x] which is [ []; 2::[] ] = [ []; [2] ]
- return the first list from that result, which is []
- iterator now moves to the second list in the list of lists created in Iteration 1.1, which is [h::x] and creates a new list based on the pattern [x; h::x] meaning that the list we are currently pointing to is the first list in the pattern, and the second list in the pattern is a modified version of our current list
- when t = [h::x] we have [h::x; h::h::x]
- all parameters are known so [h::x; h::h::x] becomes [[2]; 2::[2]] = [ [2]; [2;2] ] as seen in Line 27
- return the first list from [[2];[2;2]] which is [2]
- we have now successfully determined the results of
- now that we have exhausted the loop, go back to Call 2 because we now know that the value of calling powerset [2] is the list we just obtained, namely [ []; [2] ]
- In summary, Call 3 provided the solution to Call 2 and Call 2 provided the solution to Call 1
- In order to complete Call 1 we needed to know what the value of powerset [2] is, which we now know to be [ []; [2] ]
- We are back at Line 8 which in Call 1 looked something like:
for x in powerset [2]
- powerset [2] is known so this loop actually looks like:
for x in powerset [[];[2]]
- Therefore, for#1 will execute two times, and each list in [ []; [2] ] executes twice as shown in Lines 28-33
- Iteration 1: (Line 28)
The iterator, x currently refers to the first list in [[];[2]] which is [] - Begin executing for#2 with x = [], h = 1
- Let us examine each iteration of for#2:
Nested Iteration 1.1: (Line 29)- following the same procedure as given in the Call 2 Revisited section, create a list based on the pattern [x;h::x] where x is the current list being operated on in for#1
- again, for#2 creates a list of lists, and for each of these lists created, build two more lists based on the pattern given in the point above
- for x = [] and h = 1 we have [x;h::] = [ []; 1::[] ] = [ []; [1] ] as given in Line 29
- at this point Line 10 looks like:
for t in powerset [[];[1]]
- return the first list from that result, which is []
- the iterator, t now moves to the second list in the list of lists [[];[1]] which is [1]
- now create a new list based on the pattern [x;h::x] which in this case becomes [h::x; h::h::x]
- from Line 29 we know that h::x = 1::[1] = [1;1]
- now we have [ [1];[1;1] ] and return the first list, which is [1]
- Iteration 2: (Line 31)
The iterator, x now refers to the second list in [ []; [2] ] which is [2] - Begin executing for#2 with x = [2], h = 1
- Let us examine each iteration of for#2:
Nested Iteration 2.1: (Line 32)- create a list based on the pattern [x;h::x] where x is the current list being operated on in for#1, in this case x = [2]
- for x = [2] and h = 1 we have [x;h::x] = [ [2]; 1::[2] ] = [ [2]; [1;2] as given in Line 32
- return the first list from that result, which is [2]
- the iterator, t now moves to the second list in the list of lists [[2];[1;2]] which is [1;2]
- now create a new list based on the pattern [x;h::x] which in this case becomes [h::x; h::h::x]
- from Line 29 we know that h::x = 1::[1;2] = [1;1;2]
- now we have [ [1;2];[1;1;2] ] and return the first list, which is [1;2]
- Recall that no recursion took place during this entire revisit to Call 1, so the answer is basically the values returned from each for loop running to completion which is given in Line 34
- So the final answer is acheieved by creating a list, and within that list, prepend successive results from each for loop which is [ []; [1]; [2]; [1;2] ]
No comments:
Post a Comment