สร้าง reduce function ด้วย recursive function
Tags: haskell, functional
Published: 2020-01-04 13:31:26


## sum function

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

```haskell
list = [1, 2, 3, 4, 5]
```

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

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

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

```go
result := 0
for _, v := range list {
    result += v
}
return result
```

ถ้าเป็นภาษาแบบ [Functional Programming Language](https://en.wikipedia.org/wiki/Functional_programming) อย่าง [Haskell](https://www.haskell.org) เราสามารถสร้างฟังก์ชันเพื่อรวมเลขพวกนี้เขาด้วยกันได้โดยใช้การสร้าง Recursive Function ซึ่งเราอาศัยการเรียกตัวเองซ้ำของฟังก์ชันแทนการใช้กลไกการวนซ้ำแบบทั่วไปได้ ตัวอย่างเช่นกรณีนี้ผมสามารถสร้างฟังก์ชันชื่อ sum ได้ออกมาเป็นแบบนี้

```haskell
sum [] = 0
sum (x:xs) = x + sum xs
```

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

```haskell
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 ที่เก็บผลลัพธ์ก่อนหน้าที่จะบวกตัวถัดไป สามารถเขียนออกมาได้แบบนี้

```haskell
sum acc [] = acc
sum acc (x:xs) = sum (acc+x) xs
```

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

```haskell
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 จะได้ออกมาแบบนี้

```haskell
product [] = 1
product (x:xs) = x * product xs
```

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

```haskell
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 ออกมาแบบนี้

```haskell
product acc [] = acc
product acc (x:xs) = product (acc*x) xs
```

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

```haskell
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 ซึ่งโค้ดจะหน้าตาเป็นแบบนี้

```haskell
reduce f acc [] = acc
reduce f acc (x:xs) = reduce (f acc x) xs
```

ดังนั้นเราสามารถเอา reduce ไปทำได้ทั้ง product หรือ sum ขึ้นอยู่กับเราเปลี่ยน f นั่นเองเช่น ถ้าเรียก reduce แบบนี้

```haskell
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 แบบนี้

```haskell
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