haskell - 如何为通用向量创建列表同构实例？

Question

给定以下类(class):

class ListIsomorphic l where
    toList   :: l a -> [a]
    fromList :: [a] -> l a

如何使用 Data.Vector.Generic 编写向量类型的实例？这不起作用:

instance (V.Vector v a) => ListIsomorphic v where
    toList   = V.toList
    fromList = V.fromList

给我:

test.hs:31:10:
    Variable ‘a’ occurs more often than in the instance head
      in the constraint: V.Vector v a
    (Use UndecidableInstances to permit this)
    In the instance declaration for ‘ListIsomorphic v’

Answer 1

不要。将所有 v 的实例添加到 Listable 类中，由于实例重叠，使用起来会变得很麻烦。

Vector v a => v 与列表不同构，因为它受到哪些项可以是列表元素的限制。您需要一个捕获此约束的类，例如

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeFamilies #-}

import Data.Constraint

class ConstrainedList l where
    type Elem l a :: Constraint
    toList   :: Elem l a => l a -> [a]
    fromList :: Elem l a => [a] -> l a

我们不会为所有类型 Vector v a => v 添加 ConstrainedList 实例(这会让我们陷入重叠实例领域)，而是只为我们想要的类型定义它。下面将涵盖所有带有 Vector 的类型矢量包中的实例。

import qualified Data.Vector.Primitive as VP
import qualified Data.Vector.Generic as VG

instance ConstrainedList VP.Vector where
    type Elem VP.Vector a = VG.Vector VP.Vector a
    toList   = VG.toList
    fromList = VG.fromList

其他类型的实例

您可以为常规列表 [] 编写一个 ConstrainedList 实例，该实例仅需要其元素为空约束。

instance ConstrainedList [] where
    type Elem [] a = ()
    toList   = id
    fromList = id

任何使用 toList 或 fromList 的地方也需要 Elem l a 实例。

cmap :: (ConstrainedList l, Elem l a, Elem l b) => (a -> b) -> l a -> l b
cmap f = fromList . map f . toList

当我们知道列表和元素的具体类型时，这些函数将很容易使用，而不会受到约束的影响。

cmap (+1) [1,2,3,4]

这里有龙

不要尝试下面的操作。如果您对与列表同构且没有附加约束的事物类感兴趣，只需为其创建另一个类即可。这只是展示了当您将自己逼入绝境时可以做什么:召唤一条龙。

您还可以编写需要证明 ConstrainedList 的元素没有约束的函数。这离 GHC 并不真正支持的 constraints 包和编程风格的领域很远，但是没有足够的 constraints 示例，所以我会离开这里就是这个。

{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}

map' :: forall l a b. (ConstrainedList l, () :=> Elem l a, () :=> Elem l b) =>
                      (a -> b) -> l a -> l b
map' f = case (ins :: () :- Elem l a) of { Sub Dict ->
         case (ins :: () :- Elem l b) of { Sub Dict ->
         fromList . map f . toList
         }}

我们可以通过检查 Elem l a ~ () 来检查 ConstrainedList 是否没有约束，但如果它的约束是用不同的语言编写的，那么这将不起作用方式。

{-# LANGUAGE FlexibleInstances #-}

class Any a
instance Any a

data AList a = AList {getList :: [a]}
    deriving (Show)

instance ConstrainedList AList where
    type Elem AList a = Any a
    toList   = getList
    fromList = AList

() 与 Any a 的类型不同，尽管 () 隐含 Any a。约束包通过将它们具体化为类型类 Class 来捕获这样的关系。和 :=>

{-# LANGUAGE MultiParamTypeClasses #-}

--       class () => Any a
instance Class ()   (Any a) where
    cls = Sub Dict

-- instance ()  => Any a
instance    () :=> Any a where
    ins = Sub Dict

所有这些工作让我们可以轻松地重用函数，而无需在已知具体列表类型时提供所有这些字典。

map'' :: (a -> b) -> AList a -> AList b
map'' = map'