这个GHC类族例子的相关函数怎么写？

Question

在 GHC/Type families 网页上，它有半个入门示例说明了类型族为何有用。

data family XList a
data instance XList Char = XCons !Char !(XList Char) | XNil
data instance XList () = XListUnit !Int

基本上，它表示 Char 的列表可以用 cons 单元格表示。 ()的列表除了长度之外没有其他有用的信息，所以我们可以用长度来表示列表。

太好了。那么这个列表的其余实现呢？ length如何定义，!!或fromList如何定义？

Answer 1

对于 XList Char 可能是：

{-# LANGUAGE TypeFamilies #-}
import Prelude hiding ((!!), length)
import qualified Prelude

class XList' a where
    data family XList a :: *
    fromList :: [a] -> XList a
    length   :: XList a -> Int
    (!!)     :: XList a -> Int -> a

instance XList' Char where
    data XList Char = XCons !Char !(XList Char) | XNil

    fromList []     = XNil
    fromList (x:xs) = XCons x (fromList xs)

    length XNil         = 0
    length (XCons x xs) = 1 + length xs

    XNil         !! _ = error "index error!"
    (XCons x xs) !! 0 = x
    (XCons x xs) !! k = xs !! (k - 1)

然后：

\> let a = fromList "wxyz"
\> :t a
a :: XList Char
\> length a
4
\> a !! 2
'y'

与 XList () 类似：

instance XList' () where
    data XList () = XListUnit !Int

    fromList a = XListUnit $ Prelude.length a
    length (XListUnit n) = n

    (XListUnit n) !! k
        | k < 0 || n <= k = error "index error!"
        | otherwise       = ()

Answer 2

只是一个小小的补充：

您可以将 XList a 保留为非类型类关联的类型族，只需为包含操作的 XList-y 类型添加一个类型类；例如：

{-# LANGUAGE TypeFamilies #-}

-- Original definition from your question
data family XList a
data instance XList Char = XCons !Char !(XList Char) | XNil
data instance XList () = XListUnit !Int

-- New class for XList-y types
class XListy a where
    length :: XList a -> Int
    (!!) :: XList a -> Int -> a
    fromList :: [a] -> XList a

instance XListy () where
    length (XListUnit n) = n
    _ !! _ = ()
    fromList xs = XListUnit $ Prelude.length xs

这个GHC类族例子的相关函数怎么写？

How to write the related functions for this GHC type families example?

haskell

ghc

type-families