Functional Programming #5 : Filter-Map-Reduce

เกริ่นนำ

Filter-Map-Reduce เป็นฟังก์ชันช่วยในการทำงานของ List เหมือนกับ sum หรือ take เป็นต้น แต่ที่แยกออกมาต่างหากนั้น เพราะสามตัวนี้ทำงานสอดประสานกันได้เป็นอย่างดี และมีความสามารถสูงมาก ว่ากันว่ามีฟังก์ชันเพียงสามตัวนี้ ก็สามารถทดแทนฟังก์ชันที่ช่วยจัดการเกี่ยวกับ List ได้เกือบทั้งหมด  ฟังก์ชันทั้งสามนี้เป็นฟังก์ชันมีระดับด้วยกันทั้งสิ้น ทำให้มีความยืดหยุ่นสูง เรามาลองดูรายละเอียดกันครับ

ฟังก์ชัน filter

ฟังก์ชัน filter นั้นรับพารามิเตอร์สองตัวครับ ตัวแรกเป็นเงื่อนไข และตัวที่สองเป็น List อารมณ์เดียวกันกับ takeWhile ครับ การทำงานก็ไม่มีอะไรซับซ้อนครับ ไล่ list แต่ละตัว เอาเข้าฟังก์ชันในพารามิเตอร์ตัวแรก ถ้าเงื่อนไขเป็นจริง เก็บไว้ ถ้าไม่จริงก็ทิ้งไป ผลลัพธ์จึงได้เป็น List ใหม่ ที่เหลือเฉพาะตรงตามเงื่อนไขที่กำหนดเท่านั้น ถ้าเทียบกับ takeWhile แล้วมันต่างกันนิดเดียวครับ คือ takeWhile มันจะหยุดเมื่อเงื่อนไขเป็นเท็จ แต่ filter มันจะไม่หยุด มันจะวิ่งไปจนหมด List  ซึ่งมันก็ตรงตัวกับคำว่า filter เช่น ถ้าเราต้องการตัดเอาเลขคี่ออกจาก List ให้หมด เราเขียนอย่างนี้ได้ครับ

filter even [1..10]             -- [2, 3, 4, 6, 10]

เราสามารถสร้างฟังก์ชัน filter ขึ้นมาลักษณะเดียวกันกับ takeWhile ได้โดย

filter' _ [] = []
filter' expr (x:xs) =
    case expr x of
        True  -> x : filter' expr xs
        False -> filter' expr xs

คงไม่ต้องอธิบายมากมายครับ เพราะไม่ได้แตกต่างกับ takeWhile ซักกี่มากน้อย ประเด็นที่ยังคาใจเล็ก ๆ อยู่ที่ filter’s expr xs นั้นเขียนซ้ำสองหน ไม่ชอบเลย เราสามารถเขียนครั้งเดียวก็ได้โดยเอา filter’s expr xs ไปใส่ไว้ในตัวแปร จำได้ไหมครับ FP ก็สามารถสร้างตัวแปรเอาไว้ใช้ได้ แต่สร้างแล้วห้ามเปลี่ยนค่า  จริง ๆ แล้วก็สร้างเพื่อลดความซ้ำซากนั่นแหละครับ การใช้นั้นอาศัยโครงสร้างโปรแกรม let-in ดังนี้ครับ

filter' _ [] = []
filter' expr (x:xs) =
let rest = filter' expr xs
in
    case expr x of
        True  -> x : rest
        False -> rest

ฟังก์ชัน map

ฟังก์ชัน map เป็นการนำเอาฟังก์ชันที่ส่งเป็นพารามิเตอร์ นั้นไปกระทำกับ list ทีละตัว ได้ผลลัพธ์มาเป็น List ใหม่ ซึ่งใช้หลักการแทนทีดังนี้ครับ

map f  [1, 2, 3, 4]     --  [f 1, f 2, f 3, f 4]

ง่าย ๆ เท่านี้ครับ ลองดูตัวอย่างครับ ถ้าเราต้องการสร้าง List ใหม่ ที่ยกกำลังจาก List เดิม เขียนอย่างนี้ครับ

