Showing posts with label Functional. Show all posts
Showing posts with label Functional. Show all posts

Mar 31, 2014

PHP Closure: เริ่มต้นชีวิตใหม่ปิดกั้นตัวเองยอมลืมทุกสิ่งอย่าง

ภาษาทั่วไปเช่น Python เราสามารถทำ closure เช่นนี้ได้
read_only = 42

def f(x):
    return read_only + x

print(f(10)) # 52
หรือกระทั่ง
ls = [4, 8, 15, 16, 23, 42]

def g(x):
    ls.append(x)

g(99)
print(ls) # [4, 8, 15, 16, 23, 42, 99]
ความประหลาดและน่ารำคาญใน PHP คือเราไม่สามารถเขียนแค่นี้เพื่อทำ closure ง่ายๆ ตามข้างบนได้ เพราะเมื่อเราสร้างฟังก์ชันขึ้นมาแล้ว ฟังก์ชันนั้นจะไม่รู้จักตัวแปรใดๆ เลย (ยกเว้นพวก superglobals อย่าง $_GET) เราต้องเพิ่ม keyword global เข้าไปอีก เช่น
$ls = array(4, 8, 15, 16, 23, 42);

function g($x) {
    global $ls;
    $ls[] = $x;
}
ซึ่งท่านี้ก็ยังมีปัญหาอีกว่าถ้าตัวแปรที่ต้องการไม่อยู่ใน global scope (เช่นไปอยู่ใน local scope ของฟังก์ชันที่สร้างฟังก์ชันนี้อีกที) PHP ก็จะหาตัวแปรนั้นไม่เจอ

ทางแก้ที่ดูแล้วเป็น functional มากที่สุด คือใช้ keyword use เช่นนี้
$ls = array(4, 8, 15, 16, 23, 42);

$g = function($x) use($ls) {
    $ls[] = $x;
    return $ls;
};
แน่นอนว่าเมื่อทำแบบ functional แล้ว ตัวแปร $ls เก่าจะไม่เปลี่ยนค่า เพราะเมื่อมันถูกเรียกผ่าน use นั่นหมายถึงการคัดลอกค่าตัวแปรมาทั้งหมด แล้วตั้งชื่อตัวแปรให้เหมือนกันใน scope ต่างกัน แต่ถ้าอยากให้ตัวแปรเดิมเปลี่ยนค่าก็ยังสามารถใช้เทคนิคเดิมได้คือ
function($x) use(&$ls) { ... }
อย่างไรก็ตาม ท่านี้ยังมีปัญหาตรงที่การประกาศฟังก์ชันต้องทำแบบ anonymous (แล้วค่อยเอาตัวแปรไปรับ) แถมถ้าเราจะอ้างค่าใน scope อื่นเป็นจำนวนมาก ที่หัวฟังก์ชันจะเขียนได้รุงรังอย่าบอกใคร



ข้อดีเดียวที่นึกออกจากการบังคับใช้ global หรือ use สำหรับเรียกตัวแปรนอก scope คือ PHP อนุญาตให้ไม่ต้อง init ตัวแปรก็ได้ (ถ้าไม่มีการ init มาก่อน มันจะถือว่าเป็นค่าว่างตามการใช้งานนั้นๆ) ทำให้เราสามารถเขียนอะไรเช่นนี้ได้
function query_to_array() {
    $res = mysql_query('SELECT * FROM blah_blah_blah');
    foreach ($res as $row) {
        $ls[] = $row['foo_blah'];
    }
    return $ls;
}
เราอาจมองว่าท่านี้สวยตรงที่ไม่ต้อง init ตัวแปร $ls ที่รู้ๆ กันอยู่แล้วว่าต้องเป็น array ว่างแน่ๆ แต่ถ้าเกิดว่า query ข้างบนให้ผลลัพท์เป็นเซ็ตว่าง ตอน return เอาไปใช้ต่อจะเกิด bug เพราะ PHP ไม่สามารถบอก type ของ $ls ได้ สุดท้ายก็ต้องกลับไปประกาศตัวแปรไว้ที่จุดเริ่มต้นฟังก์ชันอยู่ดี หรือไม่งั้นก็เปลี่ยน return เป็น
return $ls ?: array();



