CODEWITHSUNDEEP
algorithmhaskellnumbers
Arets Paeglis
Arets Paeglis

Reputation: 4006

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.

Upvotes: 2

Views: 314

Answers (1)

shang
shang

Reputation: 24822

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 e.g. 32bit and 64bit unsigned integers.

Upvotes: 4

Related Questions