What have you found for these years?

2007-08-07

ludy 0.0.3 released

睽違已久,忽然心血來潮多加了幾個東西。
in CHANGES:
==============================
ludy 0.0.3, 2007.08.07

1. ludy_ext:
added:
1. Proc#curry
2. Proc#compose
3. Proc#chain
4. Symbol#to_proc
5. Array#foldl
6. Array#foldr
7. Array#filter

removed:
1. Fixnum#collect # see tc_ludy_ext.rb#test_fixnum_collect for reason

info:
1. ruby2ruby has NilClass#method_missing return nil,
so i can't just make it return blackhole

2. module Curry:
see test/tc_curry.rb for usage

see unit test for usage
==============================
雖然說請看 unit test 來揣摩用法,不過這樣真的有點無趣,
所以還是來稍微介紹一下。這次之所以忽然心血來潮想做,是因為看到
James Edward Gray II 的 higher-order ruby 專欄:
http://blog.grayproductions.net/articles/category/higher-order-ruby
第六篇的:Currying, 他的 curry 實做:

class Proc
def curry(&args_munger)
lambda { |*args| call(*args_munger[args]) }
end
end

老實講,不是說看不懂,可是我不明白為什麼要寫得那麼複雜,乍看之下實在看不太出來。
丟掉他的實做,我試著做了一個:

class Proc
def curry *pre
lambda{ |*post| self[*(pre + post)] }
end
end

就我自己測試起來,效果是一樣的,我認為應該簡潔易懂多了。
可是這根本不太像 curried function 吧?內心吶喊著。
不過在看我後來寫的 curry module 之前,先來簡單介紹一下 currying.

在 lambda caculus 中,每個 function 都只能有一個 argument,
這是因為 lambda caculus 是一種極簡的語言,用來研究某些模型的語言。
但是如果 function 只能吃一個 argument, 有很多事是會做不到的。
於是我們可以靠著 tuple 把許多的 argument 包成一個 argument,
例如在 Haskell 中,tuple 就是 (1,2,3), 用括號括起來的就是 tuple.
所以上面的 (1,2,3) 是一個有三個值的 tuple, 可以把他視為一個值。

比方說有個 function 叫 power, 像是:power 2, 10 會回傳 1024.
uncurried function 就會是 power (2, 10), 他吃一個有兩個元素的 tuple,
吐出一個 1024 的值。可是如果是這樣使用的話,其實是很不方便的。有一個
方法可以讓 function 依然只吃一個 argument, 但是又不需要使用 tuple,
可以一個值一個值傳入,那就是 curried function.

在 functional programming 中,function 的地位極高,不管在做什麼事,
幾乎都是在操作 function. 這也就是所謂的 higher-order function,
操作 function 的 function, 或是產生 function 的 function 諸如此類。
curried function 的效果就是當所吃入的 argument 不足時,他會再吐出另一個
function 去吃其他 argument,直到 argument 足夠時才會吐出結果。

power 2 的回傳會是一個 function, 他記住了 2, 當他再吃一個 argument 後,
則會再把 2 拿出來跟 argument 做運算。所以 power 的 type 會是:
power :: Int -> Int -> Int
結合順序是從右邊開始,所以是吃一個 Int, 吐出 (Int -> Int), 也就是吃一個
Int 吐出一個 Int 的 function. 可以想成這樣:

power2 = power 2
result = power2 10
result # => 1024

也就是說,可以把他看成是一個會不斷記憶 argument 的 function.
看看 James Edward Gray II 的範例:

multiply = lambda { |l, r| l * r }
double = multiply.curry { |args| args + [2] }
triple = multiply.curry { |args| args << 3 }

multiply[5, 2] # => 10
double[5] # => 10
triple[5] # => 15
triple["Howdy "] # => "Howdy Howdy Howdy "

所以他的實做其實很簡單,就是用一個 array 記憶 arguments,
最後再 prepend 到最後的 arguments 裡。

class Proc
def curry(&args_munger)
lambda { |*args| call(*args_munger[args]) }
end
end

不過我覺得不用寫得那麼複雜,所以改寫為:

class Proc
def curry *pre
lambda{ |*post| self[*(pre + post)] }
end
end

這裡利用了 ruby 的 lambda 有 closure 的特性,把 *pre 紀錄
下來,再把他 prepend 到 post 上,最後再呼叫原本的自己(self)。

可是這樣不完整,因為你必須明確表達你需要做 curry, 而 Haskell 的
curried function 是可以讓你忽略這件事的。

lambda{|a,b,c,d,e|}.curry(1).curry(2).curry(3).curry(4).carry(5)

這樣不煩死才怪。我希望能用:

lambda{|a,b,c,d,e|}[1][2][3][4][5]
也能使用:
lambda{|a,b,c,d,e|}[1,2][3][4,5]

可惜我暫時還沒找到好做法 XD
目前暫時僅提供可以 mixin 的 module, 大概是這樣用:

class Array; include Curry; end

接著 array 所有以字母開頭的 method 會多個 curried 版,
prefix c. i.e., map => cmap; foldr => cfoldr

func1 = [1,2,3].cfoldr[:-.to_proc]
assert_equal 2, func1[0]

做法其實很簡單,就只是檢查參數夠了沒,不夠就重新 curry 一份,
夠了就呼叫原始 method. 我原本一直不希望前綴 c, 而以相同名字命名之,
然後原本的名字改為:orig_method. 可惜不管怎麼試都失敗,原因不是很清楚,
但這種 side-effect 超大的動作,會失敗其實也不怎麼奇怪吧,我想。
雖然我總覺得以正常呼叫法而言,應該是沒什麼差才對,也許我有哪裡寫錯了,
只是還沒發現而已。

*

至於其他新增的東西,這裡也稍微介紹一下。首先 Array#filter 只是 select 的
alias, Array#foldl 也只是 inject 的 wrapper. Array#foldr 稍微複雜些,
不過概念上只是類似反過來的 inject 而已。Symbol#to_proc 大家應該都很熟,
連 active_support 裡面也有。只是單純的 message/method 轉換而已。

比較需要提的應該是 Proc#compose 和 Proc#chain.
前者就是數學上的 compose, facets 裡其實也有,不過手癢還是自己做了一份。
他有點類似反向的 inject, 很容易做出來。至於 chain, 這是模仿 C++ 的 loki
中的 functor 中的 chain. 效果很單純,就是把 function 串起來而已。
這拿來做 callback 應該還算方便,例如:

button.on_click = menu.method(:popup).chain button.method(:hide)
接著當按鈕被按下去後,選單就會彈出,且按鈕自動隱藏。
至於 arguments 和 returns 呢?arguments 會統一給所有人。
f1.chain(f2)['XD']
這樣 f1 和 f2 都會接到 'XD' 這個 argument.
return 則會蒐集成一個 array 並 flatten 回去。
[f1 的結果, f2 的結果, f3 的結果,...]
如果 f3 的結果是 array, 則會依序儲存:
[..., f3 的結果1, f3 的結果2, f4 的結果, ...]

這樣做的原因是要讓 chain 還能繼續 chain 而不會出現非常恐怖的 nested array.
f1.chain(f2).chain(f3).chain(f4)
但是其實可以這樣 chain:
f1.chain(f2, f3, f4)
結果和上面的會是相同的。

在 chain 之間的 travel 還沒做,下次有機會時會做。

gem install ludy # to see detail

ruby 寫起來真的很簡潔,很多功能 10 行內都能解決。

2007.08.07

0 retries:

Post a Comment

All texts are licensed under CC Attribution 3.0