ส่วนข้อเสียของการไม่ยอมให้อ้างตัวแปรนอก scope ได้นั้น นอกจากความหงุดหงิดแล้ว ก็มาจากวิวัฒนาการของภาษาสมัยนี้ที่พยายามทำให้เป็น OOP มากขึ้น ทุกวันนี้มันคงไม่แปลกที่จะเขียน
$db = new PDO('mysql: ...');
$res = $db->prepare('SELECT * FROM blah_blah_blah WHERE answer = ?');
$res->execute(array(42));
ในความจริงแล้ว ขั้นตอน prepare/execute มักถูกเขียนในส่วนอื่นๆ ไม่เอาไว้ติดกันเช่นนี้ ยิ่งไปกว่านั้นมันมักโดน refactor ไว้ในฟังก์ชันเพื่อจัดระเบียบให้อ่านง่ายด้วย ในเมื่อตัวแปร $db ที่ควรเป็น global ดันไม่สามารถเรียกใช้ได้ง่ายๆ ใครมันจะอยากเขียนแบบ OOP กันหละ?

ทางออกโดยทั่วไปก็คือสร้าง model ที่เป็น interface สำหรับ query ทั้งหมดให้ทำผ่านตัวมัน แล้วตอนสร้าง model ก็ bind ตัวแปร $db เข้าไป ก็คือเราสามารถเข้าถึง database ได้โดย $this->db ซึ่งท่านี้ก็ยังรุงรังเหมือนเดิม แถมตอนเรียกใช้ก็ยังต้องพิมพ์ยาวขึ้นอีกด้วย

ท่าที่ผมชอบมากกว่าเป็นของ Laravel ที่สร้าง class เชื่อมต่อ database นั้นๆ ไว้ให้เลย ทำให้เวลาจะทำ query ก็เพียงแค่
$res = DB::select('SELECT * FROM blah_blah_blah WHERE answer = ?', array(42));
เพราะว่า class และฟังก์ชันใน PHP สามารถเรียกใช้จาก scope ไหนๆ ก็ได้ครับ



ข้อดีนิดเดียว (แถมยังไม่แน่ว่ามันเป็นข้อดีจริงๆ หรือเปล่า) แต่ข้อเสียบานเลย รู้งี้แล้วยังเขียน PHP กันอยู่อีกรึ :P

Jan 2, 2013

ทำ Optional Argument แบบ LaTeX

command ใน LaTeX นั้นมีวิธีเรียกใช้ที่ต่างจากภาษาโดยทั่วไปอยู่บ้าง ลองดู
\sqrt{x}
\sqrt[3]{x}
อันด้านบนจะวาด √x (รากที่สองของ x -- โดยปรกติ รากที่สองไม่จำเป็นต้องมีเลข 2 กำกับ) ส่วนอันล่างจะวาด ∛x

รูปร่างของ syntax ที่น่าสนใจคือ ส่วนที่เป็น optional argument จะถูกเรียกขึ้นมาก่อน main argument แถมยังใช้วงเล็บแยกกันอีก นี่ทำให้การ currying เป็นไปได้อย่างง่ายดาย
\newcommand{\cbrt}{\sqrt[3]}
...
\cbrt{x}
จริงๆ แล้วทาง math ก็มีฟังก์ชันในแนวคิดนี้อยู่เยอะ อย่างเช่น σx(n) ซึ่งเขียนแบบนี้แล้วเข้าใจง่ายกว่า σ(n, x) และยังไม่สับสนอีกว่า argument ตัวไหนที่ควรเป็น n หรือ x กันแน่

แล้วถ้าอยากได้แบบนี้ใน Python บ้าง? ง่ายนิดเดียวเพราะใช้เทคนิคเดียวกับ Infinite List นั่นเอง
@singleton
class sigma:
    def __call__(self, n, x=1):
        if n == 1:
            return 1
        return product( sum((k**x)**i for i in range(v+1))
                            for k, v in Counter(factor(n)).items() )
    def __getitem__(self, x):
        def partial_sigma(n):
            return self(n, x)
        return partial_sigma
คราวนี้จะเขียน
6 == sigma[1](6) - 6
หรือกระทั่ง
tau = sigma[0]
...
[tau(i) for i in range(return 1, 10)]
ก็ย่อมได้

Nov 30, 2012

เปลี่ยนค่าตัวแปรใน Haskell

ใน ghci ถ้าเราลองทำอย่างนี้
let x = 10
let x = x + 1
กด Enter แล้วจะพบ prompt รอทำงานต่อ ถึงตอนนี้อาจคิดว่าไม่มีปัญหาหนิ แต่อย่าลืมว่า Haskell เป็น lazy language ดังนั้นต้องเรียก x ออกมาดูค่าด้วย

... แล้วเราก็จะพบกับความว่างเปล่า เฮ้ยทำไมแค่บวกเลขง่ายๆ มันถึงคิดช้าจังฟระ

นั่นเป็นเพราะว่ารูปด้านบนนี้เป็น recursive ตอนที่จะ eval ค่า x + 1 ด้านขวามือออกมา มันจะไปเรียกดู definition ของ x ซึ่งก็คือ x + 1 นั่นเอง (ลืมไปได้เลยว่าเราเคยบอกให้ x = 10)

