起源
TDD討論組里的申導(dǎo)最近在B站直播了Martin Fowler的經(jīng)典文章Refactoring with Loops and Collection Pipelines中談到的利用集合管道對(duì)循環(huán)進(jìn)行函數(shù)式重構(gòu)奄侠。視頻地址在這里卓箫，申導(dǎo)的翻譯在這里。組織者小波（Seaborn Lee）趁機(jī)出了一道關(guān)于集合管道函數(shù)題目垄潮。我就想啊烹卒，論函數(shù)式編程，舍Clojure其誰弯洗？而且我在Clojure很少能寫出loop... recur這樣偏底層的循環(huán)代碼旅急。話不多說，擼起袖子開工牡整。
題目
一家澡堂有 m 個(gè)房間藐吮，每個(gè)房間有 n 個(gè)時(shí)段，現(xiàn)在要給用戶推薦「最早的可以預(yù)約的時(shí)段」逃贝。
例子：
rooms: [
{
room_id: 1,
periods: [
{
time: '17:00-18:00',
status: 'available'
},
{
time: '18:00-19:00',
status: 'occupied'
}
]
}, {
room_id: 2,
periods: [
{
time: '17:00-18:00',
status: 'occupied'
},
{
time: '18:00-19:00',
status: 'available'
}
]
}
]
期望返回：
{
room_id: 1,
time: '17:00-18:00'
}
解析
題目很簡單谣辞，基本思路：首先過濾出每個(gè)房間periods中status為available的時(shí)間段，然后取第一個(gè)也就是最早的時(shí)間段（默認(rèn)為遞增排序的）沐扳，接著將room_id和這個(gè)時(shí)間段以期望返回的形式合并泥从。再然后對(duì)所有合并的結(jié)果依據(jù)時(shí)間段進(jìn)行一次排序（sort），最后取第一個(gè)結(jié)果即可沪摄。
1. Clojure 解法
轉(zhuǎn)換數(shù)據(jù)格式
原題中給的是json的格式躯嫉，不適合在Clojure中處理纱烘，所以我們手工轉(zhuǎn)換成需要的形式，如下：
清單1-1 數(shù)據(jù)定義
(def rooms
[{:room-id 1
:periods [{:time "17:00-18:00"
:status :available}
{:time "18:00-19:00"
:status :occupied}]}
{:room-id 2
:periods [{:time "17:00-18:00"
:status :occupied}
{:time "18:00-19:00"
:status :available}]}])
代碼
清單1-2 房間最早可預(yù)約時(shí)間段
(defn the-earliest-available-room [rooms]
(->> rooms
(map
(juxt first (fn [{:keys [periods]}]
(->> periods
(filter #(= (:status %) :available))
(ffirst)))))
(map #(into {} %))
(sort-by :time)
(first)))
(the-earliest-available-room rooms)
-> {:room-id 1, :time "17:00-18:00"}
這段代碼和上面的解析是一一對(duì)應(yīng)的關(guān)系和敬。為了讓程序清晰凹炸，符合管道的用法，這里使用了thread last宏（->>）昼弟，它的作用是把前面一個(gè)form作為后一個(gè)form的最后一個(gè)參數(shù)啤它。與之呼應(yīng)的是thread first宏（->），它的作用類似舱痘，不過會(huì)傳成第一個(gè)參數(shù)变骡。
我們先看(map (juxt ...) ...)這一段代碼。juxt是一個(gè)非常有意思的函數(shù)芭逝，而且超級(jí)實(shí)用塌碌。它的文檔描述如下：
(doc juxt)
->
clojure.core/juxt
[f]
[f g]
[f g h]
[f g h & fs]
Added in 1.1
Takes a set of functions and returns a fn that is the juxtaposition
of those fns. The returned fn takes a variable number of args, and
returns a vector containing the result of applying each fn to the
args (left-to-right).
((juxt a b c) x) => [(a x) (b x) (c x)]
它的神奇之處在于可以對(duì)同一個(gè)參數(shù)應(yīng)用不同的函數(shù)，而且還能將應(yīng)用的結(jié)果全部收集起來旬盯。想想題目的解析中提及的以期望返回的形式合并台妆，如果我們應(yīng)用juxt函數(shù)，就能得到[(:room-id 1) (:time "17:00-18:00")]這樣的中間結(jié)果胖翰。
(juxt first (fn ...))中first用于提取:room-id接剩，而后面的lambda表達(dá)式則用于提取:time。解法很直觀萨咳，篩選出:status是:available的時(shí)間段懊缺，然后使用(ffirst)取第一個(gè)map的首個(gè)entry。如：{:time "17:00-18:00" :status :available}培他，那么應(yīng)用(ffirst)的結(jié)果就是[:time "17:00-18:00"]鹃两。
接下來，又進(jìn)行了一次map操作舀凛，這次的目的是把元組的entries俊扳，轉(zhuǎn)換為map。舉個(gè)例子：[[:room-id 1] [:time "17:00-18:00"]] => {:room-id 1 :time "17:00-18:00"}猛遍。轉(zhuǎn)換成map之后拣度，方便以:time對(duì)結(jié)果進(jìn)行排序(sort-by :time)，最后取出第一個(gè)元素(first)螃壤，即我們期望的返回抗果。
寫完之后，我很想再寫個(gè)TDD版本的奸晴。話不多說冤馏，繼續(xù)擼袖子。
2. Clojure TDD 解法
環(huán)境準(zhǔn)備
生成工程
進(jìn)入命令行寄啼，輸入lein new midje the-earliest-available-period-of-bathroom逮光，leiningen會(huì)生成基于midje這個(gè)測試框架的工程代箭。Git
git init
> .gitignore
.lein*
.nrep*
target/
這里ctrl-c退出
git add .
git commit --message "init commit"
我使用了zsh和oh-my-zsh，自帶了很多git操作的alias涕刚，可以通過alias |grep git查看嗡综。后續(xù)的git操作都會(huì)使用alias。
自動(dòng)測試
輸入lein repl杜漠，然后(use 'midje.repl)极景，最后輸入(autotest)。這樣一旦文件修改保存驾茴，測試就會(huì)自動(dòng)觸發(fā)盼樟。Emacs
用來寫代碼的。
Tasking（任務(wù)拆分）
先不急著敲代碼锈至，我們先從測試的角度看看完成這個(gè)需求需要哪幾步晨缴？
- [ ] 單間澡堂有一個(gè)可用時(shí)間段
- [ ] 單間澡堂有多個(gè)可用時(shí)間段
- [ ] 所有澡堂（包含輸入為空）沒有可用時(shí)間段
- [ ] 多間澡堂都有可用時(shí)間段
- [ ] 多間澡堂中有的有可用時(shí)間段，有的沒有可用時(shí)間段
第1個(gè)任務(wù)
- [ ] 單間澡堂有一個(gè)可用時(shí)間段
1. 寫測試
(def room-1 {:room-id 1
:periods [{:time "17:00-18:00"
:status :available}
{:time "18:00-19:00"
:status :occupied}]})
(def room-2 {:room-id 2
:periods [{:time "17:00-18:00"
:status :occupied}
{:time "18:00-19:00"
:status :available}]})
(facts "about `the-earliest-avaible-period-of-bathroom`"
(fact "should recommand if there is only one room with available period"
;; 1號(hào)
(the-earliest-available-recommand [room-1]) => {:room-id 1 :time "17:00-18:00"})
;; 2號(hào)
(the-earliest-available-recommand [room-2]) => {:room-id 2 :time "18:00-19:00"}))
2. 寫實(shí)現(xiàn)
(defn the-earliest-available-recommand [rooms]
{:room-id 1 :time "17:00-18:00"})
針對(duì)1號(hào)測試峡捡，這個(gè)實(shí)現(xiàn)有點(diǎn)“荒誕”击碗，術(shù)語hard code說的就是這個(gè)，但是眼下足夠了们拙。不過此時(shí)稍途，應(yīng)該再寫一個(gè)類似的測試來去除hard code，即2號(hào)測試睛竣。
相應(yīng)地晰房，我們要修改實(shí)現(xiàn)求摇。
defn the-earliest-available-recommand [rooms]
(let [{:keys [room-id periods]} (first rooms)
available-periods (filter #(#{:available} (:status %)) periods)]
(merge {:room-id room-id}
(select-keys (first available-periods) [:time]))))
3. 關(guān)閉并提交
- [x] 單間澡堂有一個(gè)可用時(shí)間段
ga .
gcmsg "one available room"
第2個(gè)任務(wù)
- [ ] 單間澡堂有多個(gè)可用時(shí)間段
1. 寫測試
(def room-3 {:room-id 3
:periods [{:time "17:00-18:00"
:status :occupied}
{:time "18:00-19:00"
:status :available}
{:time "19:00-20:00"
:status :available}]})
...
(fact "should recommand the earliest one if there is only one room with multiple available periods"
(the-earliest-available-recommand [room-3]) => {:room-id 3 :time "18:00-19:00"})
保存射沟，發(fā)現(xiàn)測試還是跑過了。原因在于我們默認(rèn)了period是遞增排序的与境。我們看看有沒有重構(gòu)點(diǎn)验夯？實(shí)現(xiàn)太簡單了暫時(shí)找不到，那就歡歡喜喜地跳過實(shí)現(xiàn)步驟摔刁。
2. 關(guān)閉并提交
- [x] 單間澡堂有多個(gè)可用時(shí)間段
ga .
gcmsg "one room with multiple available periods"
第3個(gè)任務(wù)
- [ ] 所有澡堂（包含輸入為空）沒有可用時(shí)間段
1. 寫測試
(def non-available-room {:room-id 4
:periods [{:time "17:00-18:00"
:status :occupied}
{:time "18:00-19:00"
:status :occupied}
{:time "19:00-20:00"
:status :occupied}]})
(fact "should show `:no-available-room` if there is no available room"
(the-earliest-available-recommand []) => :no-available-room
(the-earliest-available-recommand [non-available-room]) => :no-available-room))
這回肯定掛掉挥转。
2. 寫實(shí)現(xiàn)
(defn the-earliest-available-recommand [rooms]
(let [{:keys [room-id periods]} (first rooms)
available-periods (filter #(#{:available} (:status %)) periods)]
(if (seq available-periods)
(merge {:room-id room-id}
(select-keys (first available-periods) [:time]))
:no-available-room)))
這里使用了Clojure中判斷集合是否為空較為常用的手法(seq )，如果集合非空共屈，那么返回集合本身绑谣；反之，返回nil拗引，nil在邏輯上是false借宵。測試通過。
3. 關(guān)閉并提交
- [x] 所有澡堂（包含輸入為空）沒有可用時(shí)間段
ga .
gcmsg "no available room"
第4個(gè)任務(wù)
- [ ] 多間澡堂都有可用時(shí)間段
1. 寫測試
(fact "should recommand the earliest if there has more than one room and each has available periods"
(the-earliest-available-recommand [room-1 room-2]) => {:room-id 1 :time "17:00-18:00"}
(the-earliest-available-recommand [room-2 room-1]) => {:room-id 1 :time "17:00-18:00"}
(the-earliest-available-recommand [room-2 room-3]) => {:room-id 2 :time "18:00-19:00"}
(the-earliest-available-recommand [room-1 room-2 room-3]) => {:room-id 1 :time "17:00-18:00"})
2. 寫實(shí)現(xiàn)
(defn the-earliest-available-recommand [rooms]
(if (seq rooms)
(first (sort-by :time
(map (fn [room]
(let [{:keys [room-id periods]} room
available-periods (filter #(#{:available} (:status %)) periods)]
(if (seq available-periods)
(merge {:room-id room-id}
(select-keys (first available-periods) [:time]))
:no-available-room)))
rooms)))
:no-available-room))
到這里矾削，我們開始使用(map )函數(shù)處理多個(gè)房間的內(nèi)容壤玫。注意豁护，當(dāng)輸入房間是空集合的時(shí)候，這里需要相應(yīng)地做(seq rooms)判空處理欲间，否則會(huì)返回nil楚里，而不是我們想要的:no-available-room。
3. 關(guān)閉并提交
- [x] 多間澡堂都有可用時(shí)間段
ga .
gcmsg "more than one room"
4. 重構(gòu)
代碼寫到這里猎贴，再不重構(gòu)就說不過去了班缎。另外，管道沒看到嘱能，倒是看到一堆括號(hào)吝梅。
我們使用thread last(->> )做一次重構(gòu)：
(defn the-earliest-available-recommand [rooms]
(if (seq rooms)
(->> rooms
(map (fn [room]
(let [{:keys [room-id periods]} room
available-periods (filter #(#{:available} (:status %)) periods)]
(if (seq available-periods)
(merge {:room-id room-id}
(select-keys (first available-periods) [:time]))
:no-available-room))))
(sort-by :time)
first)
:no-available-room))
還行，至少?zèng)]那么多嵌套了惹骂。提交一次苏携。
ga .
gcmsg "[refactor] use macro thread-last ->> to pipe"
繼續(xù)重構(gòu)，使用我們的juxt函數(shù)对粪。
(defn the-earliest-available-recommand [rooms]
(letfn [(period [{:keys [periods]}]
(->> periods
(filter #(#{:available} (:status %)))
ffirst
(#(or % [:time ::non-available]))))]
(->> rooms
(map (fn [room]
(apply conj {} ((juxt first period) room))))
(remove #(#{::non-available} (:time %)))
(sort-by :time)
first
(#(or % :no-available-room)))))
看上去還行右冻，不過不爽的是(#(or % [:time ::non-available]))。為了迎合(->> )宏著拭，我們給(or )包了一層纱扭。原因是(->> )會(huì)讓前面的結(jié)果出現(xiàn)在最后一個(gè)參數(shù)的位置，而我們需要將結(jié)果放到(or )的第一個(gè)參數(shù)的位置儡遮。有沒有什么好看的解決方法呢乳蛾？當(dāng)然有！我們可以使用(-> )來做到這點(diǎn)鄙币。
(defn the-earliest-available-recommand [rooms]
(letfn [(period [{:keys [periods]}]
(-> periods
(->> (filter #(#{:available} (:status %)))
ffirst)
(or [:time ::non-available])))]
(-> rooms
(->> (map (fn [room]
(apply conj {} ((juxt first period) room))))
(remove #(#{::non-available} (:time %)))
(sort-by :time)
first)
(or :no-available-room))))
頓時(shí)覺得世界干凈了不少肃叶。再提交一次。
ga .
gcmsg "[refactor] use juxt to extract needed fields"
第5個(gè)任務(wù)
- [ ] 多間澡堂中有的有可用時(shí)間段十嘿，有的沒有可用時(shí)間段
1. 寫測試
(fact "should recommand the earliest available room even if there has non available room"
(the-earliest-available-recommand [room-1 non-available-room]) => {:room-id 1 :time "17:00-18:00"}
(the-earliest-available-recommand [room-2 non-available-room]) => {:room-id 2 :time "18:00-19:00"})
測試直接通過因惭，又可以跳過實(shí)現(xiàn)代碼了。不過绩衷，這也預(yù)示著我們的測試是有覆蓋的蹦魔，也需要花時(shí)間整理這些測試用例。在那之前咳燕，先提交一下勿决。
2. 關(guān)閉并提交
- [x] 多間澡堂中有的有可用時(shí)間段，有的沒有可用時(shí)間段
ga .
gcmsg "mixed non-available and available rooms"
為第3個(gè)任務(wù)補(bǔ)上測試用例
- [x] 所有（包含多個(gè)）澡堂（包含輸入為空）沒有可用時(shí)間段
(fact "should show `:no-available-room` if there is no available room"
(the-earliest-available-recommand []) => :no-available-room
(the-earliest-available-recommand [non-available-room]) => :no-available-room
(the-earliest-available-recommand [non-available-room non-available-room]) => :no-available-room))
這里的第3個(gè)用例包含第2個(gè)用例招盲，我們待會(huì)整理掉低缩。不過現(xiàn)在先提交一下。
ga .
gcmsg "multiple non-available rooms"
整理測試
在前面進(jìn)行的任務(wù)當(dāng)中宪肖，我們發(fā)現(xiàn)有兩次沒有寫實(shí)現(xiàn)測試就通過的情況表制。這說明測試用例是有覆蓋的健爬。
- 第2個(gè)任務(wù)的測試用例其實(shí)覆蓋了第1個(gè)任務(wù)的測試用例，所以可以直接刪去后者么介；
- 第5個(gè)任務(wù)的測試用例覆蓋了第4個(gè)任務(wù)的部分測試用例娜遵，所以可以合并到一起。
整理下來壤短，最終的測試變成下面這樣：
(facts "about `the-earliest-avaible-period-of-bathroom`"
(fact "should recommand the earliest one if there is only one room with multiple available periods"
(the-earliest-available-recommand [room-3]) => {:room-id 3 :time "18:00-19:00"})
(fact "should show `:no-available-room` if there is no available room"
(the-earliest-available-recommand []) => :no-available-room
(the-earliest-available-recommand [non-available-room non-available-room]) => :no-available-room)
(fact "should recommand the earliest if there has more than one room and each may have available periods"
(the-earliest-available-recommand [room-1 room-2]) => {:room-id 1 :time "17:00-18:00"}
(the-earliest-available-recommand [room-2 room-1]) => {:room-id 1 :time "17:00-18:00"}
(the-earliest-available-recommand [room-2 room-3]) => {:room-id 2 :time "18:00-19:00"}
(the-earliest-available-recommand [room-1 room-2 room-3]) => {:room-id 1 :time "17:00-18:00"}
(the-earliest-available-recommand [room-1 non-available-room]) => {:room-id 1 :time "17:00-18:00"}))
文檔
The final goal of any engineering activity is some type of documentation.
更新README.md文件设拟，其中描述程序解決的問題以及運(yùn)行步驟，當(dāng)然包含設(shè)計(jì)思路那更好了久脯。提交一下纳胧。
ga .
gcmsg "update readme"
美化代碼
代碼是詩行 - by lambeta
什么是好看的代碼？除了清晰明了帘撰，格式也必須產(chǎn)生美感跑慕。
(defn the-earliest-available-recommand [rooms]
(letfn [(period [{:keys [periods]}]
(-> periods
(->> (filter #(#{:available} (:status %))))
(ffirst) ; 統(tǒng)一套上括號(hào)
(or [:time ::non-available])))]
(-> rooms
(->> (map (juxt first period))
(map #(into {} %)) ; 合并單獨(dú)提出來
(remove #(#{::non-available} (:time %)))
(sort-by :time)
(first)) ; 統(tǒng)一套上括號(hào)
(or :no-available-room))))
順眼不少，最后提交一下摧找。
ga .
gcmsg "[refactor] beautify pipe format"
這篇文章發(fā)出來一天核行，TDD討論群的一位麥姓朋友@我道：
core=> (first {:a 1 :b 2})
[:a 1]
core=> (first {:b 2 :a 1})
[:b 2]
@lambeta map的元素應(yīng)該是無序的，用first來獲得key value pair是不可靠的蹬耘。
看到這個(gè)建議的時(shí)候芝雪，我心里一陣欣喜——又有一員Clojurians，可以切磋技藝了综苔！冷靜下來惩系，發(fā)現(xiàn)自己確實(shí)忽略了map中的entries可能是無序的。所以我做了如下的驗(yàn)證：
(type {})
-> clojure.lang.PersistentArrayMap
看到PersistentArrayMap的時(shí)候如筛，我明白這些entries是保持插入順序的堡牡，也就是說，(first {:a 1 :b 2})的求值結(jié)果一定是[:a 1]妙黍。照這個(gè)思路悴侵，在我的程序當(dāng)中使用(first )取map的第一個(gè)元素并不會(huì)出錯(cuò)瞧剖。不過拭嫁，本著謹(jǐn)慎的心態(tài)，我查了一下clojure的array-map抓于，發(fā)現(xiàn)一個(gè)有趣的例子：
(defn make-map [count] (zipmap (range count) (range count)))
(type (make-map 9))
;; => clojure.lang.PersistentArrayMap
(type (make-map 10))
;; => clojure.lang.PersistentHashMap
這表明當(dāng)map中的entries數(shù)量超過一定數(shù)量（不一定是9做粤，例外見：PersistentArrayMap's assoc doesn't respect HASHTABLE_THRESHOLD）時(shí)，PersistentArrayMap就變成了PersistentHashMap捉撮，那也就意味著怕品，(first )取出來的值可能是隨機(jī)的。舉個(gè)例子：
(first {7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 0 0, 8 8, 5 5})
-> [0 0]
返回的結(jié)果并不是相當(dāng)然的[7 7]巾遭，而是[0 0]肉康。那么(first )到底干了些什么呢闯估？Cognitect公司的alexmiller回答我說：(first )會(huì)把它的參數(shù)強(qiáng)制轉(zhuǎn)換（coerce）成了一個(gè)序列，然后取第一個(gè)值吼和。我們?cè)囍?code>(seq )轉(zhuǎn)換一下：
(type { 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 0 0, 8 8, 5 5})
-> clojure.lang.PersistentHashMap
(seq { 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 0 0, 8 8, 5 5})
-> ([0 0] [7 7] [1 1] [4 4] [6 6] [3 3] [2 2] [9 9] [8 8])
果然涨薪，[0 0]出現(xiàn)在序列的首位。至于為什么是這樣的順序炫乓，需要深入Clojure的hash算法和數(shù)據(jù)結(jié)構(gòu)當(dāng)中刚夺，有時(shí)間另起一篇博客解釋。我們?cè)僭囋?code>PersistentArrayMap的情況：
(type { 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 0 0})
-> clojure.lang.PersistentArrayMap
(seq { 7 7, 1 1, 4 4, 6 6, 3 3, 2 2, 9 9, 0 0})
-> ([7 7] [1 1] [4 4] [6 6] [3 3] [2 2] [9 9] [0 0])
順序確實(shí)和原來的一致末捣。
我們的程序當(dāng)中是不應(yīng)該假設(shè)map是有序的侠姑，所以需要修改實(shí)現(xiàn)代碼。
(defn the-earliest-available-recommand [rooms]
(letfn [(period [{:keys [periods]}]
(-> periods
(->> (filter (comp ∈{:available} :status)))
(first)
(find :time)))
(room-id [room]
(find room :room-id))]
(-> rooms
(->> (map (comp (partial into {}) (juxt room-id period)))
(filter :time)
(sort-by :time)
(first))
(or :no-available-room))))
(find )函數(shù)箩做，用于從map中獲取包含該鍵值的entry莽红，如果找不到，返回nil邦邦。這樣就避免了潛在無序的entries對(duì)程序的干擾船老。另外，(partial into {})和Currying很像圃酵，它通過接收into函數(shù)及其首個(gè)參數(shù)柳畔，構(gòu)造出一個(gè)接收后續(xù)參數(shù)的函數(shù)。當(dāng)然也可以直接使用#(into {} %)這樣的形式郭赐。
下面是麥姓朋友的另一種解法薪韩，和我的解法思路不完全一樣，值得學(xué)習(xí)借鑒捌锭。
(defn the-earliest-available-recommand [rooms]
(letfn [(earliest-available-time [periods]
(->> periods
(filter (comp #{:available} :status))
(map :time)
(sort)
(first)))]
(rename-keys
(->> rooms
(map #(update-in % [:periods] earliest-available-time))
(filter :periods)
(sort-by :periods)
(first))
{:periods :time})))
真誠歡迎大家繼續(xù)點(diǎn)評(píng)俘陷。
