如何使用 haskell 寫出高效代碼刷演算法比賽題目？

01-11

由於haskell是純函數式的，演算法比賽中常見的數據結構上update-query模式的問題，都不得不每一次update對整個數據結構進行重建，這樣效率會很低，很容易超時。提高haskell代碼性能有什麼經驗？

學會使用ST monad就好.

Monad/ST - HaskellWiki

真的需要這種mutation的部分, 寫出看起來像C++的代碼也是可以理解的. 但是還是可以儘力把這部分和pure的部分分開的.

Array的話用mutable array之類的東西.

樹狀結構常常並不需要用到ST monad(看以下)

真不行還有unsafePerformIO這種核武器 (眾: 這不是普通語言做的事情怎麼就成核武了...)

crazyb0y就用Haskell刷了一些題. 他github里的用Haskell刷題的似乎已經被刪了. 不過還好幾年前我fork了一下(什麼都沒改, 純粹fork了). 所以可以這裡查看, 了解刷題技巧.

可以高效的做map的finger tree(還沒有人implement的樣子...)可以滿足很多演算法題的需求. 我的一個Finger Tree的介紹.

Finger tree真正的contribution實際上是一個很棒很棒的抽象層. 很好的抽象了要解決的問題究竟是什麼, 真的大多時候implement一個(很簡單)的monoid就好. 各種其他抽象數據結構可以幾行搞定.

可惜的是, 現在的implementation速度並不是很快, 真的感覺做OI的人可以考慮把這個

- 好好的優化一下?

- 加入一些其他operation? 比如O(log n)的reversal? (壞處是要存2倍的信息. 所以可能考慮可以turn off這個功能直到第一次reversal)

- 如果不是為了那些完美的理論結論, finger tree的後端完全可以用splay tree代替. 效率估計會好很多.

只要想好了很棒的抽象, 然後多加入點operation, 成為萬能的數據結構指日可待. (下一步就是想出適合link-cut tree的好的抽象...)

類似的有DUAL-tree. 可以想像成有同時可以從下往上和從上往下的有lazy propagation的segment tree的Haskell版本. 可以fold.

dual-tree: Rose trees with cached and accumulating monoidal annotations

這個的抽象層就低了不少, 完全在數據結構本身了...

The 「Mutable Algorithms in Immutable Languages」 series

Part 1 where we introduce the problem of mutable algorithms in immutable languages by exploring Union/Find.

Part 2 where we find models of mutable memory which can be executed purely or impurely in Haskell.

Part 3 where we fix a crucial bug in the pure implementation from part 2 by reflecting on the need for border control between 「regions」 of mutable memory and, finally, finally, introduce ST as the final solution.

鏈接都掛了, 謝 @Tang Boyun 提醒

Part 1: jspha / posts

Part 2: jspha / posts

Part 3: jspha / posts

又掛了, 可以在這裡找:

old-blog/_posts at master · tel/old-blog · GitHub

haskell的線段樹實現，直接就是可持久化的，「函數式線段樹」概念（好像？）就是這裡搬過去的。雖然更新函數需要輸入Tree，返回Tree，但並不是你想像的"對整個數據結構進行重建"，由於immutable，不變的節點全都會復用，真正更新到的節點只有O(log n)個，再加上lazy，經常更新卻不訪問複雜度還會更低。

如果演算法沒錯，實現科學的話，haskell執行效率與其他語言基本只有常數差距。

此外，至於可變數組，可以用ST monad解決。

不過確實有些數據結構難以在haskell高效實現（splay? LCT?），這種時候可能直接換個語言會更方便

SPOJ, Timus Online Judge, CodeChef, Codeforces, HackerRank都能用Haskell

Google Code Jam、Project Euler、Rosalind這樣提交答案的可以本地用

以前金斌的 fancy-walks

我也扔一些舊物 MaskRay/OJHaskell · GitHub 比較少

給大家……補充一條歪路。

就是適（da）當（liang）的開strict……

雖然我們是支持Haskell的，但用Haskell刷題的人確實很少。

Haskell提交記錄 - 51Nod

如果必須如此，那就用ref。

處理mutable數據非得用haskell這個本身就是bug。

我覺得像SPOJ這種應該在計算超時的時候為每門語言加個係數，不然有些題不用C++就AC不了。