/ 365วันแห่งโปรแกรม

[365 วันแห่งโปรแกรม #day67] Filter Map Reduce (ตอนที่ 3)

วันที่หกสิบเจ็ดของ ‪#‎365วันแห่งโปรแกรม วันนี้ขอเสนอเรื่อง Reduce ครับ


Reduce

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

Reduce ต่างจาก Filter และ Map ตรงที่ฟังก์ชันที่ Reduce รับเป็นพารามิเตอร์จะต้องรับพารามิเตอร์ 2 ตัว ตัวหนึ่งคือ element ปัจจุบัน และอีกตัวหนึ่งคือค่า accumulator (เป็นค่าของผลลัพธ์จากการคำนวณ element ก่อนหน้า) อาจเขียนแทนได้ด้วย signature นี้

Pseudocode

Reduce(func(acc, element), list)

สมมติว่าเราจะ reduce list ของตัวเลข 1 ถึง 10 ด้วยฟังก์ชัน + ก็อาจจะเขียนได้ประมาณนี้

Pseudocode

Reduce((acc, element) => acc + element, [1..10])

การทำงานจะเป็นไปตามลำดับ ดังนี้

$$((((((((((1 + 2) + 3) + 4) + 5) + 6) + 7) + 8) + 9) + 10)$$

*โดยทั่วไปหากเราไม่มีการกำหนดค่า accumulator เริ่มต้นจะถือว่า element ตัวแรกเป็น accumulator เริ่มต้น แล้ว element ตัวที่ 2 จะเป็นตัวแรกที่มีการประมวลผลตามฟังก์ชันที่ใส่เข้าไป

ในแต่ละภาษาโปรแกรมจะมีการ implement Reduce ที่แตกต่างกันและอาจจะให้ผลลัพธ์ที่แตกต่างกัน ดังนั้นจึงมีชื่ออื่นที่ใช้แทน Reduce มากมาย ไม่ว่าจะเป็น Fold, Accumulate, Scan และอื่นๆ แต่โดยทั่วไปแล้วเรามักใช้คำว่า Fold ต่อจากนี้ไปในบทความนี้จะใช้คำว่า Fold แทน Reduce

Fold Left vs Fold Right

หากเราพิจารณาจากตัวอย่างก่อนหน้า จะพบว่าถ้าเราเปลี่ยนฟังก์ชันประมวลผลเป็นลบแทนแล้ว ผลลัพธ์ที่ได้จากการ Reduce โดยเริ่มจาก element ทางด้านซ้าย และผลลัพธ์ที่ได้จากการ Reduce โดยเริ่มจาก element ทางด้านขวานั้นจะแตกต่างกัน เนื่องจากฟังก์ชันลบไม่มีคุณสมบติของการสลับที่ นี่จึงเป็นที่มาของการแยก Fold ออกเป็น Fold Left (Foldl) และ Fold Right (Foldr)

Haskell

foldl (-) 0 [1..10] // -55

foldr (-) 0 [1..10] // -5

*หมายเหตุฟังก์ชัน Fold จะรับค่า accumulator เริ่มต้นเสมอ ในตัวอย่างนี้กำหนดให้เริ่มที่ 0

จากตัวอย่างพบว่า เมื่อใช้ Foldl จะได้คำตอบเป็น -55 ซึ่งเกิดจาก

$$(((((((((((0 - 1) - 2) - 3) - 4) - 5) - 6) - 7) - 8) - 9) - 10)$$

แต่เมื่อใช้ Foldr แล้จะได้ผลลัพธ์เป็น -5 เพราะว่าลำดับการคำณวนของ Foldr จะเป็น

$$(1 - (2 - (3 - (4 - (5 - (6 - (7 - (8 - (9 - (10 - 0))))))))))$$

Fold ฟังก์ชันที่ทรงพลังที่สุดในสามโลก

สามฟังก์ชันที่เราคุยกันมา Filter, Map และ Fold ฟังก์ชันที่ทรงพลังที่สุดก็คือ Fold เพราะอะไรน่ะหรือ? เพราะแทบทุกฟังก์ชันที่ใช้ประมวลผล collection เราสามารถเขียนให้อยู่ในรูปแบบของ Fold ได้ อ้าว แล้วไหนบอกว่า Fold จะยุบรวมเหลือค่าเดียว? ก็ค่าเดียวครับ แต่เป็น collection ได้นะ ><

จากตัวอย่างเดิมของฟังก์ชั่น Filter

กำหนดให้เซ็ต s มีข้อมูลเป็นจำนวนเต็มตั้งแต่ 1 ถึง 100 จงหาสมาชิกทั้งหมดของเซ็ต s ที่เป็นจำนวนคู่

เราสามารถเขียนโปรแกรมหาคำตอบโดยใช้ Fold ได้ดังนี้

Haskell

even' x = mod x 2 ==0
foldr (\x y -> if even x then x : y else y) [] [1..100]

จะเห็นว่าผมใส่ [] เป็น accumulator เริ่มต้น ในแต่ละรอบที่ประมวลผล element ก็จะมีการเช็คว่า element นั้นเป็นเลขคู่หรือไม่ ถ้าใช่ก็จะเก็บใส่ accumulator ถ้าไม่ใช่ก็โยน accumulator ไปต่อ

ต่อมาจากตัวอย่างในเรื่อง Map

กำหนดให้เซ็ต s มีข้อมูลเป็นจำนวนเต็มตั้งแต่ 1 ถึง 100 จงเพิ่มค่าของข้อมูลทุกตัวเป็น 2 เท่า

Haskell

foldr (\x y -> x * 2 : y) [] [1..100]

ในตัวอย่างนี้เราคูณ element แต่ละตัวด้วย 2 แล้วใส่เข้าไปใน accumulator แล้วส่งต่อไปเรื่อยๆ ครับ

Fold implementation in Imperative Language

การ implement Fold ขึ้นมานั้นอาจจะยากกว่า Filter และ Map เล็กน้อย เนื่องจาก Fold นั้นซับซ้อนกว่า และทรงพลังกว่า อย่างไรก็ตามไม่มีอะไรที่ยากเกินไปครับ

กำหนดให้เซ็ต s มีข้อมูลเป็นจำนวนเต็มตั้งแต่ 1 ถึง 10 จงหาผลคูณของสมาชิกทั้งหมดด้วยฟังก์ชัน Fold (Factorial ของ 10)

สร้าง Strategy Interface ก่อน

C#

public interface IFoldStrategy<I,O>
{
    O Fold(I item, O accumulator);
}

เหมือน Interface ของ Map Strategy เลย แต่มีการเพิ่มพารามิเตอร์ accumulator เข้าไป

ต่อไปสร้าง Concrete Strategy

C#

public class MultiplyFoldStrategy : IFoldStrategy<int, int>
{
    public int Fold(int item, int accumulator)
    {
        return item * accumulator;
    }
}

แล้วก็สร้างฟังก์ชัน Fold ครับ

C#

public O Fold<I, O>(IFoldStrategy<I, O> strategy, O accumulator, IEnumerable<I> list)
{
    foreach (var item in list)
    {
        accumulator = strategy.Fold(item, accumulator);
    }

    return accumulator;
}

รัน!!

C#

var s = Enumerable.Range(1, 10).ToList();
var result = Fold(new MultiplyFoldStrategy(), 1, s);
Console.WriteLine(result);

===output===

3628800

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

เช่นเคยครับ เรามาดูใน Linq กับ Java 8 กันดีกว่า

C# + Linq

var s = Enumerable.Range(1, 10).ToList();
var result = s.Aggregate((item, acc) => item * acc);
Console.WriteLine(result);

===output===

3628800

ใน Linq มีคำสั่ง Aggregate ให้ใช้ครับ ตรงนี้จะอยู่แยกจากคำสั่ง select ปกติ ก็ถือว่าใช้งานได้ง่ายครับ

Java 8

List<Integer> s = IntStream.range(1, 10).boxed().collect(Collectors.toList());
Integer result = s.stream().reduce(1,(item, acc) -> item * acc);
System.out.println(result);

===output===

3628800

ก็สะดวกไม่แพ้กันครับ

วันนี้ผมก็ขอจบภาคทฤษฎีของ Filter Map Reduce ไว้เพียงเท่านี้ครับ วันหลังจากมีโอกาสผมจะมาแนะนำเกี่ยวกับการนำไปใช้จริง

#‎day67 #365วันแห่งโปรแกรม ‪#‎โครงการ365วันแห่ง‬...