DEV Community

Weerasak Chongnguluam
Weerasak Chongnguluam

Posted on

สร้าง reduce function ด้วย recursive function

sum function

ก่อนจะไปดูว่าจะสร้าง reduce ยังไง ไปดูกันก่อนว่าถ้าเรามี List ของตัวเลขแบบนี้

list = [1, 2, 3, 4, 5]
Enter fullscreen mode Exit fullscreen mode

และเราต้องการบวกเลขที่อยู่ในลิสต์ทั้งหมดเข้าด้วยกัน

ถ้าเป็นภาษา imperative ปกติเราสามารถสร้างตัวแปรไว้เก็บผลลัพธ์แล้ววนซ้ำด้วยลูปที่เป็นกลไกที่ภาษาให้มาเพื่อดึงแต่ละค่าในลิสต์มาบวกสะสมไปในตัวแปรนั้น

ตัวอย่างเช่นถ้าเป็น Go และจะเขียนออกมาได้ประมาณนี้

result := 0
for _, v := range list {
    result += v
}
return result
Enter fullscreen mode Exit fullscreen mode

ถ้าเป็นภาษาแบบ Functional Programming Language อย่าง Haskell เราสามารถสร้างฟังก์ชันเพื่อรวมเลขพวกนี้เขาด้วยกันได้โดยใช้การสร้าง Recursive Function ซึ่งเราอาศัยการเรียกตัวเองซ้ำของฟังก์ชันแทนการใช้กลไกการวนซ้ำแบบทั่วไปได้ ตัวอย่างเช่นกรณีนี้ผมสามารถสร้างฟังก์ชันชื่อ sum ได้ออกมาเป็นแบบนี้

sum [] = 0
sum (x:xs) = x + sum xs
Enter fullscreen mode Exit fullscreen mode

เวลาเราเรียก

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))))
Enter fullscreen mode Exit fullscreen mode

สุดท้ายก็จะเอาแต่ละค่ามาบวกกันได้ 15 แต่ว่าแบบนี้จะเริ่มที่ 5 + 0 ก่อนแล้วย้อนกลับมาบวกด้วย 4 จนไปหา 1

แต่ถ้าเราอยากให้เริ่มที่ 0+1 ก่อนแล้วค่อย +2 เราสามารถเขียน sum ใหม่โดยสร้าง function ในรูปแบบที่รับ accumulator ซึ่งเราจะให้เป็น parameter ที่เก็บผลลัพธ์ก่อนหน้าที่จะบวกตัวถัดไป สามารถเขียนออกมาได้แบบนี้

sum acc [] = acc
sum acc (x:xs) = sum (acc+x) xs
Enter fullscreen mode Exit fullscreen mode

เวลาเราเรียก

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)
Enter fullscreen mode Exit fullscreen mode

สุดท้ายก็จะเอาแต่ละค่ามาบวกกันได้ 15

product function

ทีนี้ถ้าเราต้องการคูณตัวเลขที่อยู่ในลิสต์เข้าด้วยกันล่ะ เราก็สามารถใช้ recursive function ได้เช่นกัน ตัวอย่างโค้ดของ product function จะได้ออกมาแบบนี้

product [] = 1
product (x:xs) = x * product xs
Enter fullscreen mode Exit fullscreen mode

เวลาเราเรียก

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))))
Enter fullscreen mode Exit fullscreen mode

สุดท้ายก็จะเอาแต่ละค่ามาคูณกันได้ 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
Enter fullscreen mode Exit fullscreen mode

เวลาเราเรียก

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)
Enter fullscreen mode Exit fullscreen mode

สุดท้ายก็จะเอาแต่ละค่ามาบวกกันได้ 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
Enter fullscreen mode Exit fullscreen mode

ดังนั้นเราสามารถเอา 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)
Enter fullscreen mode Exit fullscreen mode

สุดท้ายจะได้ 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)
Enter fullscreen mode Exit fullscreen mode

สุดท้ายจะได้ 120 เหมือน product

สรุป

จะเห็นว่า reduce นั้น เกิดมาจากที่เราเห็น pattern ร่วมกันของ recursive function ที่กระทำกับสมาชิกของ list ทีละคู่โดยต่างกันแค่ค่าเริ่มต้นกับ function ที่กระทำ จึงเกิดการแยกออกมาเป็น reduce function นั่นเอง

จริงๆแล้ว Haskell มีฟังก์ชัน reduce ให้ใช้แล้วแต่อยู่ในชื่อ foldl และ foldr ฟังก์ชัน ลองอ่านต่อได้ที่นี่ครับ https://wiki.haskell.org/Fold

Discussion (4)

Collapse
wingyplus profile image
Thanabodee Charoenpiriyakij

อย่างงี้ reduce function ต้องเป็น function ที่รับค่าสองตัวเสมอไหม?

Collapse
iporsut profile image
Weerasak Chongnguluam Author

หมายถึง f ที่โยนให้ reduce ใช่มั้ย

Collapse
wingyplus profile image
Thanabodee Charoenpiriyakij

ใช่ๆ

Thread Thread
iporsut profile image
Weerasak Chongnguluam Author

ใช่ f จะเป็น function ที่รับ 2 ค่า เนี่ย type ของ foldl ใน Haskell

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b