从lambda到函数式编程

时间:2022-10-12 19:12:09

 

从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               EMPTY
114               ]
115             } } 
116           }]
117 FOLD    = Z[-> f {
118             -> l { -> x { -> g {
119               IF[IS_EMPTY[l]][
120                 x
121               ][
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       EMPTY
152     ][
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       FIZZBUZZ
163     ][IF[IS_ZERO[MOD[n][THREE]]][
164       FIZZ
165     ][IF[IS_ZERO[MOD[n][FIVE]]][
166       BUZZ
167     ][
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   }]
View Code

在λ演算中,每个表达式都代表一个函数,这个函数有一个参数,并且返回一个值。不论是参数和返回值,也都是一个单参的函数。可以这么说,λ演算中,只有一种“类型”,那就是这种单参函数。

在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= LEFT
FIRST   = -> 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] }] }] }