Haskell 类型算法：如何访问列表的类型级列表

Question

我正在研究基于单元格的数据库模型的类型级表示，该模型以 Haskell 类型的查询为特征。我在尝试从更复杂的查询类型中提取值时卡住了。

首先让我向您展示有效的代码：

-- a model with datapoints defined by a list of "aspects"
-- every aspect has a "dimension" and a list of dimensional values
type Model = Double  $|$ Aspect "currency" '["eur", "usd"]
                      |$ Aspect "flowtype" '["stock", "flow"]
                      |$ Nil

-- extract the aspects from the query type
class GetAspectsSingle a where
  getAspectsSingle :: Proxy a -> [(Dimension, DimValue)]

instance (KnownSymbol d, KnownSymbol v, GetAspectsSingle as)
      => GetAspectsSingle (Aspect d v |$ as) where
  getAspectsSingle _ = (symbolText (Proxy :: Proxy d),
                        symbolText (Proxy :: Proxy v))
                         : (getAspectsSingle (Proxy :: Proxy as))

instance GetAspectsSingle Nil where
  getAspectsSingle _ = []

-- a dummy for the execution of a type-safe query
-- where CellTypeSingle is a type function that evaluates to the expected type
save :: (MonadIO m, GetAspectsSingle q)
      => Proxy model -> Proxy q -> CellTypeSingle model q -> m ()
-- just print aspects instead of actual query
save Proxy query _ = liftIO . print $ getAspectsSingle query

-- an example query
query :: Proxy (Aspect "currency" "eur" |$ Aspect "flowtype" "stock" |$ Nil)
query = Proxy

test :: IO ()
test = save (Proxy :: Proxy Model) query 3.3

关键思想是类型函数 CellTypeSingle 的计算结果为 Double，因此只有当 3.3 的类型为 Double 时，上述代码才能编译。

我想要查询允许选择多个值（相同类型），如下所示：

query :: Proxy (Aspect "currency" '["eur", "usd"] |$ Aspect "flowtype" '["stock"] |$ Nil)
query = Proxy

在上述情况下，我设法实现了计算结果为 [Double] 的相应类型函数 CellTypeList。但是，为了获得方面，我必须先 "explode" 查询。 IE。上面的查询变成了一个查询列表。这是我试过的。

saveList :: (MonadIO m, GetAspectsList q)
         => Proxy model -> Proxy q -> CellTypeList model q -> m ()
-- just print aspects instead of actual query
save Proxy query _ = liftIO . print $ getAspectsList query

class GetAspectsList query where
  type GetAspectsListType (query :: Type) :: Type
  getAspectsList :: Proxy query -> GetAspectsListType query -> [[(Dimension, DimValue)]]

instance (GetAspectsList as)
      => GetAspectsList (a |$ as) where
  type GetAspectsListType (a |$ as) = GetAspectsListType (ExplodeQuery (a |$ as))
  getAspectsList = ???

现在我卡住了：ExplodeQuery 计算结果为 '[ '[ Aspect "currency" "eur", Aspect "flowtype" "stock" ], '[ Aspect "currency" "usd", Aspect "flowtype" "stock"] ]，这是类型级别的列表列表。

我不知道如何从那里提取维度和维度值。

Answer 1

我不太明白你想做什么，但我会这么说。类型主要用于 class 化值。构建大量类型级信息，使用 Proxy 在值级擦除它，然后尝试使用 classes 恢复它以对类型进行模式匹配导致复杂的代码（如你已经看到了）并且在安全性或简洁性方面并没有真正给你买任何东西。

保持简单。我的建议是更仔细地考虑您的 API 客户会提前知道哪些信息——这是类型级的东西——以及客户想要动态构建的信息。使用类型级别的东西 class 化值级别的东西。

在这种情况下，您的用户会提前知道他们的架构 - 模型的各个维度 - 但他们通常不知道他们将对这些维度的哪些视图正在查询。

