程式扎記

轉載自這理
前言 :
在 JavaScript 中，函式是物件，是 Function 的實例，可以在變數間任意指定，可以傳給函式的參數參考，當然，要新增為物件的特性也是可以的。例如 :

> var p1 = { name : 'Justin', age : 35 };
> var p2 = { name : 'momor', age : 32 };
> function toString(){ return '[' + this.name + ',' + this.age + ']'; }
> p1.toString = toString; // 新增一個 toString 的成員到 p1.
> p2.toString = toString; // 新增一個 toString 的成員到 p2.
> p1.toString();
[Justin,35]
> p2.toString();
[momor,32]

在上例中定義了一個 toString() 函式，並分別設定為 p1 與 p2 的 toString 來參考，透過 p1, p2 呼叫時，toString() 就像是 p1, p2 的方法（Method）.

this 是什麼 :
在上例中，toString() 函式中使用了this，在呼叫函式時，每個函式都會有個 this，然而 this 參考至哪個物件，其實依呼叫方式而有所不同。以上例而言，透過 p1 呼叫時，toString() 中的 this 會參考至 p1 所參考的物件，也因此顯示 p1 物件的 name 與 age 值，透過 p2 呼叫時，toString() 中的 this 則會參考至 p2 所參考的物件. 如果呼叫函式時是透過物件與點運算子的方式呼叫，則 this 會參考至點運算子左邊的物件. 在 JavaScript 中，函式是 Function 的實例，Function 都會有個 call() 方法，可以讓你決定 this 的參考對象. 舉例來說，你可以如下呼叫 :

> var p1 = { name : 'Justin', age : 35 };
> var p2 = { name : 'momor', age : 32 };
> function toString(){ return '[' + this.name + ',' + this.age + ']'; }
> toString.call(p1);
[Justin,35]
> toString.call(p2);
[momor,32]

這次並沒有將 toString 指定為物件的特性，而是直接使用 call() 方法來呼叫函式，call() 方法的第一個參數就是用來指定函式中的 this 所參考的物件。如果函式原本具有參數，則可接續在第一個參數之後. 例如 :

> function add(n1, n2){ return this.n + n1 + n2; }
> var o = { n : 10 };
> add.call(o, 20, 30);
60

Function 也有個 apply() 方法，作用與 call() 方法相同，也可讓你在第一個參數指定 this 所參考的對象，不過 apply() 方法指定後續引數時，必須將引數收集為一個陣列，如果你有一組引數，必須在多次呼叫時共用，就可以使用 apply() 方法. 例如 :

> function add(n1, n2){ return this.n + n1 + n2; }
> var o1 = { n : 10 };
> var o2 = { n : 100 };
> var args = [20, 30]; // 定義引數陣列
> add.apply(o1, args);
60
> add.apply(o2, args);
150

所以，this 實際參考的對象，是以呼叫方式而定，而不是它是否附屬在哪個物件而定. 例如就算函式是附屬在函式上的某個特性，也可以這麼改變 this 所參考的對象 :

> var p1 = { name : 'Justin' };
> var p2 = { name : 'momor' };
> function toString(){ return this.name; }
> p1.toString = toString;
> p2.toString = toString;
> p1.toString();
Justin
> p2.toString();
momor
> p1.toString.call(p2);
momor

在最後一個測試中，是以 p1.toString.call(p2) 的呼叫方式，所以雖然 toString() 是 p1 的特性，但 call() 指定 this 是參考至 p2，結果當然也是傳回 p2 的 name.

在用物件實字建立物件時，也可以直接指定函式作為特性. 例如 :

js> var o = {
> name : 'John',
> toString : function() {
> return this.name;
> }
> };
> o.toString();
John

由於頂層函式是全域物件上的特性，所以作為一個頂層函式呼叫時，this 會參考至全域. 例如 :

js> function func() {
> return this;
> }
> func() == this;
true
> this.func() == this;
true

當一個內部函式直接被呼叫時，this 也是參考至全域物件. 例如 :

> function func() {
> function inner() {
> return this;
> }
> return inner();
> }
> func() == this;
true
> var o1 = { func : func };
> o1.func() == o1;
false
> o1.func() == this;
true
> func.call(o1) == this;
true

