Ads
順便求C4F指點下點樣係Haskell度implement Y/fix combinator?
i.e.呢舊嘢:
Y = λ y . ( λ x . y (x x)) ( λ x . y (x x))
or
Y = λ f . ( λ x . f (x x)) ( λ x . f (x x))
or
Yf
Yf produces fYf produces f(fYf) produces f(f(fYf)) ... as recursion
我見stackoverflow話Y唔屬於Haskell built-in 嘅任何一個type, 就咁define Y 去 implement會出error, 咁應該點做呢? 可否用factorial做example教下點implement Y combinator? :^(
Thanks in advance! :^(
ok睇唔明 :^(
順便求C4F指點下點樣係Haskell度implement Y/fix combinator?
i.e.呢舊嘢:
Y = λ y . ( λ x . y (x x)) ( λ x . y (x x))
or
Y = λ f . ( λ x . f (x x)) ( λ x . f (x x))
or
Yf
Yf produces fYf produces f(fYf) produces f(f(fYf)) ... as recursion
我見stackoverflow話Y唔屬於Haskell built-in 嘅任何一個type, 就咁define Y 去 implement會出error, 咁應該點做呢? 可否用factorial做example教下點implement Y combinator? :^(
Thanks in advance! :^(
順便求C4F指點下點樣係Haskell度implement Y/fix combinator?
i.e.呢舊嘢:
Y = λ y . ( λ x . y (x x)) ( λ x . y (x x))
or
Y = λ f . ( λ x . f (x x)) ( λ x . f (x x))
or
Yf
Yf produces fYf produces f(fYf) produces f(f(fYf)) ... as recursion
我見stackoverflow話Y唔屬於Haskell built-in 嘅任何一個type, 就咁define Y 去 implement會出error, 咁應該點做呢? 可否用factorial做example教下點implement Y combinator? :^(
Thanks in advance! :^(
純lambda calculus係唔type嘅。Haskell有type system限制(Hindley Milner type system唔能夠代表到y combinator嘅type),唔可以寫到純lambda calculus嘅y combinator。
http://stackoverflow.com/questions/4273413/y-combinator-in-haskell
Haskell嘅fixed point operator叫fix
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> import Data.Function
Prelude Data.Function> :t fix
fix :: (a -> a) -> a
Prelude Data.Function> let fact f n = if n == 0 then 1 else n * f (n - 1)
Prelude Data.Function> :t fix fact
fix fact :: (Eq a, Num a) => a -> a
Prelude Data.Function> fix fact 5
120
Prelude Data.Function> map (fix fact) [0..10]
[1,1,2,6,24,120,720,5040,40320,362880,3628800]
Prelude Data.Function> let y f = f (y f) -- not really the y combinator
Prelude Data.Function> :type y
y :: (t -> t) -> t
Prelude Data.Function> y fact 5
120
Prelude Data.Function> map (y fact) [0..10]
[1,1,2,6,24,120,720,5040,40320,362880,3628800]
Prelude Data.Function>
我以前響高登講過點用lisp寫y combinator。不過因為strict evaluation關係,同pure lambda calculus都係有dd分別。
http://forum14.hkgolden.com/view.aspx?type=SW&message=5112005&highlight_id=0&page=2&authorOnly=False
順便求C4F指點下點樣係Haskell度implement Y/fix combinator?
i.e.呢舊嘢:
Y = λ y . ( λ x . y (x x)) ( λ x . y (x x))
or
Y = λ f . ( λ x . f (x x)) ( λ x . f (x x))
or
Yf
Yf produces fYf produces f(fYf) produces f(f(fYf)) ... as recursion
我見stackoverflow話Y唔屬於Haskell built-in 嘅任何一個type, 就咁define Y 去 implement會出error, 咁應該點做呢? 可否用factorial做example教下點implement Y combinator? :^(
Thanks in advance! :^(
純lambda calculus係唔type嘅。Haskell有type system限制(Hindley Milner type system唔能夠代表到y combinator嘅type),唔可以寫到純lambda calculus嘅y combinator。
http://stackoverflow.com/questions/4273413/y-combinator-in-haskell
Haskell嘅fixed point operator叫fix
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> import Data.Function
Prelude Data.Function> :t fix
fix :: (a -> a) -> a
Prelude Data.Function> let fact f n = if n == 0 then 1 else n * f (n - 1)
Prelude Data.Function> :t fix fact
fix fact :: (Eq a, Num a) => a -> a
Prelude Data.Function> fix fact 5
120
Prelude Data.Function> map (fix fact) [0..10]
[1,1,2,6,24,120,720,5040,40320,362880,3628800]
Prelude Data.Function> let y f = f (y f) -- not really the y combinator
Prelude Data.Function> :type y
y :: (t -> t) -> t
Prelude Data.Function> y fact 5
120
Prelude Data.Function> map (y fact) [0..10]
[1,1,2,6,24,120,720,5040,40320,362880,3628800]
Prelude Data.Function>
我以前響高登講過點用lisp寫y combinator。不過因為strict evaluation關係,同pure lambda calculus都係有dd分別。
http://forum14.hkgolden.com/view.aspx?type=SW&message=5112005&highlight_id=0&page=2&authorOnly=False
明白哂, 咁即係Haskell冇純Y combinator嗰隻type, 唯有用番Data.Function library裏面個fix operator嚟攪, 或者偷雞用let y f = f (y f) 算數, 總之就冇得自己define個真真正正嘅Y combinator啦! :^(
ok睇唔明 :^(
Ads
上次C4F巴打講完, 我都去刨左果篇PAPER, 諗法幾得意
雖然一手計就寫到手軟 :^( :^( :^(
完全唔明 :^(
multiplication:
我地可以當Church numerals係一般數目,咁乘法可以咁做:
2 * 3 = (((0 + 2) + 2) + 2)
mul = (λ m . (λ n . (n (λ x . ((add m) x))) 0))
但如果考慮埋Church numeral同function composition嘅關係,可以聰明D:
mul = (λ m . (λ n . (λ f . (m (n f)))))
multiplication:
我地可以當Church numerals係一般數目,咁乘法可以咁做:
2 * 3 = (((0 + 2) + 2) + 2)
mul = (λ m . (λ n . (n (λ x . ((add m) x))) 0))
但如果考慮埋Church numeral同function composition嘅關係,可以聰明D:
mul = (λ m . (λ n . (λ f . (m (n f)))))
順手砌埋arithmetic mul operator e.g. multiply x and y
mul = λ x y s . x (y s)
:^(
有加有乘,減數點做? :^(
有加有乘,減數點做? :^(
睇完呢篇嘢http://gettingsharper.de/2012/08/30/lambda-calculus-subtraction-is-hard/後放棄咗! 雖然Church encoding話subtraction只是咁樣: sub = λ x y . y pred x , 但我唔太理解個pred點整出嚟, 就算整到個pred出嚟, 個sub都唔係真subtraction嚟, 篇嘢有講原因!
In short, it's not too meaningful to implement a subtraction operator in terms of plain λ calculus, 好似係! :^(
Ads
有加有乘,減數點做? :^(
睇完呢篇嘢http://gettingsharper.de/2012/08/30/lambda-calculus-subtraction-is-hard/後放棄咗! 雖然Church encoding話subtraction只是咁樣: sub = λ x y . y pred x , 但我唔太理解個pred點整出嚟, 就算整到個pred出嚟, 個sub都唔係真subtraction嚟, 篇嘢有講原因!
In short, it's not too meaningful to implement a subtraction operator in terms of plain λ calculus, 好似係! :^(
有加有乘,減數點做? :^(
睇完呢篇嘢http://gettingsharper.de/2012/08/30/lambda-calculus-subtraction-is-hard/後放棄咗! 雖然Church encoding話subtraction只是咁樣: sub = λ x y . y pred x , 但我唔太理解個pred點整出嚟, 就算整到個pred出嚟, 個sub都唔係真subtraction嚟, 篇嘢有講原因!
In short, it's not too meaningful to implement a subtraction operator in terms of plain λ calculus, 好似係! :^(
哈,呢篇野嘅方法基本上同我嘅係一樣。
Zero = λ s z . z
One = λ s z . s z
Two = λ s z . s (s z)
Three = λ s z . s (s (s z))
(where s = successor, z = zero)
2. 跟住砌埋arithmetic add operator e.g add x and y
add = λ s z x y . x s (y s z)
3. 然後用Church Boolean砌logical and/or/not operators
TRUE = λ t f . t
FALSE = λ t f . f
And = λ x y . x y FALSE
Or = λ x y. x TRUE y
Not = λ x . x FALSE TRUE
Conclusion: 阿Church真係CLS, 簡真天才嚟, 佢點諗到架?!!!
(BTW, 學λ Calculus基本上只需要明白α-conversion(用嚟avoid namespace collision between different functions)同β-reduction(用嚟do computation)呢兩個簡單operations,加上知道下lazy evaluation係左去右(唔同平時見慣嘅右去左eager evaluation)就OK了, 唔算好複雜, 比mathematical Differential Calculus淺好多好多!