Pure functional programming with Haskell

เมื่อวันก่อนเห็น quicksort ที่ implement ด้วย Haskell
เห็นแล้วก็อื้งเล็กน้อย
อื้งเพราะอะไรลองติดตามดู

qsort[]     = []
qsort(x:xs) = qsort less ++ [x] ++ qsort more
              where less = [y | y <- xs, y < x]
                    more = [y | y <- xs, y >= x

บรรทัดแรกเป็นการบอกว่า
ถ้ามีคน call qsort โดย pass parameter เป็น empty array
ก็ให้ return ค่า empty array กลับไป

บรรทัดที่ 2 ฝั่งซ้าย บอกว่า
ให้ทำ pattern matching กับ array (parameter) ที่ pass เข้ามา
โดยให้ตัวแรกสุดของ array bound เข้ากับ ตัวแปร x
ส่วนที่เหลือ bound เข้ากับ ตัวแปร xs
สมมติว่า มีการสั่ง qsort [3,5,2,9]
x จะเท่ากับ 3 ส่วน xs จะเท่ากับ [5,2,9]

ส่วนฝั่งขวาของบรรทัดที่ 2 บอกว่า
ผลลัพท์ที่จะ return กลับไป เกิดจาก
การ recursive call qsort ด้วย parameter less
บวกกับ x บวกกับ recursive call qsort ด้วย paramter more
โดย less นั้นได้มาจาก
less = [y | y <- xs, y < x]
(ประโยคนี้ดูแปลกตามากมาก)
การตีความหมายให้เริ่มจาก y <- xs, y < x ก่อน
อันนี้หมายความว่า ให้ y คือ สมาชิกของ set xs โดยที่ค่า y ต้องน้อยกว่า x
less = [y | ...] ก็แปลตรงตัว
less ก็คือ y นั่นเอง โดยที่ datatype ของ y เป็น list (array)

ส่วน more = [y | ... ก็เป็นที่มากกว่าค่า x

เวลาสั่งทำงาน ก็เพียงแต่เรียก

Main> qsort [3,4,1,3,6,45,11,23]
[1,3,3,4,6,11,23,45]

ถ้าเขียนว่าข้างในทำงานอย่างไร ก็คงได้ step ประมาณนี้

qsort [3,4,1,3,6,45,11,23] 
  = qsort [1] ++ [3] ++ [4,3,6,45,11,23]
  = [] ++ [1] ++ [] ++ [3] ++ qsort[3] ++ [4] ++ qsort [6,45,11,23]
  .....

ที่บอกว่าอื้ง ก็คือ ทำไมมันช่างเป็นโปรแกรมที่อ่านเข้าใจง่ายเช่นนี้
(เข้าใจง่ายนี่หมายถึงว่า สายตาต้องชินกับการตีความ recursive +
รูัจัก syntax เบื้องต้นก่อนนะ)
ลองเทียบกับ java ดู

static void sort(int a[], int lo0, int hi0) {
        int lo = lo0;
        int hi = hi0;
        if (lo >= hi) {
            return;
        }
        int mid = a[(lo + hi) / 2];
        while (lo < hi) {
            while (lo<hi && a[lo] < mid) {
                lo++;
            }
            while (lo<hi && a[hi] >= mid) {
                hi--;
            }
            if (lo < hi) {
                int T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }
        }
        if (hi < lo) {
            int T = hi;
            hi = lo;
            lo = T;
        }
        sort(a, lo0, lo);
        sort(a, lo == lo0 ? lo+1 : lo, hi0);
    }

(ลอก code มาจาก http://clip.dia.fi.upm.es/Projects/ParForce/Final_review/slides/intro/node4.html )

ปล. มี game ที่เขียนด้วย Haskell ด้วยนะ
ชื่อ game Frag