如何从数学角度看待高阶函数和 IO 动作？

Question

我试图从第一原则来理解函数式编程，但我仍然停留在纯函数世界和具有状态和副作用的不纯现实世界之间的接口上。从数学的角度来看，

• 什么是返回函数的函数？
• 什么是返回 IO 操作的函数（如 Haskell 的 IO 类型）？

详细说明：在我的理解中，纯函数是从域到共域的映射。最终，它是从计算机内存中的某些值到内存中的某些其他值的映射。在函数式语言中，函数是声明式定义的；即，它们描述了映射，但不描述需要对特定输入值执行的实际计算；后者由编译器来推导。在具有空闲内存的简化设置中，运行时将没有计算；相反，编译器可以在编译时为每个函数创建一个查找表。执行一个纯程序相当于查表。因此，组合函数相当于构建更高维的查找表。当然，拥有计算机的全部意义在于设计出无需逐点查找表即可指定函数的方法 - 但我发现心智模型有助于区分纯函数和效果。但是，我很难将这种心智模型应用于高阶函数：

• 对于将另一个函数作为参数的函数，生成的将值映射到值的一阶函数是什么？是否有它的数学描述（我确定有，但我既不是数学家也不是计算机科学家）。
• 返回函数的函数怎么样？我如何才能在心理上“扁平化”这个构造以再次获得将值映射到值的一阶函数？

现在到令人讨厌的现实世界。与它的交互并不纯粹，但没有它，就没有合理的程序。在我上面的简化心智模型中，分离程序的纯部分和不纯部分意味着每个函数式程序的基础是一层命令式语句，这些语句从现实世界中获取数据，对其应用纯函数（进行查表），以及然后将结果写回现实世界（磁盘、屏幕、网络等）。

在 Haskell 中，这种与现实世界的命令式交互被抽象为IO 操作，编译器根据它们的数据依赖性对它们进行排序。但是，我们不会直接将程序编写为一系列命令式 IO 操作。相反，有些函数会返回 IO 操作（类型为 的函数:: IO a）。但据我所知，这些不可能是真正的功能。这些是什么？如何根据上面概述的心智模型最好地思考它们？

Answer 1

从数学上讲，采用或返回其他函数的函数完全没有问题。从集合S到集合T的函数的标准集合论定义只是：

F ？? T表示f ? ? T和两个条件成立：

1. 如果? S , 那么(s, t) ? f对于某些t，并且
2. 如果两者(s, t) ? f和(s, t') ? f，则t = t'。

我们写f(s) = t作为(s, t) ? f .

所以写S？T只表示一个特定的集合，因此(A ? B) ? C和A ? (B ? C)又只是特定的集合。

当然，为了效率，我们不会将内存中的函数内部表示为这样的输入-输出对集合，但这是一个不错的第一近似值，如果您需要数学直觉，可以使用它。（第二个近似需要更多的工作才能正确设置，因为它使用您可能还没有经历过很多的结构来以谨慎、有原则的方式处理惰性和递归。）

IO 操作有点棘手。您想如何看待它们可能在一定程度上取决于您特定的数学倾向。

数学家的一种劝说可能想将 IO 动作定义为一个归纳集，例如：

• 如果x :: a，那么pure x :: IO a。
• 如果f :: a -> b，那么fmap f :: IO a -> IO b。
• 如果x :: IO a和f :: a -> IO b，那么x >>= f :: IO b。
• putStrLn :: String -> IO ()
• forkIO :: IO a -> IO ThreadId
• ...以及其他一千个基本案例。
• 我们对几个等式进行商数：
  • fmap id = id
  • fmap f . fmap g = fmap (f . g)
  • pure x >>= f = f x
  • x >>= pure . f = fmap f x
  • （还有一个稍微复杂的阅读，只是说这>>=是关联的）

就定义程序的含义而言，这足以指定 IO 系列类型可以包含哪些“值”。您可能会从定义自然数的标准方式中认出这种定义风格：

• 零是自然数。
• 如果n是自然数，则Succ(n)是自然数。

当然，这种定义事物的方式也有一些不太令人满意的地方。比如：任何特定的 IO 操作是什么意思？这个定义中没有任何说明。（尽管请参阅“解决尴尬的小队”以阐明即使您采用这种类型的归纳定义，您也可以说出 IO 操作的含义。）

另一种数学家可能更喜欢这种定义：

IO 操作与代表宇宙当前状态的幻象令牌上的有状态函数同构：

IO a ~= RealWorld -> (RealWorld, a)

这种定义也很吸引人。不过，值得注意的是，要说forkIO这种定义到底有什么用要困难得多。

...或者你可以采用 GHC 定义，在这种情况下IO a，a如果你在封面下挖掘得足够多，那么它就是秘密地。但是，嘘！！不要告诉那些只是想逃避IO和编写IO a -> a函数的没有经验的程序员，因为他们还不了解如何使用IO接口进行编程！