haskell - Haskell 中的幻像类型

Question

这是我的问题的简化版本。

我有一个递归数据结构(Stream1)。当我引入幻像类型(Stream a)时，递归描述(即 t1)不再起作用。另一方面，t2 通过创建无限结构来正常工作，因为它直接使用 Stream1。我需要使用构造函数 preI，例如在 t1 中。我缺少什么？我需要 t1 表现得像 t2 - 也就是说，返回一个无限流。

data Stream a = Stream Stream1
  deriving (Eq, Show)

data Stream1 = PreI Integer Stream1
  deriving (Eq, Show)

preI :: Integer -> Stream Int -> Stream Int
preI n (Stream s) = Stream (PreI n s)

t1 :: Stream Int
t1 = let x = preI 0 x
     in x

t2 :: Stream Int
t2 = let x = PreI 0 x
     in Stream x

Answer 1

preI :: Integer -> Stream Int -> Stream Int
preI n (Stream s) = ...
    -- ^^^^^^^^^^

此模式匹配会在生成任何输出之前强制使用参数。对于流来说，这很糟糕，因为它将最小固定点保持在底部(非终止)而不是无限流。

您可以尝试使用惰性/无可辩驳的模式匹配来代替:

preI :: Integer -> Stream Int -> Stream Int
preI n ~(Stream s) = Stream (PreI n s)
    -- ^

这本质上意味着:

preI :: Integer -> Stream Int -> Stream Int
preI n z = Stream (PreI n s)
    where s = case z of Stream x -> x

它首先在输出中生成Stream, PreI，然后才开始解包其输入(这在使用s时发生)。

或者，更好的是，将 Stream 从 data 更改为 newtype:这样，模式匹配将始终是懒惰的。事实上，使用 newtype 我们不再在运行时进行任何包装，并且模式匹配实际上是一个无操作。