Photo credit — Won Young Park

ลาก่อย for loop — map, reduce และผองเพื่อน

for(int i = 1; i < array.length; i++) {
  doSomething(array[i]);
}

ผมเชื่อว่าหลายๆคนคงได้เขียน code หน้าตาประมาณนี้บ่อยๆ หลายครั้งหน้าตาก็ดูซับซ้อนมากกว่านี้ ต้องใช้เวลาเพ่งอยู่นานมากกว่าจะเข้าใจ code ที่ตัวเองเคยเขียนไว้ ซึ่งบางครั้งมันก็เป็นเพราะเราเขียนไม่ดีเองด้วย แต่แล้ววันหนึ่งผมก็ได้รู้จักกับ function ที่ไม่เคยใช้มาก่อนอย่าง

map, flatMap, reduce, fold, filter, zip

function เหล่านี้ใช้ในการจัดการกับ collection จำพวก Array, List, Vector และผองเพื่อน iterable ทั้งหลาย(ทั้งนี้ขึ้นอยู่กับ language support ด้วย) ซึ่งหลายๆกรณีก็สามารถใช้แทน loop หรือ recursive function ได้เลย สำหรับผมแล้ว มันทำให้ code สะอาด และอ่านง่ายขึ้นมาก ส่วนเขียนง่ายหรือเปล่า ตอนแรกๆผมก็รู้สึกว่ายาก แต่ช่วงนี้ผมแทบไม่ได้เขียน loop เลยครับ เพราะรู้สึกว่าวิธีนี้เขียนง่ายกว่าในหลายๆกรณี และ refractor ง่ายกว่าด้วย

ในโลกของ Big Data ถ้าใครเคยรู้จัก Hadoop ก็คงได้ยิน MapReduce มาบ้าง ซึ่ง แนวคิดของ MapReduce เองก็คล้ายๆกับ function map และ reduce ที่เราจะพูดถึงกัน หรือ Apache Spark เอง หากใครเคยเขียนก็จะพบว่ามันใช้ function พวกนี้เยอะมากๆ นอกจากนี้ยังเป็นหัวใจของ (Functional) Reactive Programming ด้วย ซึ่งเจ้า Reactive Programming เนี่ยมันมีประโยชน์ในเรื่องของการจัดการกับ asynchronicity/parallelsim ผมจะเก็บไว้พูดถึงในคราวต่อๆไป แต่ถ้าใครใจร้อนก็แนะนำให้ไปอ่านที่นี่ก่อนเลยครับ

ขายของกันมาพอแล้ว ก่อนที่จะเริ่มเข้าเนื้อหาหลัก จะบอกว่าตัวอย่าง code จะเป็นภาษา scala ครับเนื่องจากความครบของ language feature และความคุ้นเคยภาษานี้ของผมเอง แต่ผมเชื่อว่าจะสามารถอ่านและนำไปปรับใช้กับภาษาอื่นๆที่ support higher-order function ได้ไม่ยาก

Higher-order function กับ collection

คราวที่แล้ว ผมได้พูดถึงภาพรวมของ functional programming และได้กล่าวถึง higher-order function ไปบ้างเล็กน้อย ซึ่งเป็นสิ่งที่เราจะสนใจเป็นพิเศษในคราวนี้ ถ้าใครยังไม่ค่อยเข้าใจว่า functional programming คืออะไร เชิญชม…

Hello, Functional Programming!

higher-order function นั้นจะต้องมีคุณสมบัติอย่างน้อยหนึ่งข้อในนี้:

1. parameter อย่างน้อย 1 ตัวเป็น function
2. return type เป็น function

สำหรับ function เราจะพูดถึงกันวันนี้มีคุณสมบัติข้อ 1 แน่ๆ สำหรับข้อ 2 นั้นจะมีหรือไม่ก็ได้ โดยมุ่งไปที่การจัดการกับ collection

function เหล่านี้อาจจะหน้าตาต่างกันไปในแต่ละภาษาเนื่องมาจากปรัชญาของภาษาที่ไม่เหมือนกันตัวอย่างเช่น map

scala, js: 
  numbers.map(x => x + 1)
ruby:
  numbers.map { |x| x + 1 }
python: 
  map(lambda x: x + 1, numbers)
==========
result:
  numbers = [0, 1, 2, 3] => [1, 2, 3, 4]