map (^2) [1, 2, 3, 4]   -- [1, 4, 9, 16]

เราสามารถสร้างฟังก์ชัน map ง่ายๆ ได้ดังนี้ครับ

map' f [] = []
map' f (x:xs) = f x : map' f xs

ฟังก์ชัน reduce

มาถึงฟังก์ชันตัวสุดท้าย ที่น่าจะเก่งที่สุดเรียกว่า reduce มองว่าเหมือนกัน sum หรือ product ในแง่ที่มันยุย List ทั้ง List ให้เหลือค่าเดียว โดยที่เราสามารถเลือกฟังก์ชันในการรวบเองได้ ไม่จำเป็นต้อง เป็น + หรือ * ฟังก์ชันอะไรก็ได้ที่รับค่าสองค่าแล้วส่งกลับออกมาเป็นค่าเดียว ส่งฟังก์ชันนั้นเป็นพารามิเตอร์ตัวแรก  เข้าใจไม่ยากนะครับ

ฟังก์ชัน reduce นั้นจริง ๆ ถือว่า out ไปแล้วครับ เพราะการรวมจากซ้ายมาขวา หรือย้อนจากขวามาซ้าย มันอาจจะได้ผลลัพธ์ไม่เท่ากัน มันจึงควรแยกออกเป็นสองตัว ซ้ายตัว ขวาตัว เพื่อป้องกันความสับสน จึงเปลี่ยนชื่อเป็น fold แทน ดังนั้นถ้าทำจากซ้ายไปขวาเรียกว่า foldl และ ถ้าทำจากขวาไปซ้าย เรียกว่า foldr เรามาบวกหนึ่งถึงร้อยกันครับ กรณีใช้ foldl หรือ foldr ได้ผลไม่ต่างกัน  เราสามารถใช้ foldl แทน sum ได้ดังนี้ครับ

foldl (+) 0 [1..100]         -- 5050

หรือทำงานแทน product ก็ได้ ดังนี้ครับ

foldl (*) 1 [1..5]           -- 120

พารามิเตอร์ ตัวแรกคือฟังก์ชันที่รับพารามิเตอร์สองตัว แล้วพารามิเตอร์ตัวที่สองคือค่าเริ่มต้น และตัวที่สามคือ List ครับ  เรามาลองดูการทำงานของ ผมใช้วงเล็บแสดง จะได้เห็นถึงความจำเป็นของค่าเริ่มต้นครับ และลำดับขั้นตอนของ foldl และ foldr ครับ

foldl (*) 6 [1..5]   --  (((((6* 1) * 2) * 3) * 4) * 5)  ได้ผลลัพธ์ 720
foldr (*) 6 [1..5]   --  (1 * (2 * (3 * (4 * (5 * 6)))))  ได้ผลลัพธ์ 720

ถ้าการรวบเป็นการบวกหรือคูณ ไม่ว่าจะใช้ foldl หรือ foldr จะได้ค่าเดียวกันครับ เพราะการคูณและการบวก มีคุณสมบัติการสลับที่ (Commutative) แต่การลบและการหารไม่มีคุณสมบัตินี้ ดังนั้น

foldl (-) 6 [1..5]   --  (((((6 - 1) - 2) - 3) - 4) - 5)  ได้ผลลัพธ์ -9
foldr (-) 6 [1..5]   --  (1 - (2 - (3 - (4 - (5 - 6)))))  ได้ผลลัพธ์ -3

แต่ในงานส่วนมากที่พบ ผมเห็นว่าบวกและคูณใช้งานมากกว่าลบหรือหาร จึงไม่มีปัญหาในการที่จะใช้ foldl หรือ foldr เพราะจะได้ค่าเดียวกัน แต่เวลาใช้ทุกครั้งต้องคำนึงเรื่องลำดับนี้ให้ดีครับ จะได้ไม่พลาด

เปรียบมวย filter map reduce