อย่างไรก็ตาม ถ้าเราเปลี่ยนไปเขียนแบบนี้
let x = 10
let y = x + 1
let x = y
เวลาเรียก x เราจะได้คำตอบที่ถูกต้องคือ 11 แล้วครับ



แต่ถ้าทำท่าข้างบนนี้ มันก็คงบาปพอๆ กับ
word = "abracadabra"
for i in range(len(word)):
    print(word[i])
ใน Python นั่นแหละ :P



ดังนั้น Haskell จะเลี่ยงไปใช้ Monad แทน
x <- return 10
x <- return (x + 1)
ดูเผินๆ เหมือนว่าเราจะเปลี่ยนค่าตัวแปร x ได้ แต่ที่จริงแล้วสองบรรทัดข้างบนนี้จะเทียบเท่ากับ
return 10 >>= \x -> return (x + 1) >>= \x -> return x
นั่นหมายความว่า แรกสุดเราเอาค่า 10 ส่งให้ฟังก์ชั่นที่รับตัวแปร 1 ตัว โดยฟังก์ชั่นนี้อ่านชื่อตัวแปรที่รับมาว่า x แล้วจึงคำนวณ x + 1 เรียบร้อยแล้วก็ส่งต่อค่าที่คำนวณได้ไปให้ฟังก์ชั่นอีกตัว ที่รับตัวแปร 1 ตัวและอ่านชื่อตัวแปรนั้นว่า x เช่นกัน

จะเห็นว่าแท้จริงแล้วเราไม่ได้เปลี่ยนค่าของตัวแปรเลย มันเป็นเพียงการส่งต่อค่าที่คำนวณแล้วให้ฟังก์ชันอื่นไปเรื่อยๆ โดยที่ฟังก์ชั่นเหล่านั้นบังเอิญเรียกชื่อตัวแปรเหมือนกันเท่านั้นเอง

Sep 13, 2012

ทำ Recursion บนการ Integral

ฟังก์ชัน factorial นั้นมีนิยามง่ายๆ ตรงไปตรงมาคือ ผลคูณของจำนวนเต็มบวกตั้งแต่ 1 ไปจนถึง n
factorial n = product [1..n]
ซึ่งถ้าสังเกตดูซักหน่อย จะพบว่ามันสามารถเขียนนิยามเป็น recursion ได้
factorial 1 = 1
factorial n = n * factorial (n - 1)
ตอนนี้เราอาจเพิ่มนิยามที่ว่า 0! = 1 เพื่อความสะดวกในการกระจายพจน์สำหรับคำนวณความน่าจะเป็น

แต่ทั้งหมดนี้จะมีปัญหาอยู่อย่างนึง ตรงที่ทุกอย่างเป็น discrete math หมดเลย นั่นคือเราไม่สามารถหาอะไรอย่าง 0.5! ได้

ถ้าดูจากที่มาและการใช้งานของมัน (ส่วนมากเป็นเรื่องความน่าจะเป็นนั่นแหละ) ก็อาจนับว่าไม่มีปัญหา แต่สำหรับ pure math แล้ว มันก็น่าจะมีอะไรซักอย่างมาตอบคำถามตรงนี้ได้นะ



โชคดี (?) ที่เรามีเลขมหัศจรรย์อย่าง e ซึ่งมีสมบัติประหลาดอย่าง
e^x = d/dx e^x
ดูๆ ไปแล้ว มันก็คล้ายกับ fixed-point combinator ที่เคยพูดไว้ในตอนก่อนๆ เพียงแต่เปลี่ยนจาก function call เป็นการ diff-integral แทน โดยมี terminate point อย่าง
integral 1/e^x dx from 0 to infinity = - 1/e^infinity + 1/e^0
                                     = 1
นี่ทำให้เราสามารถเขียน recursion ในรูปของ integral ได้ เช่น
Gamma(n) = integral 1/e^t t^(n-1) dt from 0 to infinity
ลองดูสมบัติของมันโดยทำการ integral เข้าไป จะได้ว่า
Gamma(n) = integral 1/e^t t^(n-1) dt from 0 to infinity
         = integral u dv from 0 to infinity            ; let u = 1/e^t, dv = t^(n-1) dt
         = (limit u*v for x from 0 to infinity) - integral v du from 0 to infinity
         = (1/n)(1/e^infinity infinity^n - 1/e^0 0^n) - integral v du from 0 to infinity
         = 0 - integral v du from 0 to infinity
         = (1/n) integral 1/e^t t^n dt from 0 to infinity
         = Gamma(n+1)/n
ดังนั้น จะเห็นว่า
Gamma(1) = 1
Gamma(n) = (n-1) * Gamma(n-1) = (n-1)(n-2) * Gamma(n-2) = ...
ซึ่งก็คือ
factorial(n) = Gamma(n+1)


