haskell - 如何在 Haskell 中的类型之间建立排序

Question

我需要在 * -> * 之间建立排序类型基于一种类型的每个成员都可以由另一种类型表示。这是同态。

问题是我可以定义 !<=! 的传递性关系，但类型检查器无法弄清楚。也很模糊，Identity !<=! Maybe可以源自 Identity !<=! Maybe或Identity !<=! Identity !<=! Maybe , ... 每个推导都带有 repr 的不同(但等效)定义。 .

因此，我正在寻找其他方法来创建自反和传递关系。

{-# LANGUAGE ScopedTypeVariables, TypeOperators, MultiParamTypeClasses, FlexibleInstances, UndecidableInstances, AllowAmbiguousTypes, OverlappingInstances #-}

import Control.Monad.Identity
import Data.Maybe

class x !<=! y where
  repr :: x a -> y a

instance x !<=! x where
  repr = id

instance Identity !<=! Maybe where
  repr = return . runIdentity

instance Maybe !<=! [] where
  repr = maybeToList

instance (x !<=! y, y !<=! z) => x !<=! z where
  repr = r2 . r1
    where r1 :: x a -> y a
          r1 = repr
          r2 :: y a -> z a
          r2 = repr

注意:我在 GHC 7.8 上尝试过这个。您可能必须删除 AllowAmbiguousTypes .

编辑:我想做类似 repr (Identity 3 :: Identity Int) :: [Int] 的事情

Answer 1

问题是我们无法让 GHC 对实例执行一般图形搜索。在这种特殊情况下，如果 GHC 可以执行最短路径算法，那就更好了，因为我们的函数随着路径中的每个中间表示而变得更慢。

但是，我们可以通过将传出边的数量限制为 1 来使每个图节点上的搜索明确，GHC 可以处理该问题。这意味着每种类型最多有一个直接表示:

{-# LANGUAGE FlexibleInstances, TypeOperators, MultiParamTypeClasses, FunctionalDependencies, UndecidableInstances, OverlappingInstances #-}

import Control.Monad.Identity
import Data.Maybe

class DirectRepr x y | x -> y where
    directRepr :: x a -> y a

我们可以用 DirectRepr 构建一个图表:

instance DirectRepr Identity Maybe where
    directRepr (Identity a) = Just a

instance DirectRepr Maybe [] where
    directRepr = maybeToList

然后用包装类 <= 来遍历它:

class x <= y where
    repr :: x a -> y a

instance x <= x where
    repr = id

instance (DirectRepr x y, y <= z) => x <= z where
    repr = repr . directRepr

main = print (repr (Identity ()) :: [()]) -- [()]

它也适用于循环图，因为当我们遇到 <= 的自反性情况时搜索就会停止。 (感谢OverlappingInstances):

data A a
data B a
data C a

instance DirectRepr A B where directRepr = undefined 
instance DirectRepr B C where directRepr = undefined
instance DirectRepr C A where directRepr = undefined

foo :: A Int
foo = repr (undefined :: B Int)

如果起始类型导致循环，并且循环中没有端点类型，则搜索会陷入困境，并且会出现上下文溢出。这不应该太困扰我们，因为这使得上下文溢出错误等同于普通的“无实例”错误。

bar :: Maybe Int -- context overflow
bar = repr (undefined :: A Int)