这是一个草图，不一定能直接帮助您，但至少应该为您指明正确的方向。请注意我如何使用类型来 class 化值，而不仅仅是编译时数据的无意义位。这允许我使用 class 系统以类型导向的方式生成代码，从而在不牺牲安全性的情况下获得简洁的 API。另外，如果你愿意放弃 TypeOperators 和 PatternSynonyms，这个解决方案完全是 Haskell 98.

图书馆的 API 是这样的：

data Currency = EUR | USD deriving Show
data FlowType = Stock | FlowType deriving Show

-- this class just wraps up knowledge of the type's name.
-- You could generate these instances using Template Haskell
instance Aspect Currency where
    aspectName = const "Currency"
instance Aspect FlowType where
    aspectName = const "FlowType"

-- queries contain a currency and a flowtype
type Model = () :&: Currency :&: FlowType

myQuery :: Q Model
myQuery = () :&: EUR :&: Stock :@ 3.3

用户定义自己的方面类型，如 Currency 和 FlowType，并为每个方面编写 Aspect 的实例。然后他们使用 :&: 将方面组合成更大的类型，使用 I 终止列表。然后，当构建查询时，客户端必须以正确的顺序为各个方面提供值。

这是它的实现方式。使用 :&: 类型组合器构建的模型将自动成为以下 Query class.

的实例

class Query a where
    showQuery :: a -> String

我将使用 :&: 构建的模型表示为嵌套元组。这允许我构建和递归任意大小的元组。 Q 简单地将 Model 与 Double 值配对，而 A 只是方面的标记新类型。

infixl 5 :&:
type (m :&: a) = (m, A a)
pattern m :&: a = (m, A a)

newtype A a = A a

infixl 3 :@
data Q m = m :@ Double

Query 的实例通过嵌套元组的结构递归将查询编译成字符串。（如果我们使用平面元组，我们必须写 lots of instances of Query - 每个元组大小一个 - 尽管它会稍微提高性能，因为解包元组总是 O(1) .)

instance Query a => Query (Q a) where
    showQuery (a :@ x) = showQuery a ++ "@" ++ show x
instance (Query a, Query b) => Query (a, b) where
    showQuery (x, y) = showQuery x ++ ", " ++ showQuery y
instance Query () where
    showQuery = const ""
instance Aspect a => Query (A a) where
    showQuery (A x) = aspectName (proxy x) ++ ": " ++ show x
        where proxy :: a -> Proxy a
              proxy = const Proxy

Aspect class 只是包装了类型名称的静态知识，以便我们可以在编译的字符串中使用它。

class Show c => Aspect c where
    aspectName :: Proxy c -> String

布丁的证明在于吃：

ghci> showQuery myQuery
", Currency: EUR, FlowType: Stock@3.3"  -- the leading comma is fixable. You get the idea

Answer 2

这是一个解决方案，感谢 Kosmikus。

{-# LANGUAGE TypeOperators, DataKinds, PolyKinds, ScopedTypeVariables, TypeInType #-}
{-# LANGUAGE TypeFamilies, FlexibleInstances, GADTs #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-}

module IsList where

import Data.Proxy
import GHC.TypeLits hiding (Nat)
import GHC.Types (Type)

type family Extract (k :: Type) :: Type where
  Extract Symbol = String
  Extract [a]    = [Extract a]

class Extractable (a :: k) where
  extract :: Proxy (a :: k) -> Extract k

instance KnownSymbol a => Extractable (a :: Symbol) where
  extract p = symbolVal p

instance Extractable ('[] :: [a]) where
  extract _ = []

instance (Extractable x, Extractable xs) => Extractable (x ': xs) where
  extract _ = extract (Proxy :: Proxy x) : extract (Proxy :: Proxy xs)

它甚至没有那么复杂，但我没有弄清楚嵌套。此解决方案适用于嵌套到任意深度的列表列表。

type family 应该是 Extractable class 的关联类型族。

Haskell 类型算法：如何访问列表的类型级列表

Haskell type arithmetic: how to access type-level list of lists

haskell

typeclass

ghc

type-level-computation