Note on Functional Thinking

note_on_functional_thinking.md

Notes on Functional Thinking

Chap2. Shift

3 common building blocks of functional language

1. Filter Use filter to produce a subset of a collection based on supplied filtering criteria.

2. Map Use map to transform collections in situ

3. Fold/Reduce Use reduce or fold for piecewise collection processing

Chap3. Cede

Iteration to High-Order Functions

Replacing iteration with functions such as map

Closures

定義: The function (or method) encloses a con‐ text around the things it references

實作: From an implementation standpoint, the closure instance holds onto an encapsulated copy of whatever is in scope when the closure is created

Closures let the language manage state

Closures are also an excellent example of deferred execution. For example, the correct variables or functions might not be in scope at def‐ inition time but are at execution time. By wrapping the execution context in a closure, you can wait until the proper time to execute it

Closures allow us to model behavior by encapsulating both code and context into a single construct, the closure, that can be passed around like traditional data structures and executed at exactly the correct time and place.

Currying and Partial Application

Currying describes the conversion of a multiargument function into a chain of single-argument functions

Partial application describes the conversion of a multiargument function into one that accepts fewer arguments, with values for the elided arguments supplied in advance

用途:

1. Fuction factories
2. Template method design pattern
3. Implicit values

Recursion

用不同的觀點看待 List:

Instead of thinking of a list as indexed slots, think of it as a combination of the first element in the list (the head) plus the remainder of the list (the tail)

Thinking about a list as head and tail allows me to iterate through it using recursion

下面的兩個作法的差異在於是否要管理 state, 而什麼是 state 呢? new_list 是 state, 在 imperative 版本中 程序員要管理這個 state, 但是在 recursive 版本中, 這個 state 交由 runtime 管理 (recursive 的 stack)

• Imperative filtering with Groovy

  def filter(list, predicate) {
    def new_list = []
    list.each {
      if (predicate(it)) {
        new_list << it
      }
    }
    return new_list
  }
  modBy2 = { n - > n % 2 == 0 }
  
  l = filter(1..20, modBy2)
  println l
  

• Recursive filtering with Groovy

  def filterR(list, pred) {
    if (list.size() == 0) return list
    if (pred(list.head()))
      [] + list.head() + filterR(list.tail(), pred)
    else
      filterR(list.tail(), pred)
  }
  println "Recursive Filtering"
  println filterR(1..20, { it % 2 == 0 })
  //// [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
  

Streams and Work Reordering

One of the advantages of switching from an imperative to a functional style lies in the runtime’s ability to make efficiency decisions for you

由於 functional programming 具有 lazy 的特性, 下面的程式碼交換 map, filter 的順序其實是沒差的, runtime 會在 背後自動先作 filter, 然後在做 map, 提升效率

public String cleanNames(List < String > names) {
  if (names == null) return "";
  return names
    .stream()
    .map(e - > capitalize(e))
    .filter(n - > n.length() > 1)
    .collect(Collectors.joining(","));
}

Chap4. Smarter, not Harder

Memoization

Laziness

References

1. 函數加裡化(Currying)和偏函數應用(Partial Application)的比較 | 外刊IT評論 http://www.vaikan.com/currying-partial-application/