哈斯克尔函数的理论定义是什么



我想看看,从基础的角度来看,Haskell中所谓的函数是什么。

看,绝对地,有些"事物"是联想的,具有恒等函数,理论上这就足够了。

但是每个人都试图说服我,这不是定义函数的方式。函数被定义为(他们说(来自两个集合(域和codoman(的一组元素对,满足某些条件。这意味着函数只是一个集合。你不能在不是集合的东西上定义函数。

如果我们把这种方法应用到Haskell身上,我看到的是Hask类别只是Sets的一个子类别,对我来说,这看起来很奇怪。

我宁愿扩展函数的概念,以应用于我们在 Haskell 中拥有的内容。

在评论中,这个问题是切线的,但不是很深入。我想听到一个明确的说法,比如"但实际上它们都是集合",或者"不,我们与集合论无关"。

有什么想法吗?考虑?

这是一个非常复杂的话题。为了保持简单易懂,我们经常偷工减料,经常"撒谎"。

像所有编程语言一样,Haskell有自己的语法和评估规则(操作语义(。但是,仅从操作角度考虑编程语言可能会非常有限和繁琐。当我们调用一个factorial函数时,我们不关心它是如何实现的,也不关心提供其结果所需的确切评估步骤数。

为了克服这种指称语义,提出了语法,在一些"数学"模型中逐段解释语法。许多不同的程序(句法表达式(可能映射到相同的解释("语义"(。

据我所知,整个Haskell语言的指称语义从未被定义过。不过,也有Haskell碎片的模型。这些模型通常是类别。

以下是一些示例。

如果我们(非常!(将Haskell限制在一个终止的,简单类型的核心,那么我们所需要的只是一个(双(笛卡尔闭合范畴,集合的范畴就足够了,它的乘积,共积和指数。

但是,Haskell不是终止的,并且具有一般递归,因此我们需要固定点。通常,这可以通过移至完全部分订单类别(通常介于omega-CPO或DCPO之间(来解决。

然后我们需要类型级的不动点,所以我们需要考虑一个具有初始 F 代数的类别(至少对于行为良好的函子 F(。这严重地使事情变得更加复杂。

我们还没有添加多态性!这尤其棘手,因为雷诺兹证明了多态性不能被集合天真地建模("多态性不是集合论"是主要的参考论文(。因此,我们现在有PER模型和相干模型(都是类别(,作为为多态性提供语义的一些尝试。

然后我们需要类型类,GADT,更高的等级,更高的种类,...

在实践中,我们不需要这种程度的复杂性。在编程时,我们通常处理有限数量的功能,所以我们对自己"撒谎",经常假装一切都像一个集合,或者足够接近。然后,如果真的需要,我们会重新增加复杂性。