5

我一直在对函数式编程概念和想法进行一些简单的阅读。到目前为止,非常好,我已经阅读了三个主要概念:代数结构、类型类和代数数据类型。我对什么是代数数据类型有相当好的理解。我认为总和类型和产品类型相当简单。例如,我可以想象创建一个代数数据类型,比如一个Card由两个枚举类型Suit(具有四个值和符号)和Rank(具有 13 个值和符号)组成的产品类型。

但是,我仍然对试图准确理解代数结构和类型类是什么感到不满。我脑子里只有一个表面层次的画面,但不能完全理解,例如,不同类型的代数结构,如函子、幺半群、单子等。这些到底有什么不同?它们如何在编程环境中使用?类型类与常规类有何不同?谁能至少给我指出一本关于抽象代数和函数式编程的好书的方向?有人建议我学习 Haskell,但我真的需要学习 Haskell 才能理解函数式编程吗?

4

2 回答 2

11

“代数结构”是一个远远超出编程的概念,它属于数学。

想象一下所有可能的数学对象深不可测的深海。每个条纹的数字(自然数、实数p进数......)都在那里,还有诸如字母序列、图形几何图形的对称性以及它们之间所有明确定义的转换和映射之类的东西。还有很多。

我们可以尝试通过指定条件,向这片海域“撒网”,只保留其中的一些实体。就像“事物的集合,其中有一个操作将其中两个事物组合成相同类型的第三个事物,并且该操作是关联的”。我们可以给这些条件起自己的名字,比如“半群”。(因为我们谈论的是高度抽象的东西,所以很难选择一个描述性的名称。)

这忽略了数学“海洋”的许多居民,但描述仍然适合他们中的很多人!许多事物的集合是半群。例如,具有乘法运算的自然数,以及具有连接的非空字母列表,或具有组合的正方形的对称性

您可以使用额外的条件扩展您的描述。就像“一个半群,还有一个元素,它与任何其他元素相结合得到另一个元素,不变”。这限制了符合描述的数学实体的数量,因为您需要更多的数学实体。一些有效的半群会缺少那个“中性元素”。但是很多数学实体仍然会满足扩展描述。如果你不小心,你可以声明条件如此严格,以至于没有任何可能的数学实体能够真正适合它们!在其他时候,您可以非常精确,以至于只有一个实体适合它们。

纯粹使用数学实体的这些描述,仅使用我们需要它们的一般属性,我们可以获得关于它们的意想不到的结果,乍一看并不明显,结果将适用于所有符合描述的实体。将这些发现视为“代码重用”的数学等价物。例如,如果我们知道某些事物的集合是半群,那么我们可以使用二进制取幂来计算指数,而不是繁琐地将事物与自身n时间相结合。但这只是因为半群运算的关联属性才有效。

于 2020-08-30T10:02:42.633 回答
7

你在这里问了很多问题,但我可以尽我所能回答他们:

......不同类型的代数结构,如函子、幺半群、单子等。这些到底有什么不同?它们如何在编程环境中使用?

这是学习 Haskell 时很常见的问题。我不会在这里写另一个答案——无论如何,一个完整的答案相当长——但一个简单的谷歌搜索给出了一些非常好的答案:例如我可以推荐1 2 3

类型类与常规类有何不同?

(通过“常规课程”,我假设您的意思是 OOP 中的课程。)

这是另一个常见的问题。基本上,两者除了名字之外几乎没有任何共同之处。OOP 中的字段方法的组合。通过创建该类的实例来使用类;每个实例都可以在其字段中存储数据,并使用其方法操作该数据。

相比之下,类型类只是函数的集合(通常也称为方法,尽管几乎没有联系)。您可以通过为该类型重新定义该类的每个方法来声明该数据类型的类型类的实例(同样,无连接),之后您可以使用该类型的方法。例如,Eq该类如下所示:

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool

Bool您可以通过实现每个函数来定义该类的实例,例如:

instance Eq Bool where
    True == True   = True
    False == False = True
    _ == _         = False

    p /= q = not (p == q)

谁能至少给我指出一本关于抽象代数和函数式编程的好书的方向?

我必须承认我对此无能为力(无论如何这对 Stack Overflow 来说都是题外话)。

有人建议我学习 Haskell,但我真的需要学习 Haskell 才能理解函数式编程吗?

不,你不知道——你可以从任何函数式语言中学习函数式编程,包括 Lisp(尤其是 Scheme 方言)、OCaml、F#、Elm、Scala 等。Haskell 恰好是一种特别“纯”的函数式编程语言,我会也推荐它,但如果你只是想学习和理解函数式编程,那么其中任何一个都可以。

于 2020-08-30T09:16:21.313 回答