ตัวอย่างที่ยกมานี้ให้ผลลัพธ์แบบเดียวกัน แต่เขียนไม่เหมือนกัน สังเกตได้ว่าสำหรับใน list นี้ python จะดูแปลกแยกนิดนึง ถ้าถามว่าแบบไหนดู functional ที่สุดก็คงตอบว่าแบบ python แต่ส่วนตัวแล้วผมชอบแบบที่เป็น object function อย่างใน scala, ruby, js มากกว่า

จากตัวอย่างข้างบน เราสามารถเปลี่ยน lambda expression เป็น function ก็ได้ครับอย่างเช่นในกรณี scala

def topUp(n: Int) = n + 1
numbers.map(topUp)

เราต้องประกาศลำดับ parameter ให้ถูกต้อง เพื่อให้ภายใน higher-order function นั้นนำ function ของเราไปใช้งานได้ไม่มีปัญหา ภาษาอื่นๆก็จะคล้ายๆกันครับ

จะเห็นว่าจากตัวอย่าง map ข้างบนเป็นการ apply function กับทุกๆสมาชิกใน collection ซึ่งเราสามารถกำหนด function ได้เอง ที่สำคัญคือ function เหล่านี้ (map, filter, …)จะไม่ไปแก้ไขอะไรใน collection ตั้งต้นเลย แต่จะสร้าง collection ใหม่ขึ้นมาแทน กล่าวคือเป็น pure function นั่นเอง ซึ่งเป็นคุณสมบัติที่ดีในการจัดการกับ parallelism อย่างที่บอกไว้ใน blog ที่แล้วครับ

Map

map เป็น function ที่ใช้ในการแปลงร่างสมาชิกใน collection ด้วย function ที่ใส่เข้าไป ลองดูตัวอย่างเพิ่มเติมกันครับ

จาก code ข้างต้น ถ้าเราต้องการจะสร้าง Map(data structure) ที่โดยมี key เป็น id ของหนังสือ เราสามารถใช้ function map ในการจัดการได้ดังนี้

สมมติว่าเราต้องการรายชื่อของผู้เขียนทั้งหมดมาเก็บไว้ใน Set จะพบว่ารายชื่อผู้เขียนมันซ่อนอยู่ใน List อีกทีนึงถ้าเราใช้ map ธรรมดา สุดท้ายแล้วเราต้องทำการ flatten มัน หรือทำให้ collection มันไม่ซ้อนกัน อย่างเช่น

List(List(1, 2), List(3)).flatten
// => List(1, 2, 3)

แต่เนื่องจากเรื่องแบบนี้มันเกิดขึ้นบ่อย ก็เลยมีสิ่งที่เรียกว่า flatMap (บางภาษาใช้ concatMap) ซึ่งก็คือการ map และ flatten นั่นเอง

Filter

อันนี้คิดว่าน่าจะเข้าใจง่ายที่สุด เป้าหมายของ function นี้คือเราจะกรองสมาชิกบางตัวออกไป ซึ่งรับ parameter เป็น predicate function หรือ function ที่มี return type เป็น boolean ถ้าสมาชิกใน collection นั้นทำให้ predicate return true ก็จะเก็บสมาชิกตัวนั้นเอาไว้ แต่ถ้าเป็น false ก็จะทิ้งไป

ในตัวอย่างนี้จะต้องการรายชื่อของหนังสือที่มี rating มากกว่า 4.0

Reduce/Fold

สำหรับ function นี้จะเข้าใจยากกว่าสองอันก่อนนิดหน่อย แนวคิดของ reduce และ fold นั้น จะเป็นการไล่ไปตาม collection และกระทำการแบบสะสม(accumulated) ผลลัพธ์ไปเรื่อยๆตามลำดับ ซึ่งสามารถเริ่มจากด้านซ้ายก่อนหรือขวาก่อนก็ได้(โดยปกติแล้วจะเริ่มจากซ้าย) ตัวอย่างนี้เป็นการหาผลรวม

จะเห็นได้ว่า ผมประกาศ parameter ไว้สองตัว คือ acc(accumulated) กับ curr(current) โดย reduce กับ foldLeft จะทำงานคล้ายๆกัน ลองมาดู reduce กันก่อนครับ โดยผมจะให้ [] แสดงถึง acc ในแต่ละรอบ และตัวที่อยู่นอกวงเล็บคือ curr

[1] + 2
[(1) + 2] + 3
[((1) + 2) + 3] + 4
[(((1) + 2) + 3) + 4] + 5

สำหรับ fold นั้น สิ่งที่แตกต่างกันก็คือ เราสามารถกำหนดค่าเริ่มต้น(initial value) ได้ เพราะฉะนั้น อย่างในกรณีนี้ก็จะไม่เริ่มต้นที่ [1] + 2 แต่จะเป็น [0] + 1 แทน