ถ้าผมถามว่าในสามฟังก์ชัน filter map reduce นั้น ตัวใดเจ๋งที่สุด ลองเดาเล่นๆ  ดูก่อนผมเฉลยนะครับ ถ้ายังไม่ได้คิดขอให้คิดก่อนครับพร้อมเหตุผล คิดแล้วนะครับ ถ้าคิดแล้วอ่านต่อได้ครับ

ผมขอเฉลยเลย ก็อย่างที่ใบ้เอาไว้ข้างต้น reduce เจ๋งที่สุด เพราะอะไรหรือครับ ก็ลำพัง reduce เอง เป็นฟังก์ชันครอบจักรวาล สามารถสร้างฟังก์ชันอื่น ๆ ได้ คล้าย ๆ กับเรื่องของเกตไฟฟ้า NAND เกตเรียกว่า universal gate เพราะสามารถสร้างเกตใด ๆ ก็ได้ ดังนั้นในหน่วยความจำของคอมพิวเตอร์ เช่น Flash Drive ก็นิยมใช้ NAND มาเป็นตัวสร้าง  reduce ก็เช่นกันครับมันเจ๋งตรงที่มันสามารถสร้าง ได้ทั้ง filter และ map ครับ มาลองใช้ reduce สร้าง filter และ map กันเลยครับ

filter' f list  = foldr (\x y -> if f x then x : y else y) [] list
map' f list     = foldr (\x y -> (f x) : y) [] list

ท่านคงอาจสงสัยว่ามันทำได้อย่างไร  reduce มันต้องยุบเหลือค่าเดียวสิ มันจะออกมาเป็น List ได้อย่างไร ทั้ง filter’ และ map’ ล้วนแล้วแต่ให้ผลลัพธ์เป็น List ด้วยกันทั้งสองเลย เรื่องนี้ต้องเปลี่ยนมุมมองเล็กน้อยครับ มองมุมนี้ครับ ถ้าในแต่ละรอบของ reduce แทนที่จะคำนวณสะสมค่าในแต่ค่าใน List  แต่หากเป็นการเพิ่มพูนต่อ List หละ ผลลัพธ์มันก็ได้ค่าเดียวเหมือนเดิม แต่ค่านั้นคือ List ทั้งตัวครับ ดังนั้นมันจึงแทน map ได้ ส่วน filter ก็จะซับซ้อนกว่า map เล็กน้อย ตรงที่มันมีการคัดเลือกบางตัวออกไป บางตัวรวม List บางตัวทิ้งไป อย่างนี้พอเข้าใจนะครับ

อย่างนี้ท่านก็บอกว่าในเมื่อ reduce มันแทน map กับ filter ได้อย่างนี้ก็ใช้แต่ reduce สิ อย่าเลยครับ ชื่อมันไม่สื่อ อ่านเองงงเอง เอาเป็นสามประสานแบบนี้รู้เรื่องดีกว่ามากครับ  และ filter-map-reduce รวมตัวสามประสานกลายเป็นอาวุธที่ทรงพลังมากในการนำไปแก้ปัญหา สามารถทดแทน Imperative ได้หลากหลาย เดี๋ยวลองตัวอย่างข้างล่างดูครับ

แต่ก่อนถึงตัวอย่าง ผมขอชี้ให้เห็นถึงจุดอ่อนของ Map-Filter-Reduce ก่อนครับ ท่านมองออกไหมครับว่ามันต่างกับ takeWhile หรือ find อย่างไร ใช่แล้วครับ takeWhile และ find นั้น เมื่อพบเงื่อนไขที่ต้องการมันจะหยุดทำงาน ส่วน Map-Filter-Reduce นั้น ลำพังตัวมันเองไม่มีกลไกการหยุดครับ ถ้าให้ List ขนาด 1,000 ให้มันทำ มันก็จะต้องทำให้ครบ 1,000 ตัว ลองนึกภาพดูนะครับ ถ้ามันเป็นงานที่ต้องทำหลายเครื่อง เช่นมีแฟ้มหนึ่งพันแฟ้ม ให้หลายเครื่องค้นหาอะไรซักอย่างหนึ่ง ยังไงมันก็ต้องไปหาทั้ง 1,000 แฟ้ม หยุดก่อนด้วยตัวเองไม่ได้ ดังนั้นถ้าพิจารณาในมุมมองนี้แล้ว การทำ Filter เพื่อลดจำนวนของสมาชิกที่ต้อง Map นั้นเป็นไปไม่ได้ เพราะคำสั่งได้ส่งข้ามเครื่องไปแล้ว อย่างไรเสียก็คงต้องทำอยู่ดี เราหันมาใช้ Reduce ทำการ Filter ในขั้นตอนการยุบรวมแทน ดังนั้นที่นิยมใช้จริง ๆ จึงเป็น MapReduce โดยไม่มี Filter นั่นเอง

 การประยุกต์ Project Euler

