Monday, July 23, 2007

Max sum ของ Sub-array

zdk post โจทย์ข้อนี้ ใน codenone
เพื่อเป็นการฝึกฝน functional language ผมจึงลองทำด้วย haskell ดู
ทำแล้ว หน้าตาออกมาดูไม่ได้ ก็เลยไป search หาดูว่า บรรดาผู้เชี่ยวชาญ haskell
เข้าทำไว้อย่างไรบ้าง ซึ่งก็สมหวัง เพราะมีการ post ไว้ใน mailing list นี้ Link

ปัญหานี้ ถ้าคิดแบบง่ายสุดก่อน(ไม่คำนึงเรื่อง performance) ก็คือ
1. หา sublist ทั้งหมด
2. คำนวณแปะค่า sum เข้าไปไว้ที่หน้าสุดของ sublist แต่ละตัว
3. หา maximum sum
4. return ค่าที่ได้ โดยโยนค่า sum ทิ้งไป

เริ่มด้วยการหา sublist
ความต้องการคือ
sublist [1,2,3] ต้องได้ [[1],[1,2],[1,2,3],[2],[2,3],[3]] (ไม่จำเป็นต้องเรียงลำดับ)
ดู code ที่ผมเขียน เสียก่อน
sublists xs = sublists' xs [] 
sublists' [] acc = acc
sublists' xs acc = sublists' (tail xs) (tmp ++ acc)
where tmp = snd $ mapAccumL (\acc x -> (x:acc, x:acc)) [] xs

น่าเกลียดมาก เมื่อนำไปเทียบกับมือเก๋าๆแล้ว

เริ่มจากบรรทัดนี้ก่อน เป้าหมายบรรทัดนี้คือ ถ้ามี input เป็น [1,2,3] ต้องได้ [[1],[1,2],[1,2,3]] ออกมา
where tmp = snd $ mapAccumL (\acc x -> (x:acc, x:acc)) [] xs

สามารถใช้ List comprehension แทนได้ดังนี้
where tmp = [ys | n <- [1..length xs], ys <- [(take n xs)]]

ยังยังไม่พอ มี guru มาเฉลยอีกว่า ยาวไป ใช้แค่นี้พอ
where tmp = inits xs

อาฮ้า มี function นี้ให้ใช้ด้วย ตั้งชื่อไม่สื่ออย่างนี้ จะหาเจอได้อย่างไร

ขั้นถัดไปคือปรับตรงบรรทัดนี้
sublists xs = sublists' xs []
sublists' [] acc = acc
sublists' xs acc = sublists' (tail xs) (tmp ++ acc)

เยิ่นเย้อสุดๆ เหลือแค่นี้ก็พอ
sublists [] = []
sublists xs = tmp ++ sublists (tail xs)

อืมม์ได้เท่านี้ก็หรูแล้ว เจอแบบนี้เข้าไปสั้นกว่า
(function tails โผล่ออกมาอีกแล้ว มันมี function แบบนี้ด้วยวุ้ย
tails [1,2,3] = [[1,2,3],[2,3],[3],[]]
)
sublists xs = [zs | ys <- inits xs, zs <- tails ys]

เจ๋งแล้ว แต่มีสั้นกว่านี้อีก
sublists = concatMap tails . inits

แต่การใช้ inits,tails ก็มีปัญหาตรงที่ว่ามันมี empty array เข้ามาปนด้วย
มีคนเสนอ function unfoldr (เอาอีกแล้ว มี function unfoldr ด้วยหรือนี่)
ซึ่งดูดีกว่า ตรงที่ไม่มีปัญหาเรื่อง empty array
แถมยังเป็นการฉลาดที่นำ higher order function ที่มีอยู่แล้วมา apply ใช้
sublists xs = unfoldr f xs
where f [] = Nothing
f xs = Just ([ys | n <- [1..length xs], ys <- [(take n xs)]], tail xs)

หลังจากได้ sublist แล้ว ก็มีถึงขั้นการแปะ sum ลงไปข้างหน้า
ทำง่ายๆโดย
annotate_sum = map (\xs -> (sum xs, xs)) 

จากนั้นก็จัดการหา maximum โดยใช้ function maximumBy
ซึ่งผมเขียนแบบนี้
findMax xs = maximumBy (\a b -> compare (fst a) (fst b)) xs

ก็มีคนมาแสดงให้ดูว่า ทำแบบนี้ได้นะ
findMax xs = maximumBy (\(s1,_) (s2,_) -> compare s1 s2) xs

แล้วก็มีคนมาบอกอีกว่า มันมี function comparing ให้ใช้นะ
(แต่ผมหา function นี้ไม่เจอ คาดว่าคงอยู่ใน version ใหม่กว่าที่มี)
findMax xs = maximumBy (comparing fst)

เมื่อนำมาประกอบกัน ก็ได้ดังนี้
*Main> (snd . findMax . annotate_sum . sublists) [-1,2,5,-1,3,-2,1]
[2,5,-1,3]

Related link from Roti

5 comments:

Anonymous said...

เป็นวิธีแก้ปัญหาที่แปลกมากครับ ไม่คุ้นเคย คิดตามแล้วงง ๆ พอเข้าไปอ่านใน google group ปรากฏว่าคนตั้งคำถามบ่นเรื่องวิธีคิดแบบ haskell เหมือนกัน

I've read tutorials about the syntax of Haskell, but I can't seem to
find any that teach you how to really "think" in a Haskell way. Is there
anything (books, online tutorials, exercises) that anyone could recommend?

เป็นไปได้สองอย่างคือ คนเราถนัดคิดแบบ imperative มากกว่า กับเราถูกสอนให้เขียนโปรแกรมแบบ iterative มากไป

ziddik::zdk said...

สั้นๆเลย
มึน [+_+]

PPhetra said...

คุณ bow: ผมว่าจะรอถามอาจารย์มะนาวเหมือนกัน
ว่า mode การคิดแบบ functional นี่
จริงๆแล้วมันเป็นธรรมชาติแค่ไหน

ส่วนตัวรู้สึกว่า เวลาคิดแก้ปัญหาด้วย haskell นี่
ต้องเริ่มจากหา recursive pattern ก่อนเลย
พอได้ pattern ก็จะเริ่มมองหา standard function
ที่ตรงกับ pattern นั้น หรือใช้ apply กับ pattern นั้นๆได้

ส่วนใหญ่พอไปเห็นที่คนอื่นเขียนแล้ว ผมก็จะนึกว่า
มันคิดอย่างไงวะ ถึงออกมาได้อย่างนี้
(ซึ่งก็เป็นที่มาของ post นี้เหมือนกัน)

jittat said...

โอ้ว จอร์ด

ผมกำลังดูว่าจะมองเป็น function แบบอื่น ได้หรือเปล่า

ตอนนี้กำลังลองทำดูเหมือนกันครับ คือผมรู้วิธีที่หาคำตอบได้ใน O(n) เมื่อ n เป็นขนาดของลิสต์ แต่ว่า มันเป็นแบบ imparative กำลังดู ๆ ว่าจะเขียน/มองเป็น functional ได้ยังไงดี

jittat said...

(อ่า... เขียนไม่ครบ)

บางที มันก็ดูไม่ค่อยเป็นธรรมชาติเหมือนกันนะครับ
แต่ว่าผมว่า "ธรรมชาติ" มันก็อาจจะขึ้นกับความเคยชินเหมือนกันนะครับ