在上例中，最後一個例子雖然指定外部函式的 this 為 o1，但事實上，內部函式被呼叫時，this 仍是參考至全域物件. 如果是以下這個例子 :

> function func() {
> function inner() {
> return this;
> }
> this.inner = inner;
> return this.inner();
> }
> func() == this;
true
> var o1 = { func : func };
> o1.func() == o1;
true
> o1.func.call(this) == this;
true
> o1.func.call(o1) == o1;
true

JavaScript 執行過程中，搞清楚 this 是誰有時非常重要，this 的決定方式是在於呼叫，而非定義的方式! 舉個例子來說，如果你想要自行實現 Array 的 forEach 方法，則可以如下 :

> var obj = {
> '0' : 100,
> '1' : 200,
> '2' : 300,
> length : 3,
> forEach : function(callback) {
> for(var j = 0; j < this.length; j++) {
> callback(this[j]);
> }
> }
> };
> obj.forEach(function(element) {
> print(element);
> });
100
200
300

在上例中，由於呼叫 forEach 時，obj 參考的物件就是 this 所參考的物件，因而可以取得 length 等特性，函式是物件，所以自然可以丟給 forEach 作為引數，這也就是陣列中介紹到 Array上 forEach 方法的實作原理.

This message was edited 16 times. Last update was at 26/12/2017 13:51:09

Source From Here
前言 :
在 JavaScript 中，函式是物件，是 Function 的實例. 因為是 Function 實例，你可以將之傳給另一個變數參考. 例如 :

> function max(n1, n2) { return n1 > n2 ? n1: n2; }
> var maximum = max;
> max(10, 20);
20
> maximum(10, 20);
20

注意，在將 max 指定給 maximum 時，max 後並沒有加上 () 運算子，這表示要將 max 參考的物件指定給 maximum 參考（加上括號表示要執行函式）。將一個函式指定給變數，這看來如果覺得奇怪的話，或許下這個看來比較不奇怪 :

> var maximum = function max(n1, n2){ return n1 > n2 ? n1:n2; }
> var maximum = max;
> max(1, 2);
2
> maximum(1, 2);
2

上面你所看到的函式撰寫方式，稱之為 函式實字（Function literal），這就像你寫下一個數值實字、物件實字或陣列實字，會產生數值或物件等 :

view plaincopy to clipboardprint?
var number = 10;  
var obj = { x : 10 };  
var array = [1, 2, 3];  
var func = function() {  
    // do something...  
};  

Function 實例介紹 :
函式實字會產生 Function 的實例，在 JavaScript 中，無論是函式宣告或函式實字，都會產生 Function 的實例。事實上，你也可以直接指定建立 Function 的實例 :

> var max = new Function('num1', 'num2', 'return num1 > num2 ? num1 : num2');
> max(5, 6);
6

基本上，實務上很少會直接建立 Function 實例，以上只是表示，函式確實是 Function 實例. 即然函式是物件，它就可以任意指定給其它變數，也就可以指定作為另一個函式的引數，那它就不僅能被呼叫，還可以主動要求另一個函式執行所指定的函式內容. 例如 :

> var printIt = function(element){ console.log(element); }
> [1, 2, 3].forEach(printIt);
1
2
3
> var comparator = function(n1, n2) { return n1 - n2; }
> [5, 1, 7, 3, 2].sort(comparator);
1,2,3,5,7

上例以 Array 為例，forEach 可以對陣列的每個元素作「某些事」，「某些事」是由你使用函式來指定，陣列會逐一將元素傳入給你指定的函式作為引數。 sort 則可以進行排序，但兩個元素的大小關係要由你告知，傳回正值表示傳入的 n1 順序上大於 n2，要排在 n2 的後面，傳回 0 表示兩個順序相同，傳回負值表示 n1 順序上小於 n2，要排在 n2 的前面. 像這種將函式主動丟入函式作為引數，在 JavaScript 中是很常見到的應用。事實上，若不需要名稱，你也可以如下 :

> [1, 2, 3].forEach(function(e){ console.log(e); })
1
2
3
> [5, 1, 7, 3, 2].sort(function(n1, n2){ return n1 - n2; })
1,2,3,5,7

