phpتابعی – قسمت ۲ – درک و پیاده سازی توابع map و reduce

Understanding and Implementing the famous map and reduce functions

تو بخش اول ما فرق بین توابع بی نام(anonymous functions) و lambda و closure ها رو فهمیدیم.lambda و توابع بی نام در اصل یک ایده هستند:توابع مقادیری هستند مانند اعداد صحیح و رشته ها.closure ها قادر هستند lambda ها رو ارجاع بدن به یا استفاده کنند از مقادیری که بیرون lambdaها تعریف شدند.even after those variables have fallen out of scope.

ما در مورد پروانه ها ، پرنده ها و زنبورها بحث می کنیم.

در زندگی هر کرم کوچکی لحظه ایست که تبدیل به پروانه می شود.دگرگیسی یک روند دگرگون شونده و یک تابع تغییر شکل است.کرم وارد و پروانه خارج (کرم)->(پروانه).مهم نیست که دگرگیسی چه جور اتفاق میفته ، مهم اینه که میدونیم یک تابع خاص است که باعث تغییر شکل کرم به پروانه می شود.

می تونین به توابع دیگری که به ورودی تغییر شکل میدهند و به خروجی ارسال میکنند بگین؟

توابع تغییر شکل دهنده زیادی وجود دارند.

 function square($x) { return x * x; }
 strtolower
 function filter($dirty) { /* clean up */ return $clean; }

بعضی ها مانند square یک ورودی گرفته و خروجی از همان نوع را برمیگردانند int->int .بعضی ها مانند (تابع) metamorphosis (دگرگیسی) یک نوع ورودی میگیرن و در خروجی نوع دیگه دیده می شود کرم->پروانه

تابع تغییر شکل – transformer functions

آیا انواع دیگری از توابع نیز هستند؟الان همون وقتیه که ما در مورد پرنده ها و زنبورها حرف می زنیم.تو تفکر دوم بزارین بچسبیم به پروانه ها.وقتی دو پروانه تو یک راستا میان پیش هم یک پروانه ی جدید می سازن.(بله من میدونم این یک قیاس اشتباهه) البته در مورد فکر کردن به جزئیات اینکه چگونه دو پروانه پیش هم میان خودداری و بر روی زیبایی آنچه اتفاق می افتد تمرکز می کنیم.دو پروانه برای ساختن یکی به هم می پیوندند(پروانه و پروانه)->(پروانه).این یک تابع جدیده ، تابع combiner .که ۲ چیز یکسان را می گیرد و نتیجه یک چیز دیگر از همان نوع است.

حالا ما با map ، reduce و برنامه نویسی تابعی php چه کار خواهیم کرد؟
map و reduce جز توابع high-order هستند این بدین معنیست که هر کدام پارامتری دارند که تابع هست البته نه هر تابعی. هر کدام یک نوع تابع مخصوص را میگیرند. map از تابع تغییردهنده (transformer) استفاده می کنه و reduce از تابع ترکیب کننده (combiner).تغییر شکل در map لیستی از چیزهایی ، میتونیم بگیم مثل یک مشت کرم ، داخل لیستی از چیزهای دیگه ، مانند پروانه ها .reduce کاهش می دهد یک لیست از چیزها را مانند پروانه تا وقتی که فقط یکی باقی بماند.در اینجا تصویری از اینکه map و reduce چگونه کار میکنند می بینیم:
map تغییر شکل میده لیستی از چیزهارو به لیستی از چیزهای دیگه.reduce ترکیب میکنه لیستی از چیزهارو به یک چیز،حالا این چیش شبیه php؟
php دو تابع داخلی داره:array_map و array_reduce
callback معانی مختلفی در php دارد که در قسمت بعد این نوشته ها کاملا پوشش داده میشه ولی الان callback در اینجا به معنی anonymous function (توابع بی نام ) هست.
استاندارد مثال map و reduce شمارش کلمات است.بزارین در php کمی به چالش بیفتیم:یک آرایه از رشته ها را میگیریم و باید تعداد هر کلمه رو تو کل رشته ها بشماریم. ورودی و خروجی مورد نظر رو میبینیم:
<?php
$lines = array(
             'one two three four',
             'two three four',
             'three four',
             'four',
             );
// Desired Output, array of type word => count
// array ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, )
?>
بزارین ببنیم در مورد این مساله چی میدونیم:
ورودی: (رشته ای از کلمات)
خروجی: (آرایه(کلمات=>تعدادشون))
ما احتیاج داریم ورودیو از نوع خودش بگیریم و خروجیو در نوع خودش بدیم،چگونه میتونیم از تابع تغییر شکل برای رفتن نصف راه استفاده کنیم؟و چطور یک reducer ما رو به مقصدمون میرسونه؟به کرم ها و پروانه ها فکر کنید.
Our caterpillar is a plain old, space delimited, lowercase string.
تابع تغییر شکل ما یک رشته را میگیرد و بعد از دگرگیسی اونو به پروانه تبدیل می کنه،نوع خروجی:آرایه ای که کلیدهاش کلمات و مقادیرش تعدادشون هستند. (کلمات به صورت پشت سر هم)->(آرایه:کلمات=>تعدادشون).خب اینم کد تابع تغییر شکل بی نام که از یکی از توابع داخلی php به نامarray_count_values استفاده کردیم.
<?php
// Transforms (Line of Words) -> (Array: Word => Count)
$lineToWordCounts =
    function($line) {
        return array_count_values(explode(' ', $line));
    };

// Test on a single line:
var_export($lineToWordCounts('one two three four'));
// Output: array ( 'one' => 1, 'two' => 1, 'three' => 1, 'four' => 1, )

