iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 11
2

GNU 是 GNU is not UNIX! 的縮寫。
--- 維基百科


天氣放晴了,但風吹在身上卻開始有些涼意了。

一邊說著差不多該是離開前往下一個城市的時候,小動物又一直碎唸著天氣冷了想吃有熱湯又有肉的東西再走。真是麻煩的傢伙。

我一直很好奇招牌上說的那個祖傳的湯是怎麼一回事,小動物說。


在我們知道了函式是一種可以呼叫的東西。而且函式可以被指派給變數,可以當做其它函式呼叫時的參數,也可以回傳函式之後,我們還要理解函式的一個特性:遞迴

遞迴

遞迴基本上就是在函式的定義裡,有呼叫自己的動作。例如這樣的函式:

// JavaScript 語法
function dontRunIt(x) {
  let y = x + 1
  return dontRunIt(y) //這裡呼叫了自己!
}

dontRunIt(1)

是可以定義並執行,但是(概念上)永遠都不會結束的。因為每一步那個 x 會被加上 1,接著當成下一步的 x 來呼叫。如果真的執行下去,運氣好的會把魔法記憶暫存區的空間擠爆然後整個停止,運氣不好的話嘛…

我們來看能正常運作的遞迴吧。

重要的,是什麼時候停下來

我們試著用遞迴的方式,把一個陣列加總吧。

// JavaScript 語法
function sum(source) {
  if (source.length === 0) {
    return 0
  } else {
    let [head, ...tail] = source
    return head + sum(tail)
  }
}

sum([1, 2, 3]) //=> 6

