sum function
ก่อนจะไปดูว่าจะสร้าง reduce ยังไง ไปดูกันก่อนว่าถ้าเรามี List ของตัวเลขแบบนี้
list = [1, 2, 3, 4, 5]
และเราต้องการบวกเลขที่อยู่ในลิสต์ทั้งหมดเข้าด้วยกัน
ถ้าเป็นภาษา imperative ปกติเราสามารถสร้างตัวแปรไว้เก็บผลลัพธ์แล้ววนซ้ำด้วยลูปที่เป็นกลไกที่ภาษาให้มาเพื่อดึงแต่ละค่าในลิสต์มาบวกสะสมไปในตัวแปรนั้น
ตัวอย่างเช่นถ้าเป็น Go และจะเขียนออกมาได้ประมาณนี้
result := 0
for _, v := range list {
result += v
}
return result
ถ้าเป็นภาษาแบบ Functional Programming Language อย่าง Haskell เราสามารถสร้างฟังก์ชันเพื่อรวมเลขพวกนี้เขาด้วยกันได้โดยใช้การสร้าง Recursive Function ซึ่งเราอาศัยการเรียกตัวเองซ้ำของฟังก์ชันแทนการใช้กลไกการวนซ้ำแบบทั่วไปได้ ตัวอย่างเช่นกรณีนี้ผมสามารถสร้างฟังก์ชันชื่อ sum ได้ออกมาเป็นแบบนี้
sum [] = 0
sum (x:xs) = x + sum xs
เวลาเราเรียก
sum [1, 2, 3, 4, 5]
-- จะทำให้แต่ละรอบที่เรียกซ้ำกระจาย element ออกเป็น
-- รอบที่1 => 1 + sum [2, 3, 4, 5]
-- รอบที่2 => 1 + (2 + sum [3, 4, 5])
-- รอบที่3 => 1 + (2 + (3 + sum [4, 5]))
-- รอบที่4 => 1 + (2 + (3 + (4 + sum [5])))
-- รอบที่5 => 1 + (2 + (3 + (4 + (5 + sum []))))
-- รอบที่6 => 1 + (2 + (3 + (4 + (5 + 0))))
สุดท้ายก็จะเอาแต่ละค่ามาบวกกันได้ 15 แต่ว่าแบบนี้จะเริ่มที่ 5 + 0 ก่อนแล้วย้อนกลับมาบวกด้วย 4 จนไปหา 1
แต่ถ้าเราอยากให้เริ่มที่ 0+1 ก่อนแล้วค่อย +2 เราสามารถเขียน sum ใหม่โดยสร้าง function ในรูปแบบที่รับ accumulator ซึ่งเราจะให้เป็น parameter ที่เก็บผลลัพธ์ก่อนหน้าที่จะบวกตัวถัดไป สามารถเขียนออกมาได้แบบนี้
sum acc [] = acc
sum acc (x:xs) = sum (acc+x) xs
เวลาเราเรียก
sum 0 [1, 2, 3, 4, 5]
-- จะทำให้แต่ละรอบที่เรียกซ้ำกระจาย element ออกเป็น
-- รอบที่1 => sum (0 + 1) [2, 3, 4, 5]
-- รอบที่2 => sum ((0 + 1) + 2) [3, 4, 5]
-- รอบที่3 => sum (((0 + 1) + 2) + 3) [4, 5]
-- รอบที่4 => sum ((((0 + 1) + 2) + 3) + 4) [5]
-- รอบที่5 => sum (((((0 + 1) + 2) + 3) + 4) + 5) []
-- รอบที่6 => (((((0 + 1) + 2) + 3) + 4) + 5)
สุดท้ายก็จะเอาแต่ละค่ามาบวกกันได้ 15
product function
ทีนี้ถ้าเราต้องการคูณตัวเลขที่อยู่ในลิสต์เข้าด้วยกันล่ะ เราก็สามารถใช้ recursive function ได้เช่นกัน ตัวอย่างโค้ดของ product function จะได้ออกมาแบบนี้
product [] = 1
product (x:xs) = x * product xs
เวลาเราเรียก
product [1, 2, 3, 4, 5]
-- จะทำให้แต่ละรอบที่เรียกซ้ำกระจาย element ออกเป็น
-- รอบที่1 => 1 * product [2, 3, 4, 5]
-- รอบที่2 => 1 * (2 * product [3, 4, 5])
-- รอบที่3 => 1 * (2 * (3 * product [4, 5]))
-- รอบที่4 => 1 * (2 * (3 * (4 * product [5])))
-- รอบที่5 => 1 * (2 * (3 * (4 * (5 * product []))))
-- รอบที่6 => 1 * (2 * (3 * (4 * (5 * 1))))
สุดท้ายก็จะเอาแต่ละค่ามาคูณกันได้ 120 แต่ว่าแบบนี้จะเริ่มที่ 5 * 1 ก่อนแล้วย้อนกลับมาคูณด้วย 4 จนไปหา 1
เหมือนกับกรณี sum เช่นกัน ถ้าเราอยากให้เริ่มที่ 1 * 1 แล้วเป็น (1 * 1) * 2 เราสามารถใช้ accumulator ช่วยได้ซึ่งก็จะได้ product function ออกมาแบบนี้
product acc [] = acc
product acc (x:xs) = product (acc*x) xs
เวลาเราเรียก
product 1 [1, 2, 3, 4, 5]
-- จะทำให้แต่ละรอบที่เรียกซ้ำกระจาย element ออกเป็น
-- รอบที่1 => product (1 * 1) [2, 3, 4, 5]
-- รอบที่2 => product ((1 * 1) * 2) [3, 4, 5]
-- รอบที่3 => product (((1 * 1) * 2) * 3) [4, 5]
-- รอบที่4 => product ((((1 * 1) * 2) * 3) * 4) [5]
-- รอบที่5 => product (((((1 * 1) * 2) * 3) * 4) * 5) []
-- รอบที่6 => (((((1 * 1) * 2) * 3) * 4) * 5)
สุดท้ายก็จะเอาแต่ละค่ามาบวกกันได้ 120
reduce function
ถ้าเราย้อนกลับไปดู function sum และ product อีกครั้งเราจะเห็นว่า pattern แทบจะเหมือนกันเลย ต่างกันแค่ ฟังก์ชันที่เราใช้ตอน sum คือ (+) ตอน product คือ (*)
เพราะฉะนั้น ถ้าเรา refactor ตรงส่วนที่เป็น (+) หรือ (*) ออกมาเป็น parameter ให้ชื่อว่า f แล้วตั้งชื่อ function ว่า reduce ซึ่งโค้ดจะหน้าตาเป็นแบบนี้
reduce f acc [] = acc
reduce f acc (x:xs) = reduce (f acc x) xs
ดังนั้นเราสามารถเอา reduce ไปทำได้ทั้ง product หรือ sum ขึ้นอยู่กับเราเปลี่ยน f นั่นเองเช่น ถ้าเรียก reduce แบบนี้
reduce (+) 0 [1, 2, 3, 4, 5]
-- จะทำให้แต่ละรอบที่เรียกซ้ำกระจาย element ออกเป็น
-- รอบที่1 => reduce (+) (0 + 1) [2, 3, 4, 5]
-- รอบที่2 => reduce (+) ((0 + 1) + 2) [3, 4, 5]
-- รอบที่3 => reduce (+) (((0 + 1) + 2) + 3) [4, 5]
-- รอบที่4 => reduce (+) ((((0 + 1) + 2) + 3) + 4) [5]
-- รอบที่5 => reduce (+) (((((0 + 1) + 2) + 3) + 4) + 5) []
-- รอบที่6 => (((((0 + 1) + 2) + 3) + 4) + 5)
สุดท้ายจะได้ 15 เหมือน sum
ถ้าเรียก reduce แบบนี้
reduce (*) 1 [1, 2, 3, 4, 5]
-- จะทำให้แต่ละรอบที่เรียกซ้ำกระจาย element ออกเป็น
-- รอบที่1 => reduce (*) (1 * 1) [2, 3, 4, 5]
-- รอบที่2 => reduce (*) ((1 * 1) * 2) [3, 4, 5]
-- รอบที่3 => reduce (*) (((1 * 1) * 2) * 3) [4, 5]
-- รอบที่4 => reduce (*) ((((1 * 1) * 2) * 3) * 4) [5]
-- รอบที่5 => reduce (*) (((((1 * 1) * 2) * 3) * 4) * 5) []
-- รอบที่6 => (((((1 * 1) * 2) * 3) * 4) * 5)
สุดท้ายจะได้ 120 เหมือน product
สรุป
จะเห็นว่า reduce นั้น เกิดมาจากที่เราเห็น pattern ร่วมกันของ recursive function ที่กระทำกับสมาชิกของ list ทีละคู่โดยต่างกันแค่ค่าเริ่มต้นกับ function ที่กระทำ จึงเกิดการแยกออกมาเป็น reduce function นั่นเอง
จริงๆแล้ว Haskell มีฟังก์ชัน reduce ให้ใช้แล้วแต่อยู่ในชื่อ foldl และ foldr ฟังก์ชัน ลองอ่านต่อได้ที่นี่ครับ https://wiki.haskell.org/Fold
Top comments (4)
อย่างงี้ reduce function ต้องเป็น function ที่รับค่าสองตัวเสมอไหม?
หมายถึง f ที่โยนให้ reduce ใช่มั้ย
ใช่ๆ
ใช่ f จะเป็น function ที่รับ 2 ค่า เนี่ย type ของ foldl ใน Haskell