Haskell 中的无限（最终周期性）HList

Question

假设我有一个无限的动作序列，每个动作 returns 都是某种类型的结果。类似于：

newtype Stream a = Stream (IO (a, Stream a))

但是 a 随着时间的推移而变化。我想强烈输入这个序列。显然对于任意无限类型序列和天真的方法没有意义：

data HStream :: [u] -> * where Cons :: Proxy x -> HStream xs -> HStream (x ': xs)

infiniteInt = Cons (Proxy :: Proxy Int) infiniteInt

会导致无限类型，Haskell的类型系统不支持。但是我不认为最终周期性的 HList 有什么问题（即这样的类型序列将从某个点重复自身：[Bool, Int, Int, Sting, Int, Sting, Int, Sting ... ]）。而且我还认为，如果我们有一些强规范化的方法来描述无限类型，或者有一些方法来提供无限类型相等性的证据，可以在有限的步骤中检查，那么应该可以对具有这种无限类型的程序进行类型检查。

有谁知道如何在 Haskell 中表示和使用这些类型？现在让我们从无限 finally-periodic hlist 开始，但如果有人知道如何将它泛化为更广泛的 class 无限元组以及泛化限制所在，我也会很感激。

Answer 1

用这个很酷的技巧使 HLists 无限且周期性！

将元素添加到周期性异构流时，不要扩展索引它的类型列表。旋转它。

type family Append x xs where
    Append x '[] = '[x]
    Append x (y ': xs) = y ': Append x xs

infixr 5 :::
data HStream as where
    (:::) :: { headHS :: a, tailHS :: HStream (Append a as) } -> HStream (a ': as)

myHStream :: HStream '[Char, Bool, Int]
myHStream = 'c' ::: True ::: 3 ::: 'x' ::: False ::: -5 ::: myHStream

Answer 2

一个通用选项是从对所有元素的类型进行编码的 HList 切换到类型对齐的列表（或者更一般地说，类型对齐的序列），它只确保沿有效路径转换。

data TAList c x z where
  Nil :: TAList c x x
  Cons :: c x y -> TAList c y z -> TAList c x z

因此，您可以谨慎地对转换进行编码，为 c 使用可能性较大的 GADT，并为 x 和 z 使用您选择的适当类型。无限类型对齐列表没有问题，因为它们在最终类型参数中是多态的。

您可以使用 McBride 风格的索引方案而不是 Atkey 方案来获得更大的灵活性，但代价是更复杂。

Haskell 中的无限（最终周期性）HList

Infinite (finally-periodic) HList in Haskell

haskell

types

dependent-type

hlist