haskell - Haskell 中的递归类型同义词 - 'cycle in type synonym declarations'

Question

我目前正在阅读 CSP Book由 CAR Hoare 编写，并尝试使用 Haskell 实现其早期示例。

本书首先定义了一个进程代数 - 本质上，进程接收事件并返回另一个进程或一个符号(bleep)，表明该进程不参与此事件。 STOP 过程会为任何事件返回 bleep。

这本书建议您在 LISP 中执行此操作，因此我使用了 Racket。 STOP 的定义很简单:

(define (STOP event) 'bleep)

这是一个“自动售货机”过程，它只接受事件 coin 并返回 STOP:

(define (coin-to-stop event)
  (case event
    ['coin STOP]
    [else 'bleep]))

然后我尝试在 Haskell 中实现这些相同的概念。我们没有像 Racket 那样的符号，所以让我们定义 Event:

data Event = Ev String deriving (Eq)

与 Racket 不同，我们不能混淆 'bleep 和进程之间的区别，因此我们将使用 Maybe 来定义进程的类型:

type Process = Event -> Maybe Process

其中Just p对应一个进程，Nothing对应'bleep。

现在我们可以定义STOP进程了:

stop :: Process
stop _ = Nothing

和“自动售货机”流程:

coinToStop :: Process
coinToStop (Ev "coin") = Just stop
coinToStop _           = Nothing

不幸的是，这不能编译，因为你不能有循环类型定义:

Cycle in type synonym declarations:
  src\Csp.hs: type Process = Event -> Maybe Process

我用 newtype 玩了一会儿，但我真的不明白我在那里做什么。

我意识到我可以使用以下方法实现大致等效的解决方案:

data ProcResult = P (Maybe Process)
type Process = Event -> ProcResult

但这看起来很丑陋。

在 Haskell 中表示 Process 概念的正确方法是什么？

Answer 1

Haskell 有三种类型定义:

1. data:定义“成熟的”数据类型。
2. newtype:定义“同构”类型，类似于不透明类型同义词。
3. type:定义透明类型同义词。类似于 C/C++ 中的 typedef。

因此您正在使用 type 并尝试定义递归类型同义词:

type Process = Event -> Maybe Process

好吧，Haskell 中的一个规则是，在任何情况下，当您有一个 type 同义词时，您都可以用它的展开式替换它，并且程序运行相同。 Haskell 将扩展 type 同义词以弄清楚它们代表什么类型。所以当你这样写的时候:

stop :: Process

你要求 Haskell 以这种方式扩展它:

stop :: Event -> Maybe Process
stop :: Event -> Maybe (Event -> Maybe Process)
stop :: Event -> Maybe (Event -> Maybe (Event -> Maybe Process))
     .
     .
     .

长话短说，Haskell 中的 type 同义词根本不允许递归。 newtype 和 data 可以递归，所以你应该在这里使用 newtype。