ในบางภาษาก็จะมีแค่ fold อย่างเดียว หรือ reduce อย่างเดียว แต่ก็สามารถเพิ่ม initial value ได้ อย่างเช่น reduce ใน javascript มี syntax แบบนี้

arr.reduce(callback[, initialValue])

ซึ่งเราจะไม่ใส่ค่าเริ่มต้นก็ได้ แต่ถ้าเราใส่ค่าเริ่มต้นเข้าไปก็จะประพฤติตัวเหมือน fold แล้วล่ะครับ

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

ตัวอย่างแรก ผมทำการกำหนดค่าเริ่มต้นเป็น List[Int] แล้วนำผลรวมในขณะนั้นมาต่อ List ไปเรื่อยๆ กับอีกตัวอย่างหนึ่ง ผมสร้าง function contains เพื่อตรวจสอบว่ามีสมาชิกที่สนใจอยู่ใน List หรือเปล่า จะเห็นได้ว่า return value ของ fold นั้นจะมี type เดียวกับค่าเริ่มต้นครับ

สังเกตว่า reduce เนี่ยจริงๆแล้วก็เป็นรูปแบบพิเศษของ fold ที่เลือกสมาชิกตัวแรก(หรือตัวสุดท้ายในกรณี reduceRight) มาเป็นค่าเริ่มต้น ซึ่งตรงนี้มีความสำคัญอยู่ครับ เนื่องจากจะทำให้ function ใน reduce นั้นมี สมบัติการเปลี่ยนกลุ่ม(associativity)ครับ เผื่อว่าใครจำคณิตศาสตร์วัยเด็กไม่ได้ สมบัติการเปลี่ยนกลุ่มเป็นแบบนี้

(3 + 4) + 5 = 3 + (4 + 5) // + มีสมบัติการเปลี่ยนกลุ่ม
(3 - 4) - 5 ≠ 3 - (4 - 5) // - ไม่มีมีสมบัติการเปลี่ยนกลุ่ม

ซึ่ง fold ไม่สามารถรับประกันได้ ถ้าไม่เชื่อทดลองกับตัวอย่าง accumulatingList ด้านบนดูได้ครับ(ถือเป็นการพิสูจน์ด้วยการยกตัวอย่างค้าน)

แล้วมันสำคัญยังไง? คำตอบคือถ้าเปลี่ยนกลุ่มได้ ก็จะสามารถ parallelize มันได้ครับ เพราะเราจะสามารถตัด collection ออกเป็นส่วนๆเพื่อแยกกันไป reduce แล้วค่อยนำผลลัพธ์ย่อยๆเหล่านั้นมารวมกันอีกทีหนึ่ง ซึ่งเป็นสิ่งที่เกิดขึ้นกับ Hadoop MapReduce และ RDD ใน Apache Spark นั่นเอง

Zip

zip คือการนำสอง collection มาสร้าง collection ใหม่ จริงๆแล้วก็เหมือนเรารูดซิปเลยครับ ผลลัพธ์จะออกมาเป็น pair ของสมาชิกแต่ละตัวของทั้งสอง collection เรียงตามลำดับ ตัวอย่างเช่น

ลองมาดูตัวอย่างที่ดูมีประโยชน์ขึ้นอีกนิด เราจะสร้าง function ในการหา dot product ของ 2 vector ที่อยู่ในมิติใดๆ ก็สามารถใช้ zip มาช่วยได้ครับ

อธิบายนิดนึงว่า _1 กับ _2 นี่คือตัวแรกกับตัวที่สองใน pair ครับ อย่างเช่น p =(3, 5) ก็ p._1 เป็น 3 และ p._2 เป็น 5

ส่งท้าย

แน่นอนว่าทุกอย่างมีข้อดีก็ต้องมีข้อเสียครับ อย่างแรกเลยคือ performance มันสู้ loop ไม่ได้ในหลายๆกรณี แต่ code เราก็จะสะอาดมากขึ้น และสะดวกต่อการ parallelize ซึ่งเดี๋ยวจะมาเล่าให้ฟังต่อไปครับ

ถ้ามีข้อสงสัย หรือติชม ก็สามารถพูดคุยกันได้ที่นี่ หรือบน facebook ก็ได้ครับ ถ้าชอบก็อย่าลืมกด Follow บน medium หรือ “ติดตามกันบน facebook” ได้ครับผม แล้วเจอกัน~