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]