Thursday, January 22, 2009

cluster by

Tom MoerTel เขียน function มหัศจรรย์ไว้ใน post ClusterBy: a handy little function for the toolbox
function มีหน้าตาแบบนี้
import Control.Arrow ((&&&))
import qualified Data.Map as M

clusterBy :: Ord b => (a -> b) -> [a] -> [[a]]
clusterBy f = M.elems . M.map reverse . M.fromListWith (++)
. map (f &&& return)

แล้วก็ทำแบบนี้ได้
*Main> let antwords = words "the tan ant gets some fat"
*Main> clusterBy length antwords
[["the","tan","ant","fat"],["gets","some"]]
*Main> clusterBy head antwords
[["ant"],["fat"],["gets"],["some"],["the","tan"]]
*Main> clusterBy last antwords
[["the","some"],["tan"],["gets"],["ant","fat"]]

ตัว function กระทัดรัดมาก แต่อ่านแล้วไม่เข้าใจเลย ก็เลยต้องออกแรงนั่งแกะหน่อย
เริ่มแรกสุด มันจะทำแบบนี้ก่อน
map (f &&& return) ["the", "tan", "ant", "gets", "some", "fat"]

เจ้า &&& มีชื่อเรียกว่า fanout ลองดูการทำงานมัน (เพราะอธิบายยากมาก)
*Main> (head &&& last) "abc"
('a','c')
*Main> (head &&& id) "abc"
('a',"abc")

จะเห็นว่ามัน apply function แรกกับ function ที่ 2 เข้ากับ parameter ผลลัพท์ที่ได้ก็จับมาเข้าคู่เป็น tuple ไว้ (หรือจะเรียกว่า pair ก็ได้ เพราะมีแค่ 2 elements)
Note: ถ้าใครยังงงๆกับ fanout ลองดู diagram ที่ Daniel Lyons เขียนไว้ใน Haskell Arrows

ที่นี้มาลองดู return บ้าง การที่เราสั่ง return "abc" ผลลัพท์ของมันก็คือ Monad "abc"
(ถ้ายังไม่รู้จัก monad ก็ให้สมมติไปก่อนว่า monad ก็คือ container structure แบบหนึ่ง)
ดังนั้นผลลัพท์ของ

map (head &&& return) ["the", "tan", "ant", "gets", "some", "fat"]
ก็จะได้
[("t", Monad "the"), ("t", Monad "tan"), ...]


การทำงานลำดับถัดมาก็คือ M.fromListWith (++) หรือถ้าเขียนเต็มๆก็คือ Data.Map.fromListWith (++)
เจ้า fromListWith เป็น function ที่ไว้ใช้สร้าง Dictionary(Map) structure
โดยมันจะรับ array ของ pair (ในทีนี้ก็คือ [("t", M "the"), ("t", M "tan"), ...]) แล้วสร้างเป็น Map structure โดยใช้ element แรกของ pair เป็น key ส่วน element ที่สองก็เป็น value ไป
แต่เจ้า fromListWith มีความพิเศษตรงที่ว่า กรณีที่มันพบว่า first element นั้นซ้ำกับที่เคยมีอยู่แล้ว
มันก็จะ apply function ที่เราส่งเข้าไป (ในที่นี้ก็คือ (++)) ให้กับ value ทั้งสอง
ลองดูตัวอย่าง
fromListWith (++) [("a", "ant"), ("b", "bat"), ("a", "axe")]
จะได้ผลลัพท์เป็น
Map ที่มี 2 entry
entry แรกมี key เป็น "a" และ value เป็น "axeant"
ส่วน entry ที่สอง มี key เป็น "b" และ value เป็น "bat"

กรณีของเรา element ที่สองมันมี type เป็น Monad
เจ้า function (++) เมื่อเจอกับ Monad มันจะมีพฤติกรรมเป็นแบบนี้แทน
*Main> [1] ++ [2]
[1,2]
*Main> (return 1) ++ (return 2)
[1,2]
*Main> (return "ant") ++ (return "axe")
["ant","axe"]

Note: ดูเหมือนว่าใน haskell่, Array กับ Monad มีความสัมพันธ์แน่นแฟ้น

คำสั่งลำดับถัดไปก็คือ M.map reverse
อันนี้ไม่มีอะไรแล้ว แค่ reverse ค่า value ทุกตัวใน Map

สุดท้ายก็คือ elems ก็คือ กรองเอาแต่ค่า value ใน Map

Related link from Roti

2 comments:

Anonymous said...

จนป่านนี้ผมก็ยังไม่ได้ดู Monad ให้เข้าใจกระจ่างสักที จาก clusterBy ดูเหมือนว่า Monad มันจะเป็นที่ห่อของเลยครับ

PPhetra said...

ตรง return ดูเหมือนจะเป็น hack ของเขา
จริงๆเราต้องการ function ที่ใช้แปลง [char] ให้กลายเป็น [[char]] ซึ่งถ้าเขียนแบบง่ายๆ ก็คือ

toList = (flip (:)) []

เจ้า toList นี่เอาไปแทนที่ "return" ได้เลย