首页 > 代码库 > 从lambda到函数式编程
从lambda到函数式编程
1 Object.send(:remove_const,‘TRUE‘) 2 Object.send(:remove_const,‘FALSE‘) 3 4 def to_integer(pro) 5 pro[-> n { n + 1 }][0] 6 end 7 8 def to_boolean(pro) 9 pro[true][false] 10 end 11 12 def to_array(l, count = nil) 13 array = [] 14 until to_boolean(IS_EMPTY[l]) || count == 0 15 array.push FIRST[l] 16 l = REST[l] 17 count = count - 1 unless count.nil? 18 end 19 array 20 end 21 22 def array_map_to_integer(my_list, count = nil) 23 to_array(my_list, count).map{ |p| to_integer(p) } 24 end 25 26 def to_char(c) 27 to_integer(c).chr 28 end 29 30 def to_string(s) 31 to_array(s).map{ |c| to_char(c) }.join 32 end 33 34 def puts_strings(strs) 35 to_array(strs).each do |p| 36 puts to_string(p) 37 end 38 nil 39 end 40 41 ZERO = -> p { -> x { x } } 42 ONE = -> p { -> x { p[x] } } 43 TWO = -> p { -> x { p[p[x]] } } 44 THREE = -> p { -> x { p[p[p[x]]] } } 45 46 FIVE = -> p { -> x { p[p[p[p[p[x]]]]] } } 47 48 FIFTEEN = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]] } } 49 HUNDRED = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] } } 50 51 TRUE = -> x { -> y { x } } 52 FALSE = -> x { -> y { y } } 53 54 IF = -> b { b } 55 56 IS_ZERO = -> n { n[-> x { FALSE }][TRUE] } 57 58 PAIR = -> x { -> y { -> f { f[x][y] } } } 59 LEFT = -> p { p[-> x { -> y { x } }] } 60 RIGHT = -> p { p[-> x { -> y { y } }] } 61 62 INC = -> n { -> p { -> x { p[n[p][x]] } } } 63 64 SLIDE = -> p { PAIR[RIGHT[p]][INC[RIGHT[p]]] } 65 DEC = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] } 66 67 ADD = -> m { -> n { n[INC][m] } } 68 SUB = -> m { -> n { n[DEC][m] } } 69 MUL = -> m { -> n { n[ADD[m]][ZERO] } } 70 POW = -> m { -> n { n[MUL[m]][ONE] } } 71 72 IS_LESS_OR_EQUAL = 73 -> m { -> n { IS_ZERO[SUB[m][n]] } } 74 75 Z = -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] } 76 MOD = Z[-> f { -> m { -> n { 77 IF[IS_LESS_OR_EQUAL[n][m]][ 78 -> x { 79 f[SUB[m][n]][n][x] 80 } 81 ][ 82 m 83 ] 84 } } }] 85 86 DIV = Z[-> f { -> m { -> n { 87 IF[IS_LESS_OR_EQUAL[n][m]][ 88 -> x { 89 INC[f[SUB[m][n]][n]][x] 90 } 91 ][ 92 ZERO 93 ] 94 } } } ] 95 96 EMPTY = PAIR[TRUE][TRUE] 97 UNSHIFT = -> l { -> x { PAIR[FALSE][PAIR[x][l]] } } 98 IS_EMPTY= LEFT 99 FIRST = -> l { LEFT[RIGHT[l]] }100 REST = -> l { RIGHT[RIGHT[l]] }101 102 PUSH = -> l { -> x {103 FOLD[l][UNSHIFT[EMPTY][x]][UNSHIFT]104 } }105 106 RANGE = Z[-> f { 107 -> m { -> n {108 IF[IS_LESS_OR_EQUAL[m][n]][109 -> x {110 UNSHIFT[f[INC[m]][n]][m][x]111 }112 ][113 EMPTY114 ]115 } } 116 }]117 FOLD = Z[-> f {118 -> l { -> x { -> g {119 IF[IS_EMPTY[l]][120 x121 ][122 -> y {123 g[f[REST[l]][x][g]][FIRST[l]][y]124 }125 ]126 } } }127 }]128 129 MAP = -> k { -> f {130 FOLD[k][EMPTY][131 -> l { -> x { UNSHIFT[l][f[x]] } }132 ]133 } }134 135 TEN = MUL[TWO][FIVE]136 ASC_48 = MUL[MUL[THREE][INC[THREE]]][INC[THREE]]137 ASC_65 = ADD[MUL[ADD[FIVE][ONE]][TEN]][FIVE]138 CHAR_B = INC[ASC_65]139 CHAR_F = ADD[ASC_65][FIVE]140 CHAR_I = ADD[CHAR_F][THREE]141 CHAR_U = ADD[CHAR_I][MUL[THREE][INC[THREE]]]142 CHAR_Z = ADD[CHAR_U][FIVE]143 144 FIZZ = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][CHAR_Z]][CHAR_Z]][CHAR_I]][CHAR_F]145 BUZZ = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][CHAR_Z]][CHAR_Z]][CHAR_U]][CHAR_B]146 FIZZBUZZ= UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[BUZZ][CHAR_Z]][CHAR_Z]][CHAR_I]][CHAR_F]147 148 TO_DIGITS=149 Z[-> f { -> n { PUSH[150 IF[IS_LESS_OR_EQUAL[n][DEC[TEN]]][151 EMPTY152 ][153 -> x {154 f[DIV[n][TEN]][x]155 }156 ]157 ][ADD[MOD[n][TEN]][ASC_48]] } } ]158 159 SOLUTION=160 MAP[RANGE[ONE][HUNDRED]][-> n {161 IF[IS_ZERO[MOD[n][FIFTEEN]]][162 FIZZBUZZ163 ][IF[IS_ZERO[MOD[n][THREE]]][164 FIZZ165 ][IF[IS_ZERO[MOD[n][FIVE]]][166 BUZZ167 ][168 TO_DIGITS[n]169 ]]]170 } ]171 172 ZEROS = Z[-> f { UNSHIFT[f][ZERO] }]173 UPWARDS_OF = Z[-> f { -> n { UNSHIFT[-> x { f[INC[n]][x] }][n] } }]174 MULTIPLES_OF = 175 -> m {176 Z[-> f {177 -> n { UNSHIFT[-> x { f[ADD[m][n]][x] }][n] }178 }][m]179 }180 MULTIPLY_STREAMS =181 Z[-> f {182 -> k { -> l {183 UNSHIFT[-> x { f[REST[k]][REST[l]][x] }][MUL[FIRST[k]][FIRST[l]]]184 } }185 }]
在λ演算中，每个表达式都代表一个函数，这个函数有一个参数，并且返回一个值。不论是参数和返回值，也都是一个单参的函数。可以这么说，λ演算中，只有一种“类型”，那就是这种单参函数。
在lambda演算中有许多方式都可以定义自然数，但最常见的还是邱奇数。
ZERO = -> p { -> x { x } }ONE = -> p { -> x { p[x] } }TWO = -> p { -> x { p[p[x]] } }THREE = -> p { -> x { p[p[p[x]]] } }FIVE = -> p { -> x { p[p[p[p[p[x]]]]] } }FIFTEEN = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]] } }HUNDRED = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] } }以此类推。直观地说，lambda演算中的数字n就是一个把函数f作为参数并以f的n次幂为返回值的函数。换句话说，邱奇整数是一个高阶函数 -- 以单一参数函数f为参数，返回另一个单一参数的函数。
习惯上，下述两个定义（称为邱奇布尔值）被用作TRUE和FALSE这样的布尔值：
TRUE = -> x { -> y { x } }FALSE = -> x { -> y { y } }“谓词”是指返回布尔值的函数。最基本的一个谓词是ISZERO，当且仅当其参数为零时返回真，否则返回假：
IS_ZERO = -> n { n[-> x { FALSE }][TRUE] }运用谓词与上述TRUE和FALSE的定义，使得"if-then-else"这类语句很容易用lambda演算写出。
有序对（2-元组）数据类型可以用TRUE、FALSE和IF来定义。
PAIR = -> x { -> y { -> f { f[x][y] } } }LEFT = -> p { p[-> x { -> y { x } }] }RIGHT = -> p { p[-> x { -> y { y } }] }链表数据类型可以定义为，要么是为空列表保留的值（e.g.FALSE），要么是CONS一个元素和一个更小的列表。
EMPTY = PAIR[TRUE][TRUE]UNSHIFT = -> l { -> x { PAIR[FALSE][PAIR[x][l]] } }IS_EMPTY= LEFTFIRST = -> l { LEFT[RIGHT[l]] }REST = -> l { RIGHT[RIGHT[l]] }
递归是使用函数自身的函数定义；在表面上，lambda演算不允许这样。但是这种印象是误解。
使用Y组合子和Z组合子实现可以递归：
Z = -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }
从lambda到函数式编程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。