你也可以從函式中傳回函式，這通常會形成閉包（Closure）綁定某些運算過後的資源，再傳回函式，這之後還會再談到應用. 以函式實字所建立的 Function 實例，在指定給別的變數前，稱為所謂的匿名函式（Anonymous function）。你可以完全不使用名稱來執行函式 :

> (function() {
> print('anonymous function...');
> })();
anonymous function...

實際上，函式實字也可以指定名稱. 例如 :

> var maximum = function max(num1, num2) {
> return num1 > num2 ? num1 : num2;
> };
> maximum(10, 20);
20
> max(10, 20);
js: "", line 6: uncaught JavaScript runtime exception: ReferenceError: "max" is not defined.
at :6

上例中，函式實字所建立的 max 名稱，似乎不能使用，事實上，這種語法適用於使用函式實字建立 Function 實例，但又需遞迴的場合. 例如 :

> var gcd = function g(n1, n2){ return n2!=0? g(n2, n1%n2):n1; } // 計算最大公因數
> gcd(10, 5);
5

在一個匿名函式中，如果想取得本身實例，可以藉由 arguments 的 callee 來取得. 例如 :

> var gcd = function(num1, num2) {
> return num2 != 0 ? arguments.callee(num2, num1 % num2) : num1;
> };
> gcd(20, 10);
10

函式既然是物件，本身亦可擁有特性. 例如函式有個 length 特性，代表其參數個數 :

> var gcd = function (n1, n2){ return n2!=0? arguments.callee(n2, n1%n2):n1; }
> gcd.length;
2

函式也可以擁有方法，這個之後再談，你也可以在其上新增特性或方法，就如同一個普通的物件. 函式宣告與函式宣告在運用上，幾乎是相同的，但還是有細微的差別。例如，你若寫一個 f.js 檔案如下 :

view plaincopy to clipboardprint?
func();  
function func() {  
    print('func');  
}  

直接使用 Rhino 直譯器載入執行的話或是 node js，可以正常執行 :

your_workspace> java org.mozilla.javascript.tools.shell.Main f.js
func

# node f.js
func

但如果你的f.js如下 :

view plaincopy to clipboardprint?
func();  
var func = function() {  
    print('func');  
};  

你會得到錯誤的訊息 :

your_workspace> java org.mozilla.javascript.tools.shell.Main f.js
js: uncaught JavaScript runtime exception: TypeError: func is not a function, it is undefined.

錯誤訊息告訴你，func 值是undefined. 原因在於，直譯器在載入 .js 時，會先處理所有的宣告，包括變數與函式宣告，接著再執行程式. 所以在第一個 f.js 中，是以函式宣告方式，直譯器已處理完成，因此接下來再執行時，就可以找到func 所參考的函式。而在第二個 f.js中，僅宣告了 func 變數，直譯器處理完這個宣告後，接下來要執行程式時，範圍中可以看到 func 變數，但此時還沒有指定值給 func，所以是 undefined，因此不能完成函式的執行.

雖然不重要，但還是提一下的是，以上兩種方式，在遇到要建立函式實例時，都不會再重新直譯，但如果你以直接建構 Function 實例的方式，則每次都會針對你引數的字串再作直譯動作. 函式宣告方式所建立的函式名稱，其實也是範圍物件上的特性名稱. 例如若在全域範圍宣告 :

> function func() { print('func'); }
> func();
func
> this.func();
func

可以看到，func 名稱是全域物件上的特性!

Source From Here
前言 :
對於要重複執行的內容，你可以定義函式. 例如 :

> function max(num1, num2) {
> return num1 > num2 ? num1 : num2;
> }
> max(10, 5);
10

在上面的例子示範了函式的基本宣告與呼叫方式. 函式使用 function 宣告名稱，參數位於括號之中，使用 return 傳回執行結果，如果沒宣告return傳回任何結果，預設傳回undefined.

函式宣告介紹 :
在函式上的參數宣告，只是傳入引數的具名參考，實際上，宣告函式時若傳入的引數少於參數是可行的，不足的部份，參數就是undefined :

