Ninety-nine Lisp Problem #P07

วันนี้นั่งทำโจทย์ข้อที่ 7, ในแง่ของ clisp กับ erlang
ข้อนี้ไม่ยากนัก แต่ในแง่ของ haskell แล้ว program ออกมาไม่สวยนัก
ก็เลย mail ไปถามใน mailing list ของ haskell ดู
ซึ่งก็ได้ผล มีคนเก่งๆมาช่วยไขความกระจ่าง
ถือเป็น mailing list ที่น่าประทับใจอันหนึ่ง

ลองดูโจทย์

P07 (**) Flatten a nested list structure.
Transform a list, possibly holding lists as elements into a `flat' list by replacing each list with its elements (recursively).

Example:
* (my-flatten '(a (b (c d) e)))
(A B C D E)

Hint: Use the predefined functions list and append.

CLisp
ใช้ append ในการ ต่อ list 2 อันเข้าด้วยกัน

(defun my-flatten (lst)
  (cond ((not (listp lst)) (list lst))
        ((null lst) nil)
        (t (append (my-flatten (car lst))
                   (my-flatten (cdr lst))))))

Erlang
erlang ก็ใช้วิธีตามแบบ lisp มาติดๆ
แต่ด้วยการใช้ guard + pattern matching เข้ามาช่วย
ทำให้ดูง่ายกว่า clisp

-module(p07).
-export([flat/1]).

flat([]) -> [];
flat(X) when atom(X) -> [X];
flat([H|T]) -> flat(H) ++ flat(T).

Haskell
ข้อนี้ haskell ไม่สามารถทำตรงๆได้
เนื่องจาก type system ของ Haskell
ไม่สามารถกำหนด type nested array แบบนี้ได้

[1,2] type คือ [a]
[1,[2,3]] type คือ [[a]]
[1,[2,[3,4],5]] type คือ [[[a]]]

จากโจทย์ จะเห็นว่า list มันจะซ้อนกันกี่ชั้นก็ได้
ทำให้ไม่สามารถ declare type ได้

ถ้าจะแก้โจทย์นี้ ก็ต้องเปลี่ยน structure ของ list ก่อน
โดย declare เป็น abstract data type ขึ้นมาก
จาก
[1,[2,[3,4],5]]
ให้เป็น
[E 1, S[E 2, S[E 3, E 4], E 5]]

ตัว data type เรา declare แบบนี้

data Store a = E a | S [Store a]
             deriving (Show)

จากนั้นก็เขียน function

flat :: [Store a] -> [a]
flat [] = []
flat ((E x):xs) = [x] ++ flat xs
flat ((S x):xs) = flat x ++ flat xs

จะเห็นว่ามันยืดยาวไม่สวยงาม
ผมก็เลยเขียนไปถามใน mailing list
ลองอ่านที่เขาตอบมาดู
flatten a nested list
ผมชอบ solution ที่ Conor McBride ตอบมากสุด
ทำให้รู้ด้วยว่า list มันเป็น monadic structure ด้วย

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

magic อยู่ที่ function >>=
ซึ่งถ้าไปดูนิยามมันใน library ดู จะเห็นนิยามมันเป็นแบบนี้

instance Monad [ ] where
    (x:xs) >>= f = f x ++ (xs >>= f)
    []     >>= f = []
    return x     = [x]
    fail s       = []