在haskell中，如何表示新定义的无限数据

Question

我按以下方式在 Haskell 中定义了一个新的数据类型：

data Pro = P Int Pro | Idle
              deriving Show

然后我定义了一个适用于这种新数据类型的运算符：

(>*>) :: Pro -> Pro -> Pro
Idle        >*>   ps  = ps
P i ps      >*>   qs  = P i (ps >*> qs)

所以，infi r = P r Idle >*> (infi (r+1))可以代表无限数据，如果我在终端输入infi4 1，它会无限打印。

后来才知道这个新的数据类型定义可以修改为：

data Try = T [Int] 
     deriving Show

很像，后面的是一种列表，看起来比较简单。但是当我定义以下无限数据时：

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     T qs    = T (ts ++ qs )

infi2 r = (T [r]) >/> (infi2 r)

并尝试在终端中打印它，结果显示：

Exception: stack overflow

Haskell 的惰性属性似乎不适用于这种新的数据类型。谁能告诉我原因以及如何通过第二种数据类型打印无限数据。

Answer 1

你需要tilda:

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     ~(T qs)    = T (ts ++ qs )

另外你不需要第一个子句，所以(>/>)可以定义为

(>/>) :: Try -> Try -> Try
~(T ts) >/> ~(T qs) = T (ts ++ qs)

(>*>) 的定义是惰性的，因为第二个参数没有模式匹配。

更新

正如@MigMit 所建议的，您可以只使用 newtype，并且您对 (>/>) 的原始定义将起作用。查看 https://wiki.haskell.org/Newtype

的 2 The messy bits 部分

Answer 2

另一个答案是正确的，一个正确的解决方法是使用 ~ 模式（也称为无可辩驳的模式或惰性模式）或新类型，但让我们看看 为什么 ...

这里再次给出您的定义以供参考：

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     T qs    = T (ts ++ qs)

infi2 r = T [r] >/> infi2 r -- I've omitted unnecessary parentheses

现在，如果您调用 infi2 1，则会发生以下减少：

   infi2 1

=    { expanding the definition of infi2 }

   T [1] >/> infi2 1

现在重点来了。我们想减少最外层的功能，即 >/>。但是我们必须决定哪种情况适用。这简单看到第一个没有，因为 T [1] 不匹配 T []。然而，第二种情况要求 >/> 的第二个参数的形状为 T qs，我们有 infi2 1。即使 Try 只有一个构造函数，GHC/Haskell 也不会做出这样的信仰飞跃。相反，它将进一步评估 infi2 1 直到它了解其最外层的构造函数。所以下一个减少步骤是

   T [1] >/> infi2 1

=    { expanding the definition of infi2 }

   T [1] >/> (T [1] >/> infi2 1)

现在我们再次处于完全相同的情况。我们仍然不能减少最外层的 >/> 因为我们不知道正确参数的构造函数；所以我们必须进一步减少它。但是，我们又需要减少右参进一步了解内层>/>:

右参的构造函数

   T [1] >/> (T [1] >/> infi2 1)

=    { expanding the definition of infi2 }

   T [1] >/> (T [1] >/> infi2 1)

=    { expanding the definition of infi2 }

   T [1] >/> (T [1] >/> (T [1] >/> infi2 1))

=    ...

这将无限期地继续，直到内存填满。我们永远无法做出任何真正的进步。

再次回顾最初的定义，（通过一些练习）实际上可以在不进行整个扩展的情况下看到这一点：

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     T qs    = T (ts ++ qs)

infi2 r = T [r] >/> infi2 r

在定义>/>的第二种情况下，我们只产生一个T 之后我们知道两个参数都是T秒。所以在infi2 r中，我们只能在infi2 rreturns之后减少外层的>/>，但那是递归调用...

现在介绍解决此问题的解决方案：

使用新类型

有

newtype Try = T [Int]
  deriving (Show)

而不是 data，T 上的模式匹配变为空操作。新类型保证具有与基础类型相同的运行时表示（此处 [Int]），并且应用构造函数 T 或模式匹配对类型转换有影响，但在运行时没有影响。

因此，一旦我们有

T [1] >/> infi2 1

为了对其中一种情况做出决定，我们现在只看到第一个列表是非空的，所以第一种情况不适用。第二种情况左手边

T ts >/> T qs = ...

假设 T 上的模式匹配是一个 noop 是微不足道的，并且可以立即减少。

使用 `~` 模式

同样，如果我们继续使用data，但是写

T ts >/> ~(T qs) = ...

我们更改 GHC/Haskell 的行为，以实际实现我上面提到的 "leap of faith"。无可辩驳的模式匹配会自动成功，因此它永远不会导致进一步的评估。对于 Try 这样的单构造函数数据类型，这样做基本上是安全的。但是，如果您对多构造函数数据类型进行这种惰性模式匹配，结果发现您匹配的值不是出现在您的模式中的构造函数的值，匹配仍然会成功，并且您会得到一旦您尝试使用模式内部的值，就会出现运行时异常。

显式提取

第三种选择是编写提取函数

unT :: Try -> [Int]
unT (T ts) = ts

然后说

(>/>) :: Try -> Try -> Try
T []    >/>     i       = i 
T ts    >/>     qs      = T (ts ++ unT qs)

这很明显我们不期望第二个参数的任何内容在模式匹配时。这个版本非常符合 ~-pattern-version 将编译成的版本。

总而言之，让我们看看现在的减少量：

   infi2 1

=    { expanding the definition of infi2 }

   T [1] >/> infi2 1

=    { expanding the definition of >/> }

   T ([1] ++ unT (infi2 1))

假设我们要打印结果和完整的归约，让我们从这里继续一点：

   T ([1] ++ unT (infi2 1))

=    { expanding the definition of ++ }

   T (1 : unT (infi2 1))

=    { expanding the definition of infi2 }

   T (1 : unT (T [1] >/> infi2 1))

=    { expanding the definition of >/> }

   T (1 : unT (T ([1] ++ unT (infi2 1))))

=    { expanding the definition of the outer unT }

   T (1 : ([1] ++ unT (infi2 1)))

至此，应该很明显我们确实增量地获得了无限列表。

在haskell中，如何表示新定义的无限数据

in haskell, how to represent infinite data which is newly defined

haskell

types

lazy-evaluation

使用新类型

使用 `~` 模式

显式提取

在haskell中，如何表示新定义的无限数据

in haskell, how to represent infinite data which is newly defined

haskell

types

lazy-evaluation

使用新类型

使用 ~ 模式

显式提取

使用 `~` 模式