在Haskell中使用元组定义递归数据类型

Question

我在Haskell中定义新的数据类型时遇到了麻烦.

我正在尝试创建一个数据类型NumPair,它将是一个包含两个整数或整数和另一个整数的元组NumPair.

例如,(2, 2), (0, 5), (1, (2, 3)) and (0, (4, (3, 121)))一切都应该有效NumPairs.

这是我为了尝试这样做而编写的代码:

data NumPair = (Int, Int) | (Int, NumPair) deriving (Eq, Show)

有人可以解释为什么这不起作用,我应该做什么呢,拜托？

Answer 1

您需要为每个替代添加构造函数名称:

data NumPair = Pair (Int, Int) | More (Int, NumPair) deriving (Eq, Show)

这些构造函数名称可以让您在数据类型上进行模式匹配,如下所示:

f :: NumPair -> A
f (Pair (x, y )) = ...
f (More (x, np)) = ...

然后,您可以使用构造函数构建一个值(这就是它们被称为构造函数的原因):

myNumPair :: NumPair
myNumPair = More (1, More (2, Pair (3, 4)))

还有另外两种方法可以改善您的类型.Haskell构造函数内置了对多个字段的支持,因此您可以直接在构造函数中列出值,而不是使用元组,如下所示:

data NumPair = Pair Int Int | More Int NumPair deriving (Eq, Show)

另一种可以改进的方法是识别您刚刚为非空列表编写了类型.非空列表的最佳实现位于包中,您可以在此处找到Data.List.NonEmpty该semigroups包.

然后你的类型变成:

type NumPair = NonEmpty Int

...而且你可以在非空列表中获得一堆免费的模块功能.

编辑:nm让我注意到你可能想要的是:

data NumPair = Pair (Int, Int) | More ((Int, Int), NumPair)

......相当于:

type NumPair = NonEmpty (Int, Int)

不同之处在于后者允许您追加整数对,其中前一个跟随您的问题的类型只允许您追加整数.

Answer 2

你想要的是一个“真正的联合”类型，它在 Haskell 中不存在。Haskell 只提供标记联合，程序员必须在联合中附加附加信息到所有数据。使用真正的联合与标记联合需要权衡；我不会试图以一种或另一种方式向您推销。但是，您可以通过使用提供真正联合类型的语言（例如 Typed Racket）完全根据需要定义类型。

#lang typed/racket

(define-type Num-Pair
  (Rec R
    (U (Pair Integer Integer)
       (Pair Integer R))))

(: foo Num-Pair)
(define foo '(0 . (4 . (3 . 121))))