函数式编程理论1. 技术分析1.1 函数式编程概述函数式编程是一种编程范式核心特征 纯函数: 无副作用 不可变数据: 数据不可修改 函数组合: 组合函数 递归: 替代循环 函数式概念: Lambda演算 高阶函数 柯里化 Monad1.2 Lambda演算Lambda演算要素 变量: x, y, z 抽象: λx.E 应用: (E1 E2) 归约规则: α-转换: 重命名变量 β-归约: 应用抽象 η-转换: 函数等价1.3 函数式语言对比语言纯函数式类型系统特性Haskell是静态强类型惰性求值Scala否静态强类型混合范式Clojure否动态类型Lisp方言2. 核心功能实现2.1 Lambda演算解释器class LambdaEvaluator: def __init__(self): pass def parse(self, expr): expr expr.replace( , ) if expr.startswith(λ): idx expr.find(.) param expr[1:idx] body expr[idx1:] return {type: abs, param: param, body: self.parse(body)} elif expr.startswith((): depth 1 idx 1 while depth 0: if expr[idx] (: depth 1 elif expr[idx] ): depth - 1 idx 1 first self.parse(expr[1:idx-1]) if idx len(expr): second self.parse(expr[idx:]) return {type: app, func: first, arg: second} return first else: return {type: var, name: expr} def evaluate(self, expr, envNone): if env is None: env {} if expr[type] var: return env.get(expr[name], expr) elif expr[type] abs: return expr elif expr[type] app: func self.evaluate(expr[func], env) if func[type] abs: new_env env.copy() new_env[func[param]] self.evaluate(expr[arg], env) return self.evaluate(func[body], new_env) return {type: app, func: func, arg: self.evaluate(expr[arg], env)} def to_string(self, expr): if expr[type] var: return expr[name] elif expr[type] abs: return fλ{expr[param]}.{self.to_string(expr[body])} elif expr[type] app: return f({self.to_string(expr[func])}{self.to_string(expr[arg])}2.2 高阶函数class HigherOrderFunctions: def __init__(self): pass def map(self, func, iterable): return [func(x) for x in iterable] def filter(self, func, iterable): return [x for x in iterable if func(x)] def reduce(self, func, iterable, initialNone): it iter(iterable) if initial is None: try: value next(it) except StopIteration: return None else: value initial for element in it: value func(value, element) return value def compose(self, *funcs): def composed(*args): result args for func in reversed(funcs): result func(*result) if isinstance(result, tuple) else func(result) return result return composed def curry(self, func): def curried(*args): if len(args) func.__code__.co_argcount: return func(*args) def partial(*more_args): return curried(*(args more_args)) return partial return curried2.3 惰性求值class LazyList: def __init__(self, generator): self.generator generator self.cache [] def __getitem__(self, index): while len(self.cache) index: try: self.cache.append(next(self.generator)) except StopIteration: raise IndexError(Index out of range) return self.cache[index] def __iter__(self): index 0 while True: try: yield self[index] index 1 except IndexError: break def take(self, n): return [self[i] for i in range(n)] def filter(self, func): def filtered_generator(): for item in self: if func(item): yield item return LazyList(filtered_generator()) def map(self, func): def mapped_generator(): for item in self: yield func(item) return LazyList(mapped_generator()) def natural_numbers(): n 0 while True: yield n n 12.4 Monad实现class Maybe: def __init__(self, valueNone, is_noneFalse): self.value value self.is_none is_none classmethod def just(cls, value): return cls(value, False) classmethod def nothing(cls): return cls(None, True) def bind(self, func): if self.is_none: return Maybe.nothing() result func(self.value) if isinstance(result, Maybe): return result return Maybe.just(result) def map(self, func): if self.is_none: return Maybe.nothing() return Maybe.just(func(self.value)) def __repr__(self): if self.is_none: return Nothing return fJust({self.value}) class Either: def __init__(self, is_left, value): self.is_left is_left self.value value classmethod def left(cls, value): return cls(True, value) classmethod def right(cls, value): return cls(False, value) def bind(self, func): if self.is_left: return self result func(self.value) if isinstance(result, Either): return result return Either.right(result) def fold(self, left_func, right_func): if self.is_left: return left_func(self.value) return right_func(self.value)3. 性能对比3.1 求值策略对比策略特点性能适用场景惰性求值按需计算中无限序列严格求值立即计算高通用按需调用缓存结果中重复计算3.2 函数式语言对比语言性能生态学习曲线Haskell中中高Scala高高中Clojure中中中3.3 Monad对比Monad用途复杂度常用性Maybe空值处理低高Either错误处理低高IO副作用中高4. 最佳实践4.1 函数式编程模式def functional_patterns(): # 使用高阶函数 numbers [1, 2, 3, 4, 5] doubled list(map(lambda x: x * 2, numbers)) even list(filter(lambda x: x % 2 0, numbers)) sum_total reduce(lambda x, y: x y, numbers) # 使用柯里化 curry def add(x, y): return x y add5 add(5) # 使用组合 square lambda x: x ** 2 increment lambda x: x 1 composed compose(square, increment) return { doubled: doubled, even: even, sum: sum_total, add5_result: add5(3), composed_result: composed(2) }4.2 Monad使用def monad_examples(): # Maybe monad def safe_divide(a, b): if b 0: return Maybe.nothing() return Maybe.just(a / b) result Maybe.just(10).bind(lambda x: safe_divide(x, 2)) print(fSafe divide result: {result}) # Either monad def parse_int(s): try: return Either.right(int(s)) except ValueError: return Either.left(fCannot parse {s}) parsed parse_int(42).fold( lambda err: fError: {err}, lambda val: fSuccess: {val} ) print(fParse result: {parsed})5. 总结函数式编程是一种强大的编程范式Lambda演算函数式编程的理论基础高阶函数函数作为一等公民惰性求值按需计算Monad处理副作用对比数据如下惰性求值适合无限序列Haskell最纯正的函数式语言Maybe和Either最常用的Monad推荐使用高阶函数提高代码复用性函数式编程可以提高代码的可读性和可维护性。
函数式编程理论
函数式编程理论1. 技术分析1.1 函数式编程概述函数式编程是一种编程范式核心特征 纯函数: 无副作用 不可变数据: 数据不可修改 函数组合: 组合函数 递归: 替代循环 函数式概念: Lambda演算 高阶函数 柯里化 Monad1.2 Lambda演算Lambda演算要素 变量: x, y, z 抽象: λx.E 应用: (E1 E2) 归约规则: α-转换: 重命名变量 β-归约: 应用抽象 η-转换: 函数等价1.3 函数式语言对比语言纯函数式类型系统特性Haskell是静态强类型惰性求值Scala否静态强类型混合范式Clojure否动态类型Lisp方言2. 核心功能实现2.1 Lambda演算解释器class LambdaEvaluator: def __init__(self): pass def parse(self, expr): expr expr.replace( , ) if expr.startswith(λ): idx expr.find(.) param expr[1:idx] body expr[idx1:] return {type: abs, param: param, body: self.parse(body)} elif expr.startswith((): depth 1 idx 1 while depth 0: if expr[idx] (: depth 1 elif expr[idx] ): depth - 1 idx 1 first self.parse(expr[1:idx-1]) if idx len(expr): second self.parse(expr[idx:]) return {type: app, func: first, arg: second} return first else: return {type: var, name: expr} def evaluate(self, expr, envNone): if env is None: env {} if expr[type] var: return env.get(expr[name], expr) elif expr[type] abs: return expr elif expr[type] app: func self.evaluate(expr[func], env) if func[type] abs: new_env env.copy() new_env[func[param]] self.evaluate(expr[arg], env) return self.evaluate(func[body], new_env) return {type: app, func: func, arg: self.evaluate(expr[arg], env)} def to_string(self, expr): if expr[type] var: return expr[name] elif expr[type] abs: return fλ{expr[param]}.{self.to_string(expr[body])} elif expr[type] app: return f({self.to_string(expr[func])}{self.to_string(expr[arg])}2.2 高阶函数class HigherOrderFunctions: def __init__(self): pass def map(self, func, iterable): return [func(x) for x in iterable] def filter(self, func, iterable): return [x for x in iterable if func(x)] def reduce(self, func, iterable, initialNone): it iter(iterable) if initial is None: try: value next(it) except StopIteration: return None else: value initial for element in it: value func(value, element) return value def compose(self, *funcs): def composed(*args): result args for func in reversed(funcs): result func(*result) if isinstance(result, tuple) else func(result) return result return composed def curry(self, func): def curried(*args): if len(args) func.__code__.co_argcount: return func(*args) def partial(*more_args): return curried(*(args more_args)) return partial return curried2.3 惰性求值class LazyList: def __init__(self, generator): self.generator generator self.cache [] def __getitem__(self, index): while len(self.cache) index: try: self.cache.append(next(self.generator)) except StopIteration: raise IndexError(Index out of range) return self.cache[index] def __iter__(self): index 0 while True: try: yield self[index] index 1 except IndexError: break def take(self, n): return [self[i] for i in range(n)] def filter(self, func): def filtered_generator(): for item in self: if func(item): yield item return LazyList(filtered_generator()) def map(self, func): def mapped_generator(): for item in self: yield func(item) return LazyList(mapped_generator()) def natural_numbers(): n 0 while True: yield n n 12.4 Monad实现class Maybe: def __init__(self, valueNone, is_noneFalse): self.value value self.is_none is_none classmethod def just(cls, value): return cls(value, False) classmethod def nothing(cls): return cls(None, True) def bind(self, func): if self.is_none: return Maybe.nothing() result func(self.value) if isinstance(result, Maybe): return result return Maybe.just(result) def map(self, func): if self.is_none: return Maybe.nothing() return Maybe.just(func(self.value)) def __repr__(self): if self.is_none: return Nothing return fJust({self.value}) class Either: def __init__(self, is_left, value): self.is_left is_left self.value value classmethod def left(cls, value): return cls(True, value) classmethod def right(cls, value): return cls(False, value) def bind(self, func): if self.is_left: return self result func(self.value) if isinstance(result, Either): return result return Either.right(result) def fold(self, left_func, right_func): if self.is_left: return left_func(self.value) return right_func(self.value)3. 性能对比3.1 求值策略对比策略特点性能适用场景惰性求值按需计算中无限序列严格求值立即计算高通用按需调用缓存结果中重复计算3.2 函数式语言对比语言性能生态学习曲线Haskell中中高Scala高高中Clojure中中中3.3 Monad对比Monad用途复杂度常用性Maybe空值处理低高Either错误处理低高IO副作用中高4. 最佳实践4.1 函数式编程模式def functional_patterns(): # 使用高阶函数 numbers [1, 2, 3, 4, 5] doubled list(map(lambda x: x * 2, numbers)) even list(filter(lambda x: x % 2 0, numbers)) sum_total reduce(lambda x, y: x y, numbers) # 使用柯里化 curry def add(x, y): return x y add5 add(5) # 使用组合 square lambda x: x ** 2 increment lambda x: x 1 composed compose(square, increment) return { doubled: doubled, even: even, sum: sum_total, add5_result: add5(3), composed_result: composed(2) }4.2 Monad使用def monad_examples(): # Maybe monad def safe_divide(a, b): if b 0: return Maybe.nothing() return Maybe.just(a / b) result Maybe.just(10).bind(lambda x: safe_divide(x, 2)) print(fSafe divide result: {result}) # Either monad def parse_int(s): try: return Either.right(int(s)) except ValueError: return Either.left(fCannot parse {s}) parsed parse_int(42).fold( lambda err: fError: {err}, lambda val: fSuccess: {val} ) print(fParse result: {parsed})5. 总结函数式编程是一种强大的编程范式Lambda演算函数式编程的理论基础高阶函数函数作为一等公民惰性求值按需计算Monad处理副作用对比数据如下惰性求值适合无限序列Haskell最纯正的函数式语言Maybe和Either最常用的Monad推荐使用高阶函数提高代码复用性函数式编程可以提高代码的可读性和可维护性。
