Functional Thursday #35

• [19:30 ~ 19:45] 自由交流

• [19:45 ~ 20:30] Pure Functional Real-time Queue [中文/Chinese] by CindyLinz

在 pure functional 的世界裡, 如果只使用 immutable 的資料操作. 用 list (就是 [a]) 來實作 stack 是很容易的, 但要實作 queue 就相對複雜一點.. 而如果要實作每一步操作都只需要 O(1) 時間的 queue, 就更需要一些技巧了. (註: 在號稱 pure functional 的 Haskell 裡面, 用到的資料結構不一定都是 pure functional data structure 喔)

這一次介紹用的程式語言是 Haskell. 從一個簡單的 amortized O(1) 的 queue 實作開始, 再逐步把它改成 worst case O(1) 的 queue. 其中會介紹一個叫作 schedule 的技巧, 可以把任意的 amortized 演算法改成 real time 演算法. (也會稍微介紹一下 time complexity, 以及什麼叫 amortized, 什麼叫 worst case/real time 的 time complexity.)

最後我們會獲得一個 pure functional 的 real-time queue. 它的每一步操作只需要 O(1) 的時間, 而且可以隨意把任意的歷史記錄留下來, 各自發展自己的新歷史, 而且不管怎樣翻來覆去地用, 每一個操作都只需要 O(1) 的時間.

我覺得這個資料結構本身... 不見得能有多實用 XD 但是實作過程中所用到的 schedule 技巧, 倒是非常值得一看!

• [20:30 ~ ] lightning talk & 自由交流

也歡迎大家來

https://funth.hackpad.com/Functional-Thursday-Topics-sGic3s4ncNn

填填看想投稿/想要聽的主題唷！