ถึงตอนนี้ก็คงตอบคำถามได้แล้วว่า 0.5! นั้น สามารถหาค่าได้จาก
Gamma(3/2) = (1/2) * Gamma(1/2)

Gamma(1/2) = integral 1/e^t 1/sqrt(t) dt from 0 to infinity
           = 2 * integral 1/e^u^2 du from 0 to infinity      ; let du = 1/sqrt(t)
           = integral 1/e^u^2 du from -infinity to infinity
           = sqrt(pi)

Gamma(3/2) = sqrt(pi)/2
ตอนพยายามหาค่าของ Gamma(1/2) ต้องใช้ความรู้เรื่อง double integral และการแปลงระนาบเข้าช่วย ลองศึกษาเทคนิคที่นี่

ข้อดีของการเขียนในรูป integral นี่มีอีกอย่าง คือถ้ารู้สึกว่าพิสูจน์ห่าค่าตรงๆ แบบนี้มันยากไป จะเลี่ยงไปใช้ Riemann integral เพื่อประมาณค่าแทนก็ย่อมได้ครับ

Sep 3, 2012

แก้โจทย์ป้ายสมัครงาน Google แบบบรรทัดเดียว

นอนไม่หลับ บวกกับช่วงนี้แก้โจทย์เล่นเยอะไปหน่อย เหมือนสมองไม่อยากหยุดแก้โจทย์ 555

แล้วก็นึกได้ว่า ไอ้โจทย์ป้ายสมัครงานของ Google อันนี้ ยังไม่เคยแก้เล่นเองเลยนี่หว่า


แต่ถ้าจะให้แก้ตามปรกติธรรมดา ก็ดูจะไม่ท้าทายซักเท่าไหร่ไปแล้ว (เพราะเล่นไปอ่านเฉลยมาเรียบร้อย) แบบนี้เลยต้องเพิ่ม standard ให้กับตัวเองด้วยการเขียนเป็น one-liner โดยไม่พึ่งพา stdlib ซะเลย

ตัวโจทย์คงไม่ต้องแปลแล้ว? (ถ้าตีโจทย์ไม่ออกจริงๆ แนะนำบล็อก @khajochi เลย) เอาเป็นว่าเริ่มกันเลยดีกว่านะ



โดย algorithm ที่จะใช้คำนวณหาค่า e คือ
e = 1 + 1/1! + 1/2! + 1/3! + 1/4! + ...
ต้องใช้ algorithm นี้เพราะว่ามันให้ค่าทศนิยมได้แม่นยำรวดเร็วพอสมควร และยัง implement ตามไม่ยากเท่าไหร่ ในที่นี้ใช้ถึงแค่พจน์ 1/200! ก็ให้ค่าออกมาแม่นยำเกือบ 400 ตำแหน่งแล้ว

มาเริ่มที่ส่วนที่เล็กที่สุด ฟังก์ชั่น factorial ที่ดูเผินๆ ก็ไม่มีอะไรประหลาด แต่ถ้าจะเขียนแบบ one-liner ก็เลี่ยงไม่ได้ที่จะต้องเขียนเป็น recursion และต้องไม่จองชื่อ function ไว้ก่อนด้วย ซึ่งก็ทำได้โดยใช้ combinator แบบนี้
factorial = lambda n: (lambda f, x: f(f, x))(lambda r, y: y*r(r, y-1) if y > 1 else 1, n)
(รายละเอียดอ่านได้จากตอนก่อนๆ)

ต่อมาคือการจับแต่ละพจน์มาบวกกัน ซึ่งจะ implement ตรงๆ แบบนี้ไม่ได้
sum(1/factorial(i) for i in range(200))
เพราะ float มันเก็บ precision ของทศนิยมได้เล็กนิดเดียว ดังนั้นเราต้องดัดแปลงสมการต้นแบบให้กลายเป็น
e = (1 + 1/1! + 1/2! + 1/3! + 1/4! + ...)(1!2!3!4!.../1!2!3!4!...)
เทคนิคหนึ่งที่ใช้ได้เสมอๆ เมื่อต้องการทศนิยม n ตำแหน่ง คือคูณด้วย 10 ยกกำลัง n เข้าไปนั่นเอง ดังนั้น
e*10**n = 10**n * (1 + 1/1! + 1/2! + 1/3! + 1/4! + ...)(1!2!3!4!.../1!2!3!4!...)
        = 10**n * (1 + 2!3!4!... + 1!3!4!... + 1!2!4!... + 1!2!3!... + ...)/1!2!3!4!...
จะเห็นว่าถ้าเรียงลำดับ operator ดีๆ เราจะไม่สูญเสีย precision เลย

