类型缩减无限循环

Question

我的目标是从术语中删除 ()，如下所示：

(a, b)       -> (a, b)
((), b)      -> b
(a, ((), b)) -> (a, b)
...

这是代码：

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

module Simplify where

import Data.Type.Bool
import Data.Type.Equality

type family Simplify x where
  Simplify (op () x) = Simplify x
  Simplify (op x ()) = Simplify x
  Simplify (op x y)  = If (x == Simplify x && y == Simplify y)
                          (op x y)
                          (Simplify (op (Simplify x) (Simplify y)))
  Simplify x         = x

但是，尝试一下：

:kind! Simplify (String, Int)

...导致类型检查器中的无限循环。我认为 If 类型族应该处理不可约项，但我显然遗漏了一些东西。但是什么？

Answer 1

类型族评估不是懒惰的，因此 If c t f 将评估所有 c、t 和 f。（事实上，类型族评估顺序现在根本没有真正定义。）所以难怪你最终会陷入无限循环 - 你总是评估 Simplify (op (Simplify x) (Simplify y))，即使那是 Simplify (op x y)！

您可以通过将递归和简化分开来避免这种情况，如下所示：

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

module Simplify where

import Data.Type.Bool
import Data.Type.Equality

type family Simplify1 x where
  Simplify1 (op () x) = x
  Simplify1 (op x ()) = x
  Simplify1 (op x y)  = op (Simplify1 x) (Simplify1 y)
  Simplify1 x         = x

type family SimplifyFix x x' where
  SimplifyFix x x  = x
  SimplifyFix x x' = SimplifyFix x' (Simplify1 x')

type Simplify x = SimplifyFix x (Simplify1 x)

想法是：

Simplify1 简化了一步。
SimplifyFix 采用 x 及其一步简化 x'，检查它们是否相等，如果不相等则进行另一步简化（从而找到Simplify1).
Simplify 只是通过调用 Simplify1.

SimplifyFix

由于类型族 模式匹配 是惰性的，SimplifyFix 正确地延迟了求值，防止了无限循环。

确实：

*Simplify> :kind! Simplify (String, Int)
Simplify (String, Int) :: *
= (String, Int)

*Simplify> :kind! Simplify (String, ((), (Int, ())))
Simplify (String, ((), (Int, ()))) :: *
= ([Char], Int)

Answer 2

我想我会提到，鉴于化简具有折叠结构，因此无需构建涉及固定点的复杂解决方案，它一次又一次地重新遍历表达式。

这样就可以了：

{-# LANGUAGE TypeFamilies         #-}
{-# LANGUAGE UndecidableInstances #-}
module Simplify where

type family Simplify x where
  Simplify (op a b) = Op op (Simplify a) (Simplify b)
  Simplify x        = x

type family Op op a b where
  Op op () b = b
  Op op a () = a
  Op op a b  = op a b

类型缩减无限循环

Type reduction infinite loop

haskell

infinite-loop

typechecking

type-families