ถ้าอยากซ้อมมือแก้โจทย์ปัญหา ผมแนะนำ http://www.projecteuler.net ซึ่งชื่อเวปนั้นตั้งให้เป็นเกียรติแก่สุดยอดนักคณิตศาสตร์ชาวสวิสนามว่าเลออนฮาร์ด ออยเลอร์อันโด่งดัง โดยเวปนี้จะมีโจทย์ปัญหาทางคณิตศาสตร์ให้ซ้อมมือในการเขียนโปรแกรม ซึ่งไม่ต้องตกใจ คณิตศาสตร์พื้น ๆ ครับ บวกลบคูณหารธรรมดา ไม่มีคณิตศาสตร์ชั้นสูงแต่อย่างใด

โจทย์มีตั้งแต่ง่าย ๆ ไปจนยาก ๆ คละกันไป เมื่อรันโปรแกรมแล้ว จะได้ค่าผลลัพธ์เป็นตัวเลขเพียงแค่ค่าเดียวในทุกโจทย์เลย ซึ่งไม่มีเฉลยวิธีทำ แต่เราสามารถนำเอาคำตอบที่หามาได้ไปลองกรอกดู มันจะบอกแค่ว่าถูกหรือผิด ถ้าผิดก็ไปทำมาใหม่ครับ ปัจจุบันที่เขียนบทความนี้ มีโจทย์อยู่ทั้งหมด 476 ข้อ อย่าไปยึดติดว่าเป็นโจทย์คณิตศาสตร์ ไม่น่าสนใจไกลตัวนะครับ  จริง ๆ แล้วอย่าไปคิดอย่างนั้นครับ มองมันว่าเป็นทักษะการเขียนโปรแกรมจะดีกว่า สุดแต่การนำไปประยุกต์ในอนาคตของแต่ละท่านครับ

ลืมบอกไปนะครับ ผู้ออกแบบโจทย์เหล่านี้บอกว่า ทุกข้อนี้ใช้กำลังเครื่องคอมพิวเตอร์คำนวณ ไม่ควรเกิน 1 นาที เครื่องธรรมดานี่แหละครับที่ราคาถูกที่สุดเท่าที่หาซื้อในท้องตลาดได้ ไม่ต้องใช้ถึงขนาด Core i7 สุดยอดแต่อย่างใด ถ้าลองทำดูแล้วเกินหนึ่งนาที แสดงว่าอัลกอริทึมที่ใช้ยังใช้ไม่ได้ครับ อาจต้องคิดใหม่ทำใหม่ ในบทความนี้ผมจะใช้ความรู้ที่กล่าวมาตั้งแต่บทความแรกมาใช้ในการแก้ปัญหา 5 ข้อแรกที่ได้จากเวปดังกล่าว ท่านลองคิดดูเองก่อนครับและลองทดสอบกับภาษา paradigm Imperative ที่ท่านถนัดดูนะครับ

แต่ก่อนที่จะทำโจทย์กัน ก็ขอบอกว่าวิธีที่เฉลยนั้นเป็นเพียงตัวอย่างนะครับ ไม่จำเป็นต้องเป็นวิธีที่ดีที่สุด แต่หากเป็นวิธีที่ยอมรับได้เมื่อพิจารณาในด้านประสิทธิภาพ กล่าวคือทำงานเสร็จภายในหนึ่งนาทีทุกข้อ ถ้าท่านมีวิธีที่ดีกว่า ก็มาแชร์กันบ้างครับ

 โจทย์ข้อที่ 1 : Multiples of 3 and 5