ได้แนวคิดแล้วก็เริ่ม implement กัน เริ่มโดยหา factorial ของพจน์ต่างๆ ตามปรกติ
fact_each = [factorial(i) for i in range(200)]
ทีนี้เพื่อป้องกันการคำนวณซ้ำหลายรอบ ก็เอา lambda มาห่อหุ้มมันซะ ซึ่งสิ่งที่เราต้องการต่อจากนี้คือผลคูณรวมของค่าทั้งหมด (1!2!3!4!...) โดยเรายังคงต้องใช้ list เดิมนี้อยู่ ดังนั้น
prod_and_fact_each = (lambda l: [reduce(lambda x, y: x*y, l), l])(fact_each)
ถึงตอนนี้ก็ได้เวลาเอาผลคูณรวมของ factorial ทุกตัว มาหารแต่ละตัวใน list นั้นแล้ว (เรายังต้องใช้ผลคูณรวมอีกรอบ ดังนั้นส่งต่อมันด้วย)
prod_and_div_each = (lambda a, l: [a, [a / i for i in l]])(*prod_and_fact_each)
สุดท้ายก็จับทุกตัวมาบวกกัน คูณด้วย 10 ยกกำลัง n แล้วค่อยหารด้วยค่ารวมนั้น
e = str((lambda a, l: 10**400 * sum(l) / a)(*prod_and_div_each))
เท่านี้ก็ได้เลข e ที่มีทศนิยมตามต้องการแล้วนะ <3



สำหรับส่วนที่สองจะมาดูที่จำนวนเฉพาะ เนื่องจากเลข 10 หลักค่าที่ใหญ่ที่สุดคือ n = 9999999999 การที่จะบอกว่ามันเป็นจำนวนเฉพาะหรือไม่ ก็ทดสอบด้วยการเอาไปหารจำนวนเฉพาะทุกตัวที่น้อยกว่ามันไปจนถึง sqrt(n) ซึ่งหมายความว่าเราตรวจถึงแค่จำนวนเฉพาะที่น้อยกว่า sqrt(9999999999) = 99999 ก็พอแล้ว

เริ่มด้วยฟังก์ชั่นเพิ่มจำนวนเฉพาะเข้าไป
add_prime = lambda p, t: p + [t] if all(t % q for q in p) else p
ฟังก์ชั่นนี้จะรับตัวแปร 2 ตัวคือ list ของจำนวนเฉพาะก่อนหน้า และเลขที่จะตรวจว่าเป็นจำนวนเฉพาะหรือเปล่า ส่วนค่าที่คืนมานั้น ถ้าเป็นจำนวนเฉพาะจะคืน list ที่เพิ่มจำนวนที่ตรวจเข้าไปด้วย ดังนั้นสิ่งที่เราต้องทำคือใส่ list ว่างๆ เข้าไปก่อน แล้วส่งเลขที่น้อยที่สุดคือ 2 เข้าไปตรวจ หลังจากได้ list ที่มีเลข 2 ก็ส่งเลข 3,4,5,6,...,99999 เข้าไปตรวจทีละตัว โดย list ที่เป็นผลลัพท์แต่ละครั้งที่ได้มาก็จะเก็บไว้ใช้ต่อไปเรื่อยๆ นี่ก็คือแนวคิดของ reduce นั่นเอง ซึ่งก็จะเขียนได้ว่า
p = reduce(add_prime, [[], 2] + range(3, 100000, 2))
ถึงตอนนี้ก็มีจำนวนเฉพาะทั้งหมดที่ต้องการสำหรับงานนี้แล้ว :3



สุดท้าย ได้เวลาจับทุกอย่างมารวมกัน เริ่มจากการพยายาม loop ไปยังเลข 10 ตัวในทศนิยมของ e ก่อน ซึ่งก็คือ
[e[i:10+i] for e in [e] for i in range(len(e)-9)]
แต่เนื่องจากเราต้องการ filter ตัวที่ไม่ใช่จำนวนเฉพาะออกไป ซึ่งคราวนี้เราจะเปลี่ยนมาทดสอบด้วยฟังก์ชั่น
test_prime = lambda p, e: all(int(e) % q for q in p)
ดังนั้นก็จะได้
[e[i:10+i] for e, p in [[e, p]] for i in range(len(e)-9) if test_prime(p, e[i:10+i])]
แน่นอนว่างานนี้เราต้องการแค่จำนวนเฉพาะตัวแรกที่เจอ ดังนั้นสามารถเปลี่ยนไปเขียน
next(e[i:10+i] for e, p in [[e, p]] for i in range(len(e)-9) if test_prime(p, e[i:10+i]))
ก็จะได้คำตอบแล้วหละ \(^0^)/



