Haskell:获取一个 Get monad 并返回无限类型的多态性

Question

如果以下内容是基于我的误解，我提前道歉。我在任何地方都找不到我需要的答案。

我正在实现一个从文件中读取序列化对象的程序，整个过程都使用惰性求值。我首先将文件作为单个 Lazy ByteString 读入，然后使用 Get Monad 解析它来解析文件。在文件中，有一个点存储类型描述符，另一个点存储数据。类型描述符告诉我如何解释数据以及它最终具有哪种类型，并且该类型可以采用嵌套形式； Double 或 [[Word8]] 是两种可能性。

现在，我想出的这样做的想法(并且听起来非常优雅)如下:如果方法(解析类型描述符)创建 - 但不运行 - 一个 Get Monad，然后可以运行使用保存数据的 ByteString？

这将需要这样的方法:

parseTypeDescriptor :: Get (Get a)

其中 a 与描述符描述的类型相同(意味着它可以采用嵌套形式)。以下是部分代码:

parseTypeDescriptor :: Get (Get a)
-- first part of the type descriptor is an id (Word8) that implies a type
parseTypeDescriptor = getWord8 >>= go
   where go 0 = return getWord8
         go 1 = return getWord16be
         go 2 = return getWord32be
                 ...
         -- id 5 indicates that the type is an array
         -- this means two more values are coming;
         -- the first indicates the array's length, the second its type
         go 5 = do n      <- getWord8
                   action <- parseTypeDescriptor
                   return $ -- TODO --

'action' 的类型应该是'Get a'。我在 TODO 中需要的是构造一个执行 Action n 次的值，将这些值放入一个数组中，然后在该数组周围放置一个 Get。

示例:如果 action = getWord16be 且 n = 2；那么 TODO 应该等价于:

TODO :: Get [a]
TODO = do x <- getWord16be
          y <- getWord16be
          return [x,y]

我对这一切有 3 个问题:

我不知道 -- TODO -- 的代码能满足我的要求

编译器告诉我根方法(parseTypeDescriptors)不能
返回不止一种类型。如果它返回 Get (Get Word8) 它不能
也返回 Get (Get [Word8])

我不确定在运行顶级 Get 时是否可以避免
它创建的 Gets 也在运行

我开始怀疑这实际上是不可能的，但我希望我错了——我的解释是可以理解的。

Answer 1

你并没有真正返回多态(普遍量化)的东西——事实上你总是返回一个具体类型 Get A ，但它只会在运行时决定它是什么。这称为 existential quantification . Haskell98 没有这样的东西，但你可以用广义代数数据类型来做到这一点:

{-# LANGUAGE GADTs #-}
data GetSomething where
   GetSomething :: Get a -> GetSomething

parseTypeDescriptor :: Get GetSomething
-- first part of the type descriptor is an id (Word8) that implies a type
parseTypeDescriptor = getWord8 >>= go
   where go 0 = return $ GetSomething getWord8
         go 1 = return $ GetSomething getWord16be
         go 2 = return $ GetSomething getWord32be

到目前为止一切都很好...问题是，你可以用 GetSomething 做任何有用的事情。 ，因为无法知道它实际产生的类型(它隐藏在 GADT 中)。有一些方法可以克服这个问题——例如，如果所有解析的类型都属于一个公共(public)类型类，则可以将其添加为约束:

data GetSomething where
   GetSomething :: CommonClass a => Get a -> GetSomething

这样，即使不知道确切的类型，您也可以解析值并对其进行处理。

但是，这可能不是最好的方法:您基本上总是必须在丢失的类型信息之后运行并四处乱窜才能完成工作。在 Haskell 中，存在被认为是一种反模式。

更好的解决方案可能是将类型放在一个清晰的替代数据结构中:

data GetSomething
   = GetW8 (Get Word8)
   | GetW16 (Get Word16)
   | ...
   | GetList [GetSomething]

然后，您可以简单地进行模式匹配以找出您拥有的特定类型，并且由于支持的类型列表是有限的，您可以确保不会因为某个类型实际上不受支持而遇到问题。