โจทย์ : เมื่อกำหนดตัวเลขที่ต่ำกว่า 10 เอาเฉพาะที่หารด้วย 3 หรือ 5 ลงตัว ซึ่งก็คือ 3, 5, 6, 9 ถ้าเอาเลขที่ได้ทั้งหมดจากการนี้บวกเข้าด้วยกัน จะได้ผลลัพธ์ 23 จงหาผลรวมของตัวเลขทุกตัวที่หารด้วย 3 หรือ 5 ลงตัว ที่ต่ำกว่า 1000

เฉลยได้ดังนี้ครับ

foldl (+) 0 $ filter (\x -> x `mod` 3 == 0 || x `mod` 5 == 0) [1..999]

อย่างที่กล่าวไว้ข้างต้น เราสามารถยุบรวมการทำงาน filter เข้ากับ reduce ทำให้เหลือ reduce แต่อย่างเดียว ได้ดังนี้ครับ

 foldl (\x y -> if  y `mod` 3 == 0 || y `mod` 5 == 0 then x + y else x) 0 [1..999]

 โจทย์ข้อที่ 2 : Even Fibonacci numbers

โจทย์: ค่าของฟิโบนัซซี่เกิดจากการบวกกันของสองค่าก่อนหน้า ถ้าเริ่มจาก 1, 2 จะได้ ฟิโบนัซซี 10 ค่าแรกดังนี้ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … พิจารณาเฉพาะค่าของฟิโบนัซซีที่ไม่เกิน 4ล้าน จงหาผลรวมของอนุกรมที่เป็นเลขคู่

เฉลยได้ดังนี้ครับ

fib’ = 1 : 1 : [a + b | (a, b) <- zip fib’ (tail fib’) ]
fib = tail fib’
foldl (+) 0 $ takeWhile (<4000000) $ filter even fib

 โจทย์ข้อที่ 3 : Largest prime factor

โจทย์: ค่าตัวประกอบจำนวนเฉพาะของ 13195 คือ 5, 7, 13 และ 29 จงหาค่าตัวประกอบเฉพาะที่มีค่ามากที่สุดของ 600851475143

ที่โจทย์ต้องการหาคือ ตัวเลขสูงสุด ที่หาร 600851475143 ลงตัวเป็นจำนวนเฉพาะคือมีเฉพาะตัวมันเองและ 1 เท่านั้นที่เอามาหารมันได้ลงตัว เฉลยได้ดังนี้ครับ

import Data.List as List (find)
sqrtInt n =
    let m = floor $ sqrt (fromIntegral n)
    in
       if (odd m) then m else (m - 1) 
isPrime n = (length $ takeWhile (\x -> n `mod` x /= 0) list) == length list    where list = (2 : [3, 5..(n-1)])
maxPrimeDiv' m 1 = if m `mod` 2 == 0 then 2 else m
maxPrimeDiv' m n
    | m `mod` n /= 0 = cont
    | isPrime n = n
    | otherwise = cont
         where cont = maxPrimeDiv' m (n-2)
maxPrimeDiv m = maxPrimeDiv' m (sqrtInt m)
maxPrimeDiv 600851475143

โจทย์ข้อนี้น่าสนใจครับ เพราะแสดงให้เห็นถึงการใช้ฟังก์ชันหลายตัวทำงานสอดประสานกันเพื่อแก้โจทย์ปัญหา ผมลองใช้การเรียกตัวเองมาแก้ปัญหาดูบ้าง ก็ได้ผลอย่างที่เห็น  ลองเทียบกับ Imperative น่าจะพบว่าโจทย์ข้อนี้มีซับซ้อนพอสมควร และยังจะเห็นได้ว่า การเขียนโปรแกรมแบบไม่มี Sequence จะทำได้อย่างไร ทดลองดูได้ครับ

