6

我正在尝试编写一个从文件中读取原始字节的函数，将其“转换”为“普通”类型，然后对其进行排序。

为了做到这一点，我需要告诉排序它应该如何解释二进制数据——即，二进制数据的类型是什么。

为了使其成为“二进制”数据，在“我可以将这些数据视为原始位，因为我从磁盘读取和写入它”的意义上，数据的类型必须是二进制和位。而且，要对其进行排序，它必须是 Ord 的成员。

任何受这些方式约束的类型都应该是可排序的。

作为一个小技巧，为了将类型传递给排序函数，我改为传递该类型的居民。（如果有办法传递类型本身并获得结果，我很想知道。）

{-# LANGUAGE RankNTypes #-}

import Data.Binary.Get
import Data.Binary.Put

type Sortable = forall a. (Bits a, Binary a, Ord a) => a

data SortOpts = SortOpts { maxFiles :: Int
    , maxMemory :: Integer
    , maxThreads :: Int
    , binType    :: Sortable
}

defaultOpts = SortOpts { maxFiles = 128
    , maxMemory = 1000 * 1000 * 1000 * 1000
    , maxThreads = 4
    , binType = 0 :: Word32
};

putBinaryValues :: Binary a => Handle -> [a] -> IO ()
putBinaryValues out vals = do
    let bytes = runPut . mapM_ put $ vals
    BL.hPut out bytes

binaryValues :: (Binary a, Bits a) => a -> Handle -> IO [a]
binaryValues t inf = do 
    size <- hFileSize inf
    let cast = runGet (genericReplicateM (size `div` byteWidth) get)
    cast . BL.fromChunks . (:[]) <$> BS.hGetContents inf
    where genericReplicateM n = sequence . (DL.genericReplicate n)
          byteWidth = fromIntegral $ (bitSize t) `div` 8

但这不会编译。显然，Haskell 坚持认为记录的所有值都是具体类型。至少，这就是我从错误消息中收集到的：

Could not deduce (a ~ Word32)
    from the context (Bits a, Ord a, Binary a)
        bound by a type expected by the context:
             (Bits a, Ord a, Binary a) => a
at ...
    `a' is a rigid type variable bound by
        a type expected by the context: (Bits a, Ord a, Binary a) => a

那么，我怎样才能实现这种概括呢？

编辑：

我想使用记录更新语法来“配置”排序。例如：

configure = defaultOpts -- and exporting that

然后

let myOpts = configure{ binType = 42 :: Word16 }

但这不起作用，我不太明白为什么，除非它只是 NYI。 

Record update for insufficiently polymorphic field: binType :: a
In the expression: configure {binType = words !! 0}
In an equation for `o': o = configure {binType = words !! 0}
In the expression:
  do { inTestHandle <- inTest;
       words <- testRandomWords;
       putBinaryValues inTestHandle $ take 100 words;
       seekBeg inTestHandle;
       .... }

那么，我的客户端代码是否只需将值从 defaultOpts 中复制出来，并在每次想要重新配置排序时创建一个新记录？

4

2 回答 2

8

问题

问题是RankNTypes. 看Sortable，它是一个返回任意值的函数a，其中a是Ord,Bits和的实例Bytes。换句话说，那里不仅有 3 个类的实例，还拥有所有实例。

Word32显然不能这样做，所以试图把它放在那里是错误的。

想一想undefined，undefined不是“某种类型兼容a”，它可以是所有类型。这相当于说

foo :: a
foo = 1

如果你想要一些 vocab:a是普遍量化的，那么调用者选择实现。您想要的是存在量化，被调用者选择具体类型。

可能的修复

所以最简单的补救措施是

data SortOpts a = SortOpts { 
    maxFiles :: Int
    , maxMemory :: Integer
    , maxThreads :: Int
    , binType    :: a
}

并约束a每个功能

 someFun :: (Bits a, Bytes a, Ord a) => SortOpts a -> whatever

为了方便打字，

 class (Ord a, Bytes a, Bits a) => Sortable a where
 instance (Ord a, Bytes a, Bits a) => Sortable a where

否则，您将需要创建一个存在的“拳击”类型。在这里，我使用GADT来做到这一点。

 {-# LANGUAGE GADTs #-}

 data SortBox where
     Sort :: (Bits a, Bytes a, Ord a) => a -> SortBox

然后简单地通过拆箱并对其进行操作来创建Bits、Bytes和的实例。这让您可以将任何类型装箱，然后将其一般用作、或. 它在类型级别是透明的，但在值级别您必须将奇怪的东西装箱。OrdaSortBitsBytesOrd

data SortOpts a = SortOpts { 
    maxFiles :: Int
    , maxMemory :: Integer
    , maxThreads :: Int
    , binType    :: SortBox
}
于 2013-09-03T17:45:57.510 回答
1

您可以ExistentialQuantification在您的SortOpts类型中使用。以下编译：

{-# LANGUAGE ExistentialQuantification #-}

import Data.Bits
import Data.Word
import Data.Binary
import Data.Binary.Get
import Data.Binary.Put

data SortOpts = forall a. (Bits a, Binary a, Ord a) => SortOpts
    { maxFiles   :: Int
    , maxMemory  :: Integer
    , maxThreads :: Int
    , binType    :: a
    }

defaultOpts = SortOpts
    { maxFiles = 128
    , maxMemory = 1000 * 1000 * 1000 * 1000
    , maxThreads = 4
    , binType = 0 :: Word32
    }

但是，请注意，您不能将binType其用作函数，因为它具有类似的类型，exists a. SortOpts -> a并且您不能将存在类型用作返回值。但是，您可以通过模式匹配获取字段值，例如

test :: SortOpts -> ByteString -> ByteString -> Ordering
test (SortOpts{binType=binType}) bsa bsb = compare a b where
    a = runGet get bsa `asTypeOf` binType
    b = runGet get bsb `asTypeOf` binType

binType这使用给定的存在反序列化和比较两个字节串SortOpts。

正如您所注意到的，Haskell 的记录更新语法不支持存在字段，因此您需要执行以下操作来更新binType：

defaultOpts = SortOpts
    { maxFiles = 128
    , maxMemory = 1000 * 1000 * 1000 * 1000
    , maxThreads = 4
    , binType = 0 :: Word32
    }

alternativeOpts = withBinType (0 :: Word16) $ defaultOpts
    { maxFiles = 256 }

withBinType :: (Bits a, Binary a, Ord a) => a -> SortOpts -> SortOpts
withBinType bt (SortOpts{..}) = SortOpts maxFiles maxMemory maxThreads bt

以上用于RecordWildCards使复制记录更容易一些。稍后使用选项记录时，它也是一个方便的扩展。

或者，正如 jozefg 建议的那样，您可以为binType. 你会像这样使用它：

{-# LANGUAGE ExistentialQuantification #-}

data BinType = forall a. (Bits a, Binary a, Ord a) => BinType a

data SortOpts = SortOpts
    { maxFiles   :: Int
    , maxMemory  :: Integer
    , maxThreads :: Int
    , binType    :: BinType
    }

defaultOpts = SortOpts
    { maxFiles = 128
    , maxMemory = 1000 * 1000 * 1000 * 1000
    , maxThreads = 4
    , binType = BinType (0 :: Word32)
    }

alternativeOpts = defaultOpts
    { binType = BinType (0 :: Word16) }

由于SortOpts现在只是一种常规记录类型，因此您可以正常使用所有记录操作。要引用 unwrapped binType，您需要在包装器上进行模式匹配，以便test之前的示例变为 (using RecordWildCards)

test :: SortOpts -> ByteString -> ByteString -> Ordering
test (SortOpts{..}) bsa bsb = case binType of
    BinType bt -> compare a b where
        a = runGet get bsa `asTypeOf` bt
        b = runGet get bsb `asTypeOf` bt

请注意，以上所有内容都假设您有一个特定的用例，您需要能够出于某种原因将确切的类型参数隐藏在存在变量后面。通常，您只需保留类型参数SortOpts并将其限制在使用SortOpts. IE

data SortOpts a = SortOpts
    { maxFiles   :: Int
    , maxMemory  :: Integer
    , maxThreads :: Int
    , binType    :: a
    }

test :: (Bits a, Binary a, Ord a) => SortOpts a -> ByteString -> ByteString -> Ordering
test (SortOpts{..}) bsa bsb = compare a b where
    a = runGet get bsa `asTypeOf` binType
    b = runGet get bsb `asTypeOf` binType

如果需要，您可以使用ConstraintKinds扩展来制作更短的别名，如

{-# LANGUAGE ConstraintKinds #-}

type BinType a = (Bits a, Binary a, Ord a)

test :: BinType a => SortOpts a -> ByteString -> ByteString -> Ordering
于 2013-09-03T18:25:23.887 回答