สำหรับ code ฉบับเต็มๆ ที่เป็น one-liner (แต่ขึ้นบรรทัดใหม่เพื่อให้อ่านสะดวก) คือ
next(e[i:10+i] for e, p in [[
        str((lambda a, l: 10**400 * sum(l) / a)(*
            (lambda a, l: [a, [a / i for i in l]])(*
                (lambda l: [reduce(lambda x, y: x*y, l), l])(
                    [(lambda f, x: f(f, x))(
                           lambda r, y: y * r(r, y-1) if y > 1 else 1, i)
                        for i in range(200)])))),
        reduce(
            lambda ps, t: ps + [t] if all(t % p for p in ps) else ps,
            [[], 2] + range(3, 100000, 2))]]
    for i in range(len(e)-9)
        if all(int(e[i:10+i]) % q for q in p))
happy coding นะครับ ^^

Aug 22, 2012

อะไรคือ Y Combinator

ถึงตอนนี้เราคงทำ recursion บน lambda เป็นกันแล้ว (ถ้ายังไม่เป็น แนะนำให้อ่านตอนก่อน)

กลับไปดูอีกรอบ จะเห็นว่าตอนเรียก recursion ต้องใส่ชื่อฟังก์ชันตัวเองลงไปเป็นตัวแปรหนึ่งเสมอ
lambda f, x: 1 if x == 0 else x * f(f, x-1)
แล้วถ้าเราไม่อยากทำอย่างนี้หละ อยากจะเรียกแค่ f(x-1) เหมือนการเรียกใช้งานฟังก์ชันตามปรกติทั่วไป จะทำได้มั้ย?

ถอยหนึ่งก้าว กลับไปเขียน factorial แบบธรรมดาๆ ก่อน
f = lambda x: 1 if x == 0 else x * f(x-1)
ฟังก์ชันนี้ยังคงสามารถเรียกใช้ได้ เนื่องจากว่าเราจองชื่อ f ไว้ให้มันแล้ว (ซึ่งไม่ใช่สิ่งที่เราต้องการ) นั่นหมายความว่าชื่อ f ต้องมีปรากฏอยู่ใน scope นี้จึงจะทำ recursion ได้ และมันมีอีกวิธีนึงที่จะทำให้ f ปรากฏอยู่ภายใน scope นี้โดยไม่ต้องจองชื่อหรือส่งผ่านเป็นตัวแปรใน scope เดียวกัน คือ
lambda f: lambda x: 1 if x == 0 else x * f(x-1)
แต่การประกาศเช่นนี้จะทำให้เราไม่สามารถใช้ฟังก์ชันได้ทันที เพราะเราต้องเอาฟังก์ชั่นนี้ส่งไปเป็นตัวแปรให้ตัวมันเองเรื่อยๆ เช่น ถ้าต้องการหา 5 factorial ต้องเขียนออกมาอย่างนี้
(lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
  (lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
    (lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
      (lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
        (lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
          (lambda f: lambda x: 1 if x == 0 else x * f(x-1))(
            (lambda whatever: 42)
          )
        )
      )
    )
  )
)(5)
นั่นหมายความว่าเราต้องการอะไรซักอย่าง ที่จะทำหน้าที่ generate ฟังก์ชันของเรานี้ออกมาเรื่อยๆ ไม่ว่าจะมีอะไรเกิดขึ้นก็ตาม นี่คือแนวคิดของ fixed-point combinator โดยมีตัวหนึ่งที่เป็นมีชื่อเสียงเป็นที่รู้จักกันมากคือ Y combinator ซึ่งเขียนได้ดังนี้
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
(นิยามเต็มๆ คือ Y = λf.(λx.f (x x)) (λx.f (x x)) ซึ่งไม่จำเป็นต้องติดตัวแปร v มาด้วย)

ลองมาสำรวจการทำงานของมันดีกว่า จะเห็นได้ว่า
Y(g)(n)
-> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(g)(n)
   # reduce: g -> f
-> (lambda x: g(lambda v: x(x)(v)))(lambda x: g(lambda v: x(x)(v)))(n)
   # reduce: (lambda x: g(lambda v: x(x)(v))) -> x
-> g(lambda v: (lambda x: g(lambda v: x(x)(v)))(lambda x: g(lambda v: x(x)(v)))(v))(n)
   # reduce: n -> v
-> g((lambda x: g(lambda v: x(x)(v)))(lambda x: g(lambda v: x(x)(v)))(n))
   # for inner g function, expand back to lambda: f <- g
-> g(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))(g)(n))
   # by definition
-> g(Y(g)(n))
   # thus
