Generating an unique ID from two values
What would be an idiomatic way of generating an unique number (say, a 64bit unsigned int) from two values, in such a way that the input values (also numbers of the same type) could be regenerated from the number, as a Haskell function?
On C/C++ I would probably use something like
result = (((value1) << BITS) + ((value2) & ((1 << BITS) - 1)))
and, accordingly,
value1 = (result >> BITS)
and
value2 = (result & ((1 << BITS) - 1))
for regenerating the values, but I don't think I should be trying to use bitwise operations in Haskell.
After consideration, I simply abandoned the idea of using bitwise operations and resorted to Cantor's pairing function:
pair :: (Fractional a) => a -> a -> a
pair x y = (1 / 2) * (x + y) * (x + y + 1) + y
unpair :: (RealFrac a, Floating a) => a -> (a, a)
unpair z = (x, y) where
q = (-1 / 2) + sqrt (1 / 4 + 2 * z)
j = fromInteger (truncate q)
y = z - ((1 / 2) * j * (j + 1))
x = j - y
This is probably the way I should have thought from the beginning. Thank you all very much for helping me to better understand bit operations on Haskell, though.
You can use the exact same way in Haskell. Bitwise operations can be found in Data.Bits and unsigned, fixed-sized integer types in Data.Word . For example:
import Data.Bits
import Data.Word
combine :: Word32 -> Word32 -> Word64
combine a b = (fromIntegral a `shiftL` 32) + fromIntegral b
separate :: Word64 -> (Word32, Word32)
separate w = (fromIntegral $ w `shiftR` 32, fromIntegral $ w .&. 0xffff)
The thing that might trip you up compared to C is that Haskell never converts between different numeric types implicitly, so you need to use fromIntegral to convert between eg 32bit and 64bit unsigned integers.
上一篇: 寻找可重放/有些无状态的PRNG算法
下一篇: 从两个值生成唯一的ID