> function func(a, b) { console.log(a); console.log(b) }
> func(10, 20);
10
20
> func(10);
10
undefined
> func();
undefined
undefined
> func(10, 20, 30, 40); // 給超過參數定義的引數
10
20

在上例中，你也看到了，就算傳入比參數個數還多的引數也是可行的，那多的引數跑到哪去了？事實上，在函式內部會自動宣告 arguments 名稱參考至具陣列外觀的物件，上頭帶有所有傳入的引數. 例如，你可以如下設計一個加總數值的函式 :

> function sum(){ var sum=0; for(var j=0; j
> sum(1, 2);
3
> sum(1, 2, 3);
6
> sum(1, 2, 3, 4);
10

arguments 不是 Array 實例，它只是具有數字作為特性，特性參考至傳入的引數，並具有 length 特性代表傳入引數的個數. 在 JavaScript 中，參數只是具名的引數，事實上，你改變參數的值，arguments 對應索引的參考值也會相應的改變 :

js> function func(a, b) {
> print(a + ': ' + arguments[0]);
> print(b + ': ' + arguments[1]);
> a = 0;
> b = 0;
> print(a + ': ' + arguments[0]);
> print(b + ': ' + arguments[1]);
> }
js> func(100, 200);
100: 100
200: 200
0: 0
0: 0

由於呼叫函式時傳入的引數個數不一定要等於參數個數，因此若要確認引數等於參數個數，可透過 arguments 的 length 來檢查傳入的引數個數. 例如 :

> function func(a, b){ if(arguments.length!=2) { throw new Error('must give 2 arguments'); } }
> func(10);
js: "", line 40: exception from uncaught JavaScript throw: Error: must give 2 arguments
at :40 (func)
at :39

事實上，在 JavaScript 程式設計上的慣例，很少檢查引數個數，而是在引數不足時提供預設值，這很容易辦到，因為引數不足時，不足的參數會是 undefined，而 undefined 在判斷式中會被當 false，所以可以撰寫如下來提供預設值 :

> function numberGenerator(length, begin, step) {
> begin = begin || 0;
> step = step || 1;
> var numbers = [begin];
> length--;
> for(var j = 0; j < length; j++) {
> numbers.push(numbers[j] + step);
> }
> return numbers;
> }
> numberGenerator(10);
0,1,2,3,4,5,6,7,8,9
> numberGenerator(10, 5);
5,6,7,8,9,10,11,12,13,14
> numberGenerator(10, 5, 2);
5,7,9,11,13,15,17,19,21,23

在上例是一個數值產生器，length 一定要提供，若不提供 begin 的話，預設起始值就是 0，若不提供 step 的話，步進值就是1.
如果在選項非常多時，還會採用選項物件（Option object）的方式. 例如 :

> function func(option) {
> option = {
> x : option.x || 10,
> y : option.y || 20,
> z : option.z || 30
> };
> print(option.x);
> print(option.y);
> print(option.z);
> }
> func({ x : 100 });
100
20
30
> func({ x : 100, y : 200 });
100
200
30
> func({ x : 100, y : 200, z : 300 });
100
200
300

在上例中，呼叫函式時必須提供物件，物件上帶有函式所需的資料，函式內部對於物件上沒有提供資料時，會提供預設值.

Using recursion to fold lists with higher-order functions
In chapter 3, you learned how to fold lists, and folding applies to immutable lists as well. But with mutable lists, you had the choice to implement these operations through iteration or recursively. In chapter 3, you implemented folds iteratively because you were using mutable lists, where adding and removing elements was done in place by nonfunctional methods. The add method returned nothing, and the remove method returned only the removed element, while modifying the list argument. Because immutable lists are recursive data structures, you can very easily use recursion to implement folding operations.
Let’s consider common folding operations on lists of numbers.

Exercise 5.7
Write a functional method to compute the sum of all elements of a list of integers using simple stack-based recursion. The recursive definition of the sum of all elements of a list is

* For an empty list: 0
* For a non-empty list: head plus the sum of the tail

This translates nearly word-for-word into Java code:

view plaincopy to clipboardprint?
public static Integer sum(List ints) {  
    return ints.isEmpty()  
            ? 0  
            : ints.head() + sum(ints.tail());  
}  

Don’t forget that this implementation will overflow the stack for long lists, so don’t use this kind of code in production.

Exercise 5.8
Write a functional method to compute the product of all elements of a list of doubles using simple stack-based recursion. The recursive definition of the product of all elements of a non-empty list is

* For an empty list: 1.0
* For a non-empty list: head * product of tail

Consider what will happen when you’ve applied the recursive formula to all elements. You’ll end up with a result that will have to be multiplied by the product of all elements of an empty list. Because you want to eventually get this result, you have no choice but to say that the product of all elements of an empty list is 1. This is the same situation as with the sum example, when you use 0 as the sum of all elements of an empty list. The identity element, or neutral element, for the sum operation is 0, and the identity or neutral element for the product is 1. So your product method could be written as follows:

view plaincopy to clipboardprint?
public static Double product(List ds) {  
    return ds.isEmpty()   
            ? 1.0   
            : ds.head() * product(ds.tail());  
}  

Note that the product operation is different from the sum operation in one important way. It has an absorbing element, which is an element that satisfies the following condition:

a × absorbing element = absorbing element × a = absorbing element

The absorbing element for multiplication is 0. By analogy, the absorbing element of any operation (if it exists) is also called the zero element. The existence of a zero element allows you to escape the computation, also called short circuiting:

view plaincopy to clipboardprint?
public static Double product(List ds) {  
    return ds.isEmpty()   
            ? 1.0   
            : ds.head() == 0.0   
                ? 0.0   
                : ds.head() * product(ds.tail());  
}  

But forget about this optimized version and look at the definitions for sum and product. Can you detect a pattern that could be abstracted? Let’s look at them side by side (after having changed the parameter name):

view plaincopy to clipboardprint?
public static Integer sum(List list) {  
  return list.isEmpty()  
      ? 0  
      : list.head() + sum(list.tail());  
}  
  
public static Double product(List list) {  
  return list.isEmpty()  
      ? 1  
      : list.head() * product(list .tail());  
}  

Now let’s remove the differences and replace them with a common notation:

view plaincopy to clipboardprint?
public static Type operation(List list) {  
  return list.isEmpty()  
      ? identity  
      : list.head() operator operation(list .tail());  
}  
  
public static Type operation(List list) {  
  return list.isEmpty()  
      ? identity  
      : list.head() operator operation(list .tail());  
}  

The two operations are nearly the same. If you can find a way to abstract the common parts, you’ll just have to provide the variable information (Type, operation, identity, and operator) to implement both operations without repeating yourself. This common operation is what we call a fold, which you studied in chapter 3. In that chapter, you learned that there are two kinds of folds—right fold and left fold—as well as a relation between these two operations.

Listing 5.2 shows the common parts of the sum and product operations abstracted into a method called foldRight, taking as its parameters the list to fold, an identity element, and a higher-order function representing the operation used to fold the list. The identity element is obviously the identity for the given operation, and the function is in curried form. (See chapter 2 if you don’t remember what this means.) This function represents the operator portion of your code.
Listing 5.2. Implementing foldRight and using it for sum and product

view plaincopy to clipboardprint?
public static  B foldRight(List list, B n, Function> f)  
{  
    return list.isEmpty()  
            ? n  
            : f.apply(list.head()).apply(foldRight(list.tail(), n, f));  
}  
  
public static Integer sum(List list)  
{  
    return foldRight(list, 0, x -> y -> x + y);  
}  
  
public static Double product(List list)  
{  
    return foldRight(list, 1.0, x-> y-> x * y);  
}  

Note that the Type variable part has been replaced with two types here, A and B. This is because the result of folding isn’t always of the same type as the elements of the list. Here, it’s abstracted a bit more than is needed for the sum and product operations, but this will be useful soon. The operation variable part is, of course, the names of the two methods.

The fold operation isn’t specific to arithmetic computations. You can use a fold to transform a list of characters into a string. In such a case, A and B are two different types: Char and String. But you can also use a fold to transform a list of strings into a single string. Can you see now how you could implement concat? By the way, foldRight is very similar to the singly linked list itself. If you think of the list 1, 2, 3 as

view plaincopy to clipboardprint?
Cons(1, Cons(2, Cons(3, Nil)  

you can see immediately that it’s very similar to a right fold:

view plaincopy to clipboardprint?
f(1, f(2, f(3, identity)  

But perhaps you’ve already realized that Nil is the identity for adding elements to lists. This make sense: if you want to transform a list of characters into a string, you have to start with an empty list. (By the way, Nil is also the identity for list concatenation, although you could do without it, provided the list of lists to be concatenated isn’t empty. In such a case, it’s called a reduce rather than a fold. But this is possible only because the result is of the same type as the elements.) This can be put in practice by passing Nil and cons to foldRight as the identity and the function that are used to fold:

view plaincopy to clipboardprint?
List.foldRight(list(1, 2, 3), list(), x -> y -> y.cons(x))  

This simply produces a new list with the same elements in the same order, as you can see by running the following code:

view plaincopy to clipboardprint?
System.out.println(List.foldRight(list(1, 2, 3), list(),  
                                               x -> y -> y.cons(x)));  

This code produces the following output:

[1, 2, 3, NIL]

Here’s a trace of what’s happening at each step:

foldRight(list(1, 2, 3), list(), x -> y -> y.cons(x));
foldRight(list(1, 2), list(3), x -> y -> y.cons(x));
foldRight(list(1), list(2, 3), x -> y -> y.cons(x));
foldRight(list(), list(1, 2, 3), x -> y -> y.cons(x));

Now let's write a method to compute the length of a list. This method will use the foldRight method (Exercise 5.9). The Nil implementation is obvious and returns 0. The Cons implementation may be written as:

view plaincopy to clipboardprint?
public int length() {  
  return foldRight(this, 0, x -> y -> y + 1);  
}  

Note that this implementation, beside being stack-based recursive, has very poor performance. Even if transformed to heap-based, it’s still O(n), meaning the time needed to return the length is proportional to the length of the list. In following chapters, you’ll see how to get the length of a linked list in constant time.

The foldRight method uses recursion, but it’s not tail recursive, so it will rapidly overflow the stack. How rapidly depends on several factors, the most important of which is the size of the stack. In Java, the size of the stack is configurable through the -Xss command-line parameter, but the major drawback is that the same size is used for all threads. Using a bigger stack would be a waste of memory for most threads.

Instead of using foldRight, create a foldLeft method that’s tail recursive and can be made stack-safe. Here’s its signature (Exercise 5.10):

view plaincopy to clipboardprint?
public abstract  B foldLeft(B identity, Function> f);  

The Nil implementation will obviously return identity. For the Cons implementation, start with defining a front-end method foldLeft calling a stack-based tail recursive helper method foldLeft_ with an accumulator acc initialized to identity and a reference to this:

view plaincopy to clipboardprint?
public  B foldLeft(B identity, Function> f) {  
  return foldLeft_(identity, this, f);  
}  
  
private  B foldLeft_(B acc, List list,  
                                    Function> f) {  
  return list.isEmpty()  
      ? acc  
      : foldLeft_(f.apply(acc).apply(list.head()), list.tail(), f);  
}  

Then make the following changes so you can use the TailCall interface you defined in chapter 4 (the ret and sus methods are imported statically):

view plaincopy to clipboardprint?
public  B foldLeft(B identity, Function> f) {  
    return foldLeft_(identity, this, f).eval();  
}  
  
private  TailCall foldLeft_(B acc, List list, Function> f) {  
    return list.isEmpty()  
              ? ret(acc)  
              : sus(() -> foldLeft_(f.apply(acc).apply(list.head()),  
                                                       list.tail(), f));  
}  

Use your new foldLeft method to create new stack-safe versions of sum, product, and length (Exercise 5.11).

view plaincopy to clipboardprint?
public static Integer sumViaFoldLeft(List list) {  
    return list.foldLeft(0, x -> y -> x + y);  
}  
  
public static Double productViaFoldLeft(List list) {  
    return list.foldLeft(1.0, x -> y -> x * y);  
}  
  
public static  Integer lengthViaFoldLeft(List list) {  
    return list.foldLeft(0, x -> ignore -> x + 1);  
}  

Note that once again, the second parameter of method length (representing each element of the list on each recursive call of the method) is ignored. This method is as inefficient as the previous one and shouldn’t be used in production code.

Let's use foldLeft to write a static functional method for reversing a list (Exercise 5.12). Reversing a list via a left fold is very simple, starting from an empty list as the accumulator and cons-ing each element of the first list to this accumulator:

view plaincopy to clipboardprint?
public static  List reverseViaFoldLeft(List list) {  
  return list.foldLeft(list(), x -> x::cons);  
}  

This example uses a method reference instead of a lambda, as explained in chapter 2. If you prefer to use a lambda, it’s equivalent to the following:

view plaincopy to clipboardprint?
public static  List reverseViaFoldLeft(List list) {  
  return list.foldLeft(list(), x -> a -> x.cons(a));  
}  

Let's write foldRight in terms of foldLeft (Exercise 5.13). This implementation can be useful for getting a stack-safe version of foldRight:

view plaincopy to clipboardprint?
public static  B foldRightViaFoldLeft(List list,  
                              B identity, Function> f) {  
  return list.reverse().foldLeft(identity, x -> y -> f.apply(y).apply(x));  
}  

Note that you can also define foldLeft in terms of foldRight, although this is much less useful:

view plaincopy to clipboardprint?
public static  B foldLeftViaFoldRight(List list,  
                              B identity, Function> f) {  
  return List.foldRight(list.reverse(),identity, x -> y ->  
                                                    f.apply(y).apply(x));  
}  

Again, note that the foldLeft method you use is an instance method of List. In contrast, foldRight is a static method. (We’ll define an instance foldRight method soon.)

Heap-based recursive version of foldRight
As I said, the recursive foldRight implementation is only for demonstrating these concepts, because it’s stack-based and thus shouldn’t be used in production code. Also note that this is a static implementation. An instance implementation would be much easier to use, allowing you to chain method calls with the object notation.

Let's use what you learned in chapter 4 to write a heap-based recursive instance version of the foldRight method (Exercise 5.14). The method can be defined in the parent List class. Write a tail recursive stack-based version of the foldRightmethod (using a helper method). Then change the helper method to a heap-based recursive implementation using the TailCall interface you developed in chapter 4.

First, let’s write the stack-based tail recursive helper method. All you have to do is write a helper method that takes an accumulator as an additional parameter. The accumulator has the same type as the function return type, and its initial value is equal to the identity element (which, by the way, is used twice):

view plaincopy to clipboardprint?
public  B foldRight(B identity, Function> f) {  
    return foldRight_(identity, this.reverse(), identity, f);  
}  
  
public  B foldRight_(B acc, List ts, B identity, Function> f) {  
    return ts.isEmpty()  
            ? acc  
            : foldRight_(f.apply(ts.head()).apply(acc), ts.tail(), identity, f);  
}  

Now change both methods to use TailCall heap-based recursion:

view plaincopy to clipboardprint?
public  B foldRight(B identity, Function> f) {  
    return foldRight_(identity, this.reverse(), identity, f).eval();  
}  
  
private  TailCall foldRight_(B acc, List ts, B identity, Function> f) {  
    return ts.isEmpty()   
            ? ret(acc)   
            : sus(() -> foldRight_(f.apply(ts.head()).apply(acc), ts.tail(), identity, f));  
}  

Now we can implement concat in terms of either foldLeft or foldRight (Exercise 5.15). The concat method can be implemented easily using a right fold:

view plaincopy to clipboardprint?
public static  List concat(List list1, List list2) {  
    return foldRight(list1, list2, x -> y -> new Cons<>(x, y));  
}  

Another solution is to use a left fold. In this case, the implementation will be the same as reverseViaFoldLeft applied to the reversed first list, using the second list as the accumulator:

view plaincopy to clipboardprint?
public static  List concat(List list1, List list2) {  
  return list1.reverse().foldLeft(list2, x -> x::cons);  
}  

Now let's write a method for flattening a list of lists into a list containing all elements of each contained list (Exercise 5.16). This operation consists of a series of concatenations. In other words, it’s similar to adding all elements of a list of integers, although integers are replaced with lists, and addition is replaced with concatenation. Other than this, it’s exactly the same as the sum method.

view plaincopy to clipboardprint?
public static  List flatten(List> list) {  
  return foldRight(list, List.list(), x -> y -> concat(x,y));  
}  

Mapping and filtering lists
You can define many useful abstractions for working on lists. One abstraction consists of changing all the elements of a list by applying a common function to them.

Write a functional method that takes a list of integers and multiplies each of them by 3 (Exercise 5.17). Try using the methods you’ve defined up to now. Don’t use recursion explicitly. The goal is to abstract stack-safe recursion once and for all so you can put it to work without having to reimplement it each time.

view plaincopy to clipboardprint?
public static List triple(List list) {  
      return List.foldRight(list, List.list(), h -> t ->  
                                                        t.cons(h * 3));  
}  

Write a function that turns each value in a List into a String (Exercise 5.18). This operation can be seen as concatenating an empty list of the expected type (List) with the original list, with each element being transformed before being cons-ed to the accumulator. As a result, the implementation is very similar to what you did in the concat method:

view plaincopy to clipboardprint?
public static List double2String(List list) {  
    return List.foldRight(list, List.list(), h -> t -> t.cons(Double.toString(h)));  
}  

Finally, let's Write a general functional method map that allows you to modify each element of a list by applying a specified function to it. This time, make it an instance method of List. Add the following declaration in the Listclass (Exercise 5.19):

view plaincopy to clipboardprint?
public abstract  List map(Function f);  

Use the stack-safe instance version of the foldRight method. The map method may be implemented in the parent List class:

view plaincopy to clipboardprint?
public  List map(Function f) {  
  return foldRight(list(), h -> t -> new Cons<>(f.apply(h),t));  
}  

Then let's write a filter method that removes from a list the elements that don’t satisfy a given predicate. Once again, implement this as an instance method with the following signature (Exercise 5.20):

view plaincopy to clipboardprint?
public List filter(Function f)  

Here’s an implementation in the parent List class, using foldRight. Don’t forget to use the stack-safe version of this method

view plaincopy to clipboardprint?
public List filter(Function f){  
     return foldRight(list(), h -> t -> f.apply(h) ? new Cons<>(h,t) : t);  
}  

Write a flatMap method that applies to each element of List a function from A to List, and returns a List. Its signature will be (Exercise 5.21):

view plaincopy to clipboardprint?
public  List flatMap(Function> f);  

For example, List.list(1,2,3).flatMap(i -> List.list(i, -i)) should return list(1,-1,2,-2,3,-3). Once again, it can be implemented in the parent List class, using foldRight:

view plaincopy to clipboardprint?
public  List flatMap(Function> f) {  
    return foldRight(list(), h -> t -> concat(f.apply(h), t));  
}  

Create a new version of filter based on flatMap (Exercise 5.22). Here’s a static implementation:

view plaincopy to clipboardprint?
public static  List filterViaFlatMap(List list, Function p) {  
    return list.flatMap(a -> p.apply(a) ? List.list(a) : List.list());  
}  

Notice that there’s a strong relation between map, flatten, and flatMap. If you map a function returning a list to a list, you get a list of lists. You can then apply flatten to get a single list containing all the elements of the enclosed lists. You’d get exactly the same result by directly applying flatMap. One consequence of this relation is that you can redefine flatten in terms of flatMap:

view plaincopy to clipboardprint?
public static  List flatten(List> list) {  
  return list.flatMap(x -> x);  
}  

This isn’t surprising, because the call to concat has been abstracted into flatMap.

Supplement
* FP with Java - Ch5 - Data handling with lists - Part1
* FP with Java - Ch5 - Data handling with lists - Part2

程式扎記

標籤

2017年12月25日星期一

[ JavaScript Gossip ] JavaScript 核心 : 一切都與函式有關 (this 是什麼?)

[ JavaScript Gossip ] JavaScript 核心 : 一切都與函式有關 (Function 實例)

[ JavaScript Gossip ] JavaScript 核心 : 一切都與函式有關 (函式宣告)

2017年12月24日星期日

[ FP with Java ] Ch5 - Data handling with lists - Part2

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2017年12月25日 星期一