不動点コンビネータ？

社内勉強会用資料です

Transcript

1. @yubessy 0x64 Reboot #12 "λ"
2. ※ JavaScript(ES6)
3. Q1.
4. A1. for (var p = 1, n = 1; n <= 5; n++) p *= n p // -> 120
5. Q2.
6. A2. var f = n => n == 0 ? 1 : n * f(n - 1) f(5) // -> 120
7. Q3.
8. A3. ※ (g => (h => g(y => h(h)(y)))(h => g(y => h(h)(y)))) (f => n => n == 0 ? 1 : n * f(n - 1)) (5) (g => (h => g(y => h(h)(y)))(h => g(y => h(h)(y))))(f => n => n // -> 120
9. Z = g => (h => g(y => h(h)(y)))(h => g(y => h(h)(y))) g = f => n => n == 0 ? 1 : n * f(n - 1) x = 5 g A2 f = n => n == 0 ? 1 : n * f(n - 1)
10. Z Z(g) = g(Z(g)) Z(g)(5) = g(Z(g))(5) = (f => n => n == 0 ? 1 : n * f(n - 1))(Z(g))(5) = (n => n == 0 ? 1 : n * (Z(g))(n - 1))(5) = 5 == 0 ? 1 : 5 * (Z(g))(5 - 1) = 5 * (Z(g))(4) = ... = 5 * 4 * 3 * 2 * 1 ※ 3 Z(g)
11. Z = g => (h => g(y => h(h)(y)))(h => g(y => h(h)(y))) Z(g) = g(Z(g)) Z(g) = (g => (h => g(y => h(h)(y)))(h => g(y => h(h)(y))))(g) = (h => g(y => h(h)(y)))(h => g(y => h(h)(y))) = (h => g(x => h(h)(x)))(h => g(y => h(h)(y))) // α- = g(x => (h => g(y => h(h)(y)))(h => g(y => h(h)(y)))(x)) = g((h => g(y => h(h)(y)))(h => g(y => h(h)(y))) // η- = g(Z(g))
12. (g => (h => g(y => h(h)(y)))(h => g(y => h(h)(y)))) (f => n => n == 0 ? 1 : n * f(n - 1)) (5) = = fix(g) = g(fix(g)) fix Z ※
13. ->
15. ->
16. (g => g(g))(f => n => n == 0 ? 1 : n * f(f)(n - 1))(5) g => g(g)
17. body body http://matt.might.net/articles/js-church/
18. -> 1 2 -> Haskell OCaml ES6 https://en.wikipedia.org/wiki/Fixed- point_combinator#Type_for_the_Y_combinator http://okmij.org/ftp/Computation/ xed-point- combinators.html
19. toolbox Haskell \f -> f f \g -> (\h -> g (h h)) (\h -> g (h h)) \f -> \n -> if n == 0 then 1 else n * f(n - 1) newtype Rec a = In { out :: Rec a -> a } \f -> (\x -> f (out x x)) (In (\x -> f (out x x))) \f -> \n -> if n == 0 then 1 else n * f(n - 1) OCaml (with -rectypes ) fun f -> f f fun g -> (fun h y -> g (h h) y) (fun h y -> g (h h) y) fun f n -> if n == 0 then 1 else n * f(n - 1)