โจทย์ข้อนี้ไม่เหมาะกับการใช้ Map-Reduce เพราะประสิทธิภาพไม่ดี และถ้าไม่อยากเขียนแบบการเรียกตัวเอง ก็สามารถใช้ฟังก์ชันที่เรียนไปแล้วช่วยได้ดังนี้ครับ

import Data.List as List (find)

sqrtInt n =
    let m = floor $ sqrt (fromIntegral n)
    in
        if (odd m) then m else (m - 1)
isPrime n = (length $ takeWhile (\x -> n `mod` x /= 0) list) == length lis
    where list = (2 : [3, 5..(n-1)])
maxPrimeDiv m = maxPrimeDiv' m (sqrtInt m)
maxPrimeDiv 600851475143

สังเกตที่ where นะครับ where นั้นเหมือน let in แต่สร้างตัวแปรไว้ท้ายแทนที่จะเป็นข้างบน จริง ๆ แล้ว let-in กับ where มีการใช้งานที่ต่างกันพอสมควร แต่ผมขอข้ามไปครับ

โจทย์ข้อที่ 4 : Largest palindrome product

โจทย์: ตัวเลขพาลินโดรมคือเลขที่อ่านจากหน้าไปหลังและในทางกลับกันได้ค่าเดียวกัน ตัวเลขพาลินโดรมที่มาค่ามากที่สุดที่เกิดขึ้นตัวเลขสองหลักคูณกันคือ 9009 ซึ่งได้มาจาก 91 x 99 จงหาค่าพาลินโดรมที่มีค่ามากที่สุดที่เกิดจากผลคูณของเลข 3 หลักสองจำนวน

เฉลย

isPalinString str
    | length str <= 1  = True
    | head str /= last str = False
    | otherwise = isPalinString $ tail $ init str
isPalinNum num1 num2 = isPalinString $ show (num1 * num2)
palinList =  [(a, b, a*b, isPalinNum a b) | a <- [1..999], b <- [1..999]]
max' (a1, b1, a_b1, bool1) (a2, b2, a_b2, bool2)
    | bool2 == True && a_b2 > a_b1 = (a2, b2, a_b2, bool2)
    | otherwise = (a1, b1, a_b1, bool1)
findMaxPalin list = foldl max' (-1, -1, -1, True) list
findMaxPalin palinList

พระเอกในข้อนี้คือ tuple ขนาด 4 สมาชิก ลองทำความเข้าใจดูครับ

โจทย์ข้อที่ 5 : Smallest multiply

โจทย์: 2520 คือตัวเลขที่น้อยที่สุดที่หารโดย 1 ถึง 10 ลงตัวทั้งหมด จงหาเลขที่น้อยที่สุดที่หารโดย 1 ถึง 20 ลงตัวทั้งหมด

เฉลย

import Data.List  as List (find)
remAll m n = (sum $ map (m `mod`) [1..n])
noRem n = find (\(m, r) -> r == 0) $ map (\m -> (m, remAll m n)) [2..]
noRem 20

ข้อนี้ใช้ map ถึงสองครับ น่าสนใจครับ

 สรุป

เราเดินทางกันมาไกลครับ ตั้งแต่การปั้นน้ำในบทความก่อนๆ มาถึงบทนี้ท่านคงเห็นแล้วว่ามันกลายเป็นตัวได้อย่างไร ผมคงขอจบบทความการแนะนำ Functional Programming แต่เท่านี้ครับ แต่มันยังไม่จบนะครับ การประยุกต์ยังมีอีกหลายหลายที่ท่านจะเห็นในบทความต่อๆ ไป หวังว่าเพื่อนใหม่ของท่านคนนี้ ท่านจะพึงพอใจไม่มากก็น้อย  ไม่ใช่สิต้องมากสิ ถ้าน้อยมันจะมีประโยชน์อะไร

You may also like...

2 Responses

  1. Kai says:

    ขอบคุณครับ

  2. avrthekop says:

    ขอบคุณบทความดีๆครับ

Leave a Reply

Your email address will not be published. Required fields are marked *