// Test with array_map:
$counts = array_map($lineToWordCounts, $lines);
var_export($counts);
// Output: array ( 0 => array ( 'one' => 1, 'two' => 1, 'three' => 1, 'four' => 1, ),
//                 ۱ => array ( 'two' => 1, 'three' => 1, 'four' => 1, ),
//                 ۲ => array ( 'three' => 1, 'four' => 1, ),
//                 ۳ => array ( 'four' => 1, ), )
?>

رشته ها به پروانه ها تبدیل میشن و ما باید اونهارو در یک آرایه ترکیب کنیم،اگر ما یک تابع combiner (ترکیب کننده) بنویسیم که دو آرایه از تعداد کلمات بگیره و اونو در یک آرایه ترکیب کنه ، میتونیم از reduce برای ترکیب آرایه ها در یک آرایه استفاده کنیم .

<?php
// Combiner (Array:Word=>Count,Array:Word=>Count)->(Array:Word=>Count)
$sumWordCounts =
    function($countsL, $countsR) {
        // Get all the words
        $words = array_merge(array_keys($countsL), array_keys($countsR));
        $out = array();
        // Put them in a new (Array: Word => Count)
        foreach($words as $word) {
            // Sum their counts
            $out[$word] = isset($countsL[$word]) ? $countsL[$word] : 0;
            $out[$word] += isset($countsR[$word]) ? $countsR[$word] : 0;
        }
        return $out;
    };
$totals = array_reduce($counts, $sumWordCounts, array());
var_export($totals);
// Output: array ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, )
?>

ما با استفاده از توابع داخلی پی اچ پی array_map و array_reduce و از lambda های تغییر شکل و ترکیب کننده یک شمارشگر چند خطی کلمات پیاده سازی کردیم. قسمت map هر خطو از رشته به آرایه ای از تعداد کلمات اون خط تغییر میده.و قسمت reduce ترکیب میکنه اون آرایه های تعداد کلماتو به [عدد |تعداد]،که تعداد نهایی در کل خطوط است.
شما برای پیاده سازی map/reduce در php آماده هستید؟
پیاده سازی map بسیار سادست و به ندرت احتیاج به توضیح دارد.تمام کاری که انجام میدیم فراخوانی تابع تغییر شکل برای هر عنصر ورودی و ذخیره هر نتیجه در آرایه ای که بازگشت داده خواهد شد.

<?php
/**
 * $transformer lambda(caterpillar) -> butterfly
 * $in array of caterpillars
 */
function map($transformer, $in) {
    $out = array();
    foreach($in as $item) {
        $out[] = $transformer($item);
    }
    return $out;
}
?>

به جزئیات توجه نکنید فقط تمرکز کنید به جایی که ما بیشتر از یک عنصر به تابع reduce میدهیم:

<?php
/**
 * $combiner lambda(butterfly, butterfly) -> butterfly
 * $in array of butterflies
 */
function reduce($combiner, $in, $identity) {
    if(count($in) <= 1) {
        $out = $identity;
    } else if(count($in) > 1) {
        $out = array_shift($in);
        do {
            $next = array_shift($in);
            $out = $combiner($out, $next);
        } while(!empty($in));
    }
    return $out;
}
$totals = reduce($sumWordCounts, map($lineToWordCounts, $lines), array());
var_export($totals);
// Output: array ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, )
?>

با reduce ما شروع به شیفت دادن اولین پروانه از لیست میکنیم و ترکیب میکنیم اونهارو با پروانه ی بعدی برای ساختن یک ابر پروانه.و بعد ترکیب می کنیم اون ابر پروانه با لیست بعدی پروانه ها.تا زمانیکه ما یک پروانه داشته باشیم.
map/reduce نگاه ۲:پیاده سازی بازگشتی،لطفا
پیاده سازی اولیه map و reduce به صورت امرانه از حلقه ها استفاده می شد،مردمی که تابعی فکر میکنند عقیده دارند حلقه ها زباله اند و چرا ما باید از حلقه ها استفاده کنیم در جایی که تابع بازگشتی داریم؟map و reduce چطور به نظر میان وقتی حلقه ها رو حذف کنیم؟
قبل از اینکه این کارو انجام بدیم ،اجازه بدین چند تابع کمکی برای مقادیر بازگشتی بسازیم:

<?php
// First element of an array
function first($in) {
    return empty($in) ? null : $in[0];
}

// Everything after the first element of an array
function rest($in) {
    $out = $in;
    if(!empty($out)) { array_shift($out); }
    return $out;
}

// Take an element and an array
//  and fuse them together so that the element
//  is at the front of the array
function construct($first, $rest) {
    array_unshift($rest, $first);
    return $rest;
}
?>

حالا این توابع به ما کمک میکنند با آرایه ها مانند لیست ها کار کنیم:

<?php
/**
 * $transformer lambda(caterpillar) -> butterfly
 * $in array of caterpillars
 */
function map($transformer, $in) {
    return !empty($in) ?    construct(  $transformer(first($in)),
                                        map($transformer,rest($in)))
                        :    array();
};

/**
 * $combiner lambda(butterfly, butterfly) -> butterfly
 * $in array of butterflies
 */
function reduce($combiner, $in, $identity) {
    return !empty($in) ?    $combiner(first($in),
                                      reduce($combiner, rest($in), $identity))
                         :  $identity;
};

$totals = reduce($sumWordCounts, map($lineToWordCounts, $lines), array());
var_export($totals);
// Output: array ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, )
?>

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *