函数式编程入门(一)

什么是函数式编程?

如果你在互联网上搜索函数式编程( Functional Programming, 下文简写为 FP) 相关的问题, 你或许会发现大量的关于 FP 与 OOP 的比较与争论^[1], 又或者从范畴学角度一讲就是态射,变化式,仿函数,单子...

但是理解这些之前,我们需要清晰一个更基本的问题:

FP 是什么?

在这里, 也许我们可以这样下一个不太严谨的定义, FP 是一种编程范式, 旨在构建强约束、数学性的“框架”来优化代码

当然, 这样说可能有点抽象, 接下来会我们一步步尝试理解函数式编程的基本概念

前提: 一等公民函数

无论如何,函数式编程依赖于一个基本的前提:

函数是一等公民

也就是说函数可以和其他任何对象都一样使用, 比如支持作为参数传递等

相反的,c 语言中函数就不是一等公民, 你只能传递函数指针,而没有函数的上下文与闭包环境,

因此, 在 c 语言中指针是一等公民, 但函数不是

不过不用担心, 如今现代编程语言cpp/python/java/js/...已经多多少少都提供了一些函数式编程的支持

核心概念: 纯函数

纯函数是这样一种函数，即相同的输入，永远会得到相同的输出，而且没有任何可观察的副作用。

等等, 这不就是数学上函数的定义吗?

是的,所谓纯函数就是数学上的函数

在函数式编程中, 我们希望所有的函数都是纯函数

而在后面我们会学习许多技巧,让我们尝试尽可能的把不纯的函数转为或者分离出纯函数

那纯函数有什么好处呢?为什么我们要尽可能的转为纯函数?

先来看看愚蠢的代码例子:

author="open17"
def say_author_name():
    return f"{author.upper()}!"
say_author_name()

显然,大学第一门语言课中, 或许我们就多半学过要尽力避免使用这种糟糕的全局变量, 解决的办法也很多, 最简单的比如author改为传参, 又或者author改为不可变类型

def say_author_name(author):
    return f"{author.upper()}!"
say_author_name("open17")

你会发现, 遵循这样的常识修改之后, 我们不知不觉的把say_author_name转为了纯函数

是的, 纯函数不是什么高大上的东西, 也许很多时候我们在无意识中就会尽力的把函数优化为纯函数

而在函数式编程, 与其他范式不同的是, 我们会进一步加强这种约束,尽可能将所以函数转为纯函数

同时上面的例子其实也展示了纯函数的优点:

它尽可能的避免对于系统状态的依赖(全局变量)

对于系统状态的依赖是一种副作用, 而副作用中的“副”是滋生 bug 的温床

副作用是在计算结果的过程中，系统状态的一种变化，或者与外部世界进行的可观察的交互。

而在 FP 中, 我们希望构建纯函数来尽可能的让副作用在可控的范围内发生

不要小看这一点, 让副作用可控, 意义十分重大

比如纯函数基本不需要访问共享的内存, 可以简化程序在并发中遇到的很多问题与困难, 无需痛苦的思考要怎么上锁, 怎么设置信号量...

此外纯函数还有很多优点,比如支持 memo,便于移植,引用透明...

重要工具: 柯里化

柯里化(curry), 是一种 FP 基本工具, 可以快速方便的使我们书写纯函数

curry 的概念很简单：只传递给函数一部分参数来调用它，让它返回一个函数去处理剩下的参数。

柯里化原理就是利用闭包, 我们可以手写一个最简单的柯里化

def curried_add(x):
    def add_y(y):
        return x + y
    return add_y

add_5 = curried_add(5)
print(add_5(3)) # 输出8

利用柯里化,我们可以维护纯函数定义的同时利用简单的传递参数写出很多 fancy 的代码

值得一提的是局部调与柯里化是不完全等价的,柯里化可以视为局部调用的子集

尽管 python 本身是支持局部调用的,但为了方便起见我们还是简单的实现一个柯里化的装饰器

def curry(func):
    def curried(*args):
        if len(args) >= func.__code__.co_argcount:
            return func(*args)
        return lambda *next_args: curried(*args, *next_args)
    return curried

下面是另一个柯里化的简单例子, 可以方便的通过修改简单的参数构造前缀和,前缀积等前缀函数

@curry
def dynamic_prefix(op: callable, nums: List[int], left: int, right: int):
    pre_num=[0] + list(accumulate(nums, op))
    return pre_num[right + 1] - pre_num[left]

presum=dynamic_prefix(add)
premult=dynamic_prefix(mul)


presum_arr=presum([11,2,5,3,10])
premult_arr=premult([11,2,5,3,10])

print(presum_arr(2,4),premult_arr(0,1))

重要工具: 组合

组合是定义在纯函数上的

既然纯函数是都是数学上的函数,怎么能没有组合函数的概念呢?

如果你不了解离散数学中组合函数的定义也没关系,一个简单的组合可以视为如下代码

def compose(f,g):
    def composed(x):
        return f(g(x))
    return composed

要注意到组合函数是满足交换律的,这点可以帮助我们优化代码

compose(f, compose(g, h)) == compose(compose(f, g), h);

回到之前柯里化的例子, 有时候前缀和我们不需要求区间的值, 因此我们可以拆开, 在需要的时候再组合

def compose(*functions):
    return reduce(lambda f, g: lambda x: f(g(x)), functions)

@curry
def dynamic_prefix(op: callable, nums: List[int]):
    return [0] + list(accumulate(nums, op))

@curry
def prefix_range(pre_num: List[int] , left: int, right: int):
    return pre_num[right + 1] - pre_num[left]

presum=dynamic_prefix(add)

presum_range=compose(prefix_range, presum)

print(presum_range([1,2,3])(1,2))

技巧: 延迟执行

或许你会敏锐的发现, 很多时候我们与外部交互(也就是副作用)是不可避免的

比如 python 发送 http 请求, 这显然是不纯的函数:

def get_cid(bvid):
    url=f"https://api.bilibili.com/x/player/pagelist?bvid+{bvid}"
    return requests.get(url).json()['data']

如何变成一个纯函数呢?

def get_cid(bvid):
    url=f"https://api.bilibili.com/x/player/pagelist?bvid={bvid}"
    def f():
        return requests.get(url).json()['data']
    return f

这就是一个延迟执行的纯函数了,我们可以对它使用任何纯函数才能使用的工具(组合,memo 等)

当然, 你会觉得这并没什么什么特别的意义, 在讲到 functor(仿函数)的时候我们会进一步讨论这一点

总结

懒得写,基于 gpt 生成的

函数式编程（Functional Programming, FP）是一种基于数学思想的编程范式，强调通过纯函数等核心概念，构建更加稳定、可预测的程序逻辑。

本文从基础的“一等公民函数”出发，逐步引入 FP 的核心理念和实用工具，帮助我们理解其魅力和应用场景：

纯函数 是 FP 的基础，具备不依赖外部状态、无副作用的特性，能够提高代码的可维护性、并发性和可预测性。
柯里化 提供了一种简洁灵活的方式来构建纯函数，使得我们可以通过组合小函数来构建复杂的逻辑。
函数组合 让我们像数学运算一样将简单函数结合，形成更复杂的操作，确保代码保持清晰和模块化。
延迟执行 将副作用推迟到明确需要时再发生，从而增强了函数的纯净性，也为使用高级工具铺平了道路。

通过函数式编程的思维方式，我们可以减少程序中的副作用，利用高阶工具更高效地解决实际问题。虽然 FP 可能起初显得抽象，但它的原则和实践是提升代码质量和开发效率的有力武器。

到这里，你已经掌握了一些函数式编程的基础知识，可以开始尝试实际应用了！接下来的篇章将深入探讨更棘手的概念，如控制流、异常处理和异步编程。

尽管他们都是编程范式, 但严格意义上来说站在函数式对立面的是命令式(也就是绝大多数人写的代码形式),这点向上可以追溯到 $λ$ 演算与图灵机 ↩︎

什么是函数式编程? ​

前提: 一等公民函数 ​

核心概念: 纯函数 ​

重要工具: 柯里化 ​

重要工具: 组合 ​

技巧: 延迟执行 ​

总结 ​