-> g(g(Y(g)(n)))
-> g(g(g(Y(g)(n))))
-> g(g(g(g(...))))
วิธีเอามาใช้งานก็ไม่ยุ่งยาก เพียง
(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(  # Y-comb
  lambda f:                                  # recursive function name
    lambda x: 1 if x == 0 else x * f(x-1)    # recursive function definition
  )(5)                                       # recursive function argument
ลองเปลี่ยนมาหา fibonacci บ้าง ก็ง่ายนิดเดียว
(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(
  lambda f:
    lambda x: x if x <= 1 else f(x-1) + f(x-2)
  )(5)
ง่ายจริงป่ะ?

Aug 21, 2012

Recursive Lambda ความงามบนความงาม...

พอถล่ำลึกลงไปใน functional programming ซักพักหนึ่ง จะเริ่มเกิดคำถามขึ้นมาว่า
"แล้วเราจะทำ recursion บน lambda ได้หรือเปล่า?"
ฟังดูเผินๆ ไม่น่าเป็นไปได้ เพราะ lambda ทำให้ฟังก์ชันไม่มีชื่อ แต่การ recursion ต้องอาศัยชื่อของฟังก์ชันนั้นๆ เพื่อเรียกมันขึ้นมาทำงานเสมอ สมมติเช่นฟังก์ชันง่ายๆ ที่จะทำการยกกำลังสองเลขที่ได้รับมาทันที
(lambda x: x**2)(5)
นี่คือฟอร์มที่เรียบง่ายสุด และถ้าเราทดลองเพิ่มตัวแปรเข้าไปให้ฟังก์ชันนี้ (โดยไม่จำเป็นต้องใช้มัน) อาจจะเขียนฟังก์ชันนี้ออกมาได้ว่า
(lambda w, x: x**2)(999, 5)
แน่นอนว่ากรณีนี้เราไม่สนใจเลข 999 ที่ถูกนำไปเก็บไว้ยังตัวแปร w เลย ...แล้วเราก็คงจะถึงทางตัน ถ้าไม่สังเกตว่าตัวแปร w นั้นหนะ รับค่าอะไรเข้ามาก็ได้ (เพราะไม่ได้ใช้) นี่รวมไปถึงเราอาจจะยัด lambda เข้าไปให้มันก็ได้
(lambda w, x: x**2)(lambda u: 42, 5)
นั่นหมายความว่า lambda ไม่จำเป็นต้องไร้ชื่อเสียทีเดียว แน่หละมันอาจจะไร้ชื่อใน scope หนึ่งๆ แต่กับ scope ที่ใหญ่ขึ้นกว่าตัวมันแล้ว เราสามารถตั้งชื่อให้มันได้ ถึงตอนนี้จะเปลี่ยนชื่อตัวแปรกันซักหน่อย พร้อมกับเอาฟังก์ชันสำหรับคำนวณจากด้านบนมาใส่แทน lambda u: 42 ไปซะ
(lambda g, y: y**2)(lambda x: x**2, 5)
จะเห็นว่าเลข 5 จะถูกเก็บไว้ในตัวแปร y และคำนวณ y**2 ตรงๆ โดยที่ lambda x: x**2 ไม่ได้แสดงบทบาทอะไร แต่เนื่องจากฟังก์ชัน lambda x: x**2 ถูก scope ด้านหน้าแปะป้ายชื่อให้ว่า g เป็นที่เรียบร้อยแล้ว ดังนั้น เราสามารถส่งผ่านเลข 5 ให้ไปทำงานกับ lambda x: x**2 ได้ดังนี้
(lambda g, y: g(y))(lambda x: x**2, 5)
แม้ว่าตอนนี้เราจะสามารถเรียกชื่อของ lambda x: x**2 ใน scope ที่ใหญ่กว่าตัวมันได้ แต่มันก็ไม่มีประโยชน์เลยเพราะการจะทำ recursion นั้นต้องสามารถเรียกชื่อตัวมันเองใน scope ที่มันอยู่ได้ ดังนั้น เราจะใช้ท่าเดิมคือส่งผ่านเจ้า lambda x: x**2 นี้ต่อไปเรื่อยๆ ไม่ให้มันหายไป โดย
(lambda g, y: g(g, y))(lambda f, x: x**2, 5)
เท่านี้ ใน scope ของ lambda f, x: x**2 ก็สามารถเรียกตัวเองได้แล้ว (ชื่อว่า f) ถึงตอนนี้ก็ได้เวลาเขียน recursion ให้มัน อาจเริ่มจากฟังก์ชันง่ายๆ อย่าง factorial ก็ได้
(lambda g, y: g(g, y))(lambda f, x: 1 if x == 0 else x * f(f, x-1), 5)
สังเกตว่าการเรียก recursion ภายใน lambda นี้ ต้องส่งผ่านชื่อฟังก์ชันตัวเองเป็นตัวแปรพ่วงลงไปด้วยเสมอนะ

จบแล้ว แค่นี้แหละ recursion บน lambda ไม่ยากอย่างที่คิดเลยใช่มั้ยครับ ;)

Aug 18, 2012

ทำไม Functional Programming ถึงไม่ได้รับความนิยม


จากที่ @lewcpe คอมเมนท์ไว้ในตอนก่อน มานั่งคิดๆ ดูว่าทำไม functional programming ถึงไม่ได้รับความนิยมเท่าไหร่

คิดว่าสาเหตุใหญ่ๆ น่าจะเป็นเพราะปรกติแล้ว มนุษย์เราจะคิดการทำงานทาง "ซ้าย -> ขวา" คิดจากส่วนที่เล็กสุดออกไปยังระดับที่ใหญ่ขึ้นเรื่อยๆ เช่นเขียนโปรแกรมอย่างนี้

sh:
echo 'hello to the old world' | tr ' ' '\n' | sort -r | paste -sd ' '
ruby:
puts 'hello to the old world'.split.sort.reverse.join ' '
แต่ในการเขียนโปรแกรมแบบ functional programming การทำงานของจะเป็นในทิศทาง "ซ้าย <- ขวา" แทน ซึ่งขัดกับความรู้สึกของเรา

python:
print(' '.join(reversed(sorted('hello to the old world'.split()))))
haskell:
print (join " " . reverse . sort . splitOn " ") "hello to the old world"


อีกเรื่องที่ยากคงเป็นเพราะไม่มี for/while loop มีแต่ recursion ให้ใช้ อันนี้สาย imperative ทำใจลำบากพอควรเลย

ส่วนเรื่องอื่นๆ อย่าง immutable คงไม่มีปัญหาเท่าไหร่ อันที่จริงถ้าไม่สนว่าจะ optimize กันสุดๆ ไม่ว่าจะเขียนด้วยภาษาอะไรก็ควรยึดเรื่องนี้ไว้หน่อย มันทำให้ bug งี่เง่าหายไปได้หลายตัวเลยหละ :3

Aug 17, 2012

Function Composition กับ Programming


ตอนม.ปลาย คงเคยเห็นฟังก์ชั่นที่เขียนแทนด้วยสัญลักษณ์ g o f กันมาแล้ว ซึ่งมันหมายความง่ายๆ เช่นนี้
(g o f) (x) = g(f(x))
(นิยามเต็มๆ ของมันคือ ถ้า f: X -> Y และ g: Y -> Z แล้ว g o f: X -> Z ---- ที่ต้องนิยามเช่นนี้เพราะเราจะสามารถละการเขียน argument x ติดไปกับนิยามได้)

ในการเขียนโปรแกรม (โดยเฉพาะเชิง functional) เรามักต้องทำงานแบบฟังก์ชันต่อเนื่อง คือ output จาก function หนึ่ง จะถูกนำมาใช้เป็น input ให้ฟังก์ชันถัดไปเป็นลูกโซ่

เขียนอธิบายเป็นภาษาโปรแกรมได้คือ
first_input = x
first_output = f(first_input)
second_input = first_output
second_output = g(second_input)
y = second_output
หรือเพื่อไม่ให้เปลืองตัวแปร ทั้งหมดนี้สามารถย่อได้เหลือ
y = g(f(x))
คำถามคือ ถ้าเราต้องการประกาศแค่ฟังก์ชั่นที่ทำงานต่อกันไปเรื่อยๆ เช่นนี้ โดยที่ไม่ต้องการใส่ input ให้ฟังก์ชั่นโดยทันที เราจะทำอย่างไร?

ทางออกหนึ่งคือใช้ lambda เข้าช่วย
h = lambda x: g(f(x))
แล้วเวลาจะเรียกใช้ฟังก์ชั่นนี้ ก็แค่สั่ง
y = h(x)
ฟังดูง่ายดี แต่นึกดูอีกที ทำไมเราถึงต้องทำอะไรให้มันยุ่งยากด้วยการเอา lambda เข้ามาเกี่ยวด้วย?

ในภาษา imperative คงไม่มีทางเลือกอื่น แต่สำหรับภาษา functional จ๋าอย่าง Haskell เราสามารถเขียนแบบนี้ได้
let h = g . f
จะเห็นว่าง่ายดายเหมือนกับ g o f ตอนแรกเลย เวลาใช้ก็แค่
h x
หรือถ้าจะละการประกาศฟังก์ชั่น h ทิ้งไป เพื่อหาผลลัพท์ทันทีเลย ก็ทำได้โดย
(g . f) x
อ่าห์... นี่มันคณิตศาสตร์ชัดๆ!!