P07 กับ List Moand

เห็นน้องป้อทำโจทย์ P07 ของ Ninety-Nine Lisp Problem ก็เลยกลับไปอ่านวิธีทำของตัวเอง แล้วก็พบว่าถึงแม้เวลาจะผ่านมา 4 ปีแล้ว ตัวเองก็ยังไม่เคยเข้าใจคำตอบของ Conor McBride เลย วันนี้ก็เลยได้ฤกษ์ทำความเข้าใจกับ List Monad ที่ Conor ใช้ตอบคำถามผม

เริ่มด้วยคำอธิบาย Monad ที่บอกว่า Monad คือ "an abstract datatype of actions" ซึ่งมีนิยามง่ายๆแค่นี้

class Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    return :: a -> m a

มันคือ pattern ฉนั้นอย่าพึ่งไปพยายามจินตนาการว่า มันทำอะไรได้บ้าง
หันกลับมาดู context ของ List บ้าง เรารู้ว่า type ของ List คือ [a] จะเห็นว่า type [a] มันสามารถมองเป็น m a ได้ (เพราะ type constructor มันมี free variable 1 ตัวเหมือนกัน) ฉนั้นเราลองมา implement ให้ List เป็น Monad กัน

เริ่มจาก implementation ที่ง่ายที่สุดก่อน ก็คือ return, return มี type เป็น a -> m a ฉนั้นกรณีของ List, คำสั่ง return 4 ก็ควรได้ค่า [4] ออกมา

instance Monad [] where
        return x = [x]

ตัวถัดมาก็คือ function >>= นิยามของ type มันคือ m a -> (a -> m b) -> m b
เปลี่ยน m a ให้เป็น [a] จะได้ [a] -> (a -> [b]) -> [b] จะเห็นว่า definition มันไกล้เคียงกับ map function ที่มี type เป็น [a] -> (a -> b) -> [b] ดังนั้นเราสามารถ implement >>= โดยใช้ map และ concat
หน้าตาออกมาดังนี้

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)

ได้นิยามของ List ในมุมมองของ Monad ออกมาอย่างงงๆ
แล้วมันมีประโยชน์อะไรหล่ะ ที่ทำ List type ให้เป็น instance ของ Monad type

ลองมาหัดใช้ List Monad ทำโจทย์

ถ้าให้ list ของ [1..10] มาให้หาตัวเลข 2 ตัวที่ผลคูณมีค่า = 16

ถ้าใช้ List Monad ก็จะเขียนแบบนี้

guard True xs = xs
guard False xs = []

solve = do
  x <- [1..10]
  y <- [x..10]
  guard (x * y == 16) (return (x,y))

ซึ่งมี form ที่ไกล้เคียงกับ solution ที่ใช้ List comprehension

[(x,y) | x <- [1..10], y <- [x..10], x * y == 16]

กลับมาที่ solution ที่ McBride เขียนตอบผม

flat1 :: Store a -> a
flat1 (E a) = return a
flat1 (S xs) = xs >>= flat1

ถึงตอนนี้พอจะรู้เรื่องกับคำอธิบายของเขาแล้ว

Your (flat xs) on a list of stores becomes my (xs >>= flat1), systematically lifting the operation on a single store to lists of them and concatenating the results. The return operation makes a singleton from an element. This way of working with lists by singleton and concatenation is exactly the monadic structure which goes with the list type, so you get it from the library by choosing to work with list types. In Haskell, when you choose a typed representation for data, you are not only choosing a way of containing the data but also a way to structure the computations you can express on that data