第一次遇到遞迴,我們一步步拆開來看:

  1. 定義完函式後,有人呼叫了 sum,並把 [1, 2, 3] 當參數傳進函式。
  2. 進入函式後,source 會被替換成 [1, 2, 3]
  3. 因為 source 不是空的,所以長度會大於 0,跳過第 3 行進入 else 區塊。
  4. source 被拆成 head 是 1, tail[2, 3]
  5. 留著 1 + 的部份,用 tail,也就是 [2, 3] 當做參數,呼叫下一輪的 sum
  6. 一樣不是空陣列,進入 else, 切成 head2tail[3]
  7. 留著 2 + 的部分,下一輪呼叫 sum 的參數是 tail[3]
  8. 一樣不是空陣列,進入 else, 切成 head3tail[]
  9. 留著 3 + 的部分,下一輪呼叫 sum 的參數是 tail[]
  10. source 終於是空陣列了,回傳 0
  11. 我們拿到了 (1 + (2 + (3 + (0))),可以加總了,拿到結果: 6

尾遞迴

雖然這樣可以運作,但是重新看一下上面的步驟,我們有好幾步的敘述是「留著 x+,接著用 y 當參數進行下一輪的呼叫」。而這個「留著」的行為,事實會在魔法運作的暫存空間裡記著一筆記錄。這次的輸入只有三個,影響不大,但一般來說當術式運作時,若遞迴超過二、三十層,那麼法術的反應速度會明顯的變慢。

想解決這個問題,我們要用到一個技巧,叫做尾遞迴 (tail recursive)。訣竅是每一次遞迴中,回傳的那行,只能是一個可以直接回傳的值,或是單純的函式呼叫。像是這樣:

// JavaScript 語法
function tailRecursiveSum(source, accu) {
  if(source.length === 0) {
    return accu;
  } else {
    let [head, ...tail] = source
    return tailRecursiveSum(tail, accu + head)
  }
}

tailRecursiveSum([1, 2, 3], 0) //=> 6

我們把函式改成接受兩個參數,而其中一個是用來累加的值,接下來每一圈只要做到這兩件事,最後一步就會是個單純的函式呼叫:

  1. 取出一個元素,讓下一步要處理的資料變短一個 (也就是 tail)。
  2. 把取出的元素跟累加器相加

而這麼一來魔法運作時不需要多記錄什麼等一下要回來處理的東西,而是在每一步都把函式呼叫代換成新的參數,在最後一步直接回傳結果。

當我們在尾遞迴加總的範例裡,看到了 sourceaccu。而每一步的計算就是把 accu 跟拿到的元素相加。那麼,我們是不是可以把這個相加的計算也抽出來,讓其它人可以任意的替換成他們想要的計算方式,相乘也好相減也好。那麼大家只要傳入 source 、累加器、以及每一步的累加方式,就自動進行尾遞迴了?

把計算也抽象化

應該可以猜到了吧?這個把計算部份抽象做出來的自動遞迴用法術,就是… reduce。那麼,你想要自己試試看嗎?

// JavaScript 語法
function myReduce(source, accu, f) {
  // ?
}

myReduce([1, 2, 3], 0, (accu, x) => accu + x) //=> 應該要拿到 6

(防雷分隔線)


(防雷分隔線)


(防雷分隔線)


(防雷分隔線)

讓我看看你寫的…喔喔喔雖然花了一段時間,但是很棒啊!嗯?想看我寫的?

// JavaScript 語法
function myReduce(source, accu, f) {
  if (source.length === 0) {
    return accu //當 source 為空時表示已經折完了,回傳累加器(最終結果)
  } else {
    //否則先把 source 切成頭跟尾巴, 倒數第二步時,尾巴會是空串列
    let [head, ...tail] = source;
    return myReduce(tail, f(accu, head), f); //遞迴
    //三個參數分別是 (尾巴, 呼叫 f 產生這一步的累加, f 本身要繼續傳下去)
  }
}

myReduce([1, 2, 3, 4, 5], 1, (accu, i) => accu * i) //=> 120

於是我們現在知道只要某個國家的函式能夠遞迴,我們就可以像組合積木一樣,先組出 reduce,再組出 mapfilter… 一路下去將各種好用的高階函式逐個組裝出來了。


至此,我們已經知道很多有趣的概念了,但是函數式程式設計的核心想法,並非僅是只靠用函式的方式來操作而己。雖然表面上看起來很像是如此,但是就像上次說的,觀點不同,就會得出不同的理解與做法。而更深入的部份,只待在這個莊園裡是很難體會的。

而等你理解了其它的概念之後,回來這個莊園或是其它國家,就能夠不眩目於表面的操作或特定的字詞,而是用更深一層的角度來思考跟解決事情。

所以,想跟我一起往下走,繼續這趟旅程嗎?




於是我們跟學院的人們道別,離開莊園,啟程前往神領 Haskell。

在走了好長一段路後,喧嘩聲遠去而回頭已看不見來時的圍牆。忽然有一條刺眼的弧線,從很遠很遠的地方拋射過來,在前方的荒涼草原上,舖開一整片光的平面。

而當光漸漸柔和下來,就看見在那暖亮的表面,鋼筋與磚塊及各式各樣的建材自平面向上自行組合堆疊並不斷拔高,在短時間內,一幢幢的高樓重覆著建立崩壞建立的過程向上伸展,而整座架構於光流上的城市就在我們眼前逐漸但確實的成形…

我轉頭看小動物,它的表情看起來蠻複雜的。似乎有點開心,但又帶著一絲猶豫。


沒想到這會在這種時候跑到這邊來。

「那個,究竟是什麼?」

Elixir 之城,分散的不沉堡壘

[to be continue]


上一篇
mostly:functional 第九章:高階函式與它們的產地
下一篇
mostly:functional 第十一章:冗餘的變數,連續的轉變
系列文
mostly:functional 從零開始的異世界程式觀 --- 函數式程式設計的試煉35

1 則留言

0
Steven C.
iT邦新手 5 級 ‧ 2020-09-30 10:50:09

範例這段 code 在 node 和 DevTools 執行失敗呢,
原來在 JavaScript 裡面, ([] == []) == false:

function myReduce(source, accu, f) {
  // 這邊 source === [] 回傳 false 導致無限遞迴
  if (source === []) {
    return accu;
  } else {
    // ...
  }
}

myReduce([1, 2, 3, 4, 5], 1, (accu, i) => accu * i); //=> 120
taiansu iT邦新手 5 級 ‧ 2020-09-30 10:51:42 檢舉

咦原來沒有都改到 XD 感激~~~

我要留言

立即登入留言