public
Last active

Naive bijective function in Haskell. http://stackoverflow.com/questions/742013

  • Download Gist
Alphabet.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
module Alphabet (
Alphabet,
encodeWithAlphabet,
decodeFromAlphabet
) where
 
import Prelude
import Data.List(elemIndex, mapAccumR)
import Data.Maybe(fromMaybe)
 
-- Alias for clearer type signatures.
type Alphabet = String
 
-- Use an Alphabet to convert a base 10 integer to a string in an arbitrary base.
encodeWithAlphabet :: Alphabet -> Int -> String
encodeWithAlphabet a 0 = [head a]
encodeWithAlphabet a i = rest ++ [digit] where
base = length a
digit = a !! (i `mod` base)
remainder = i `div` base
rest = if remainder > 0
then encodeWithAlphabet a remainder
else ""
 
-- Use an Alphabet to decode a string into a base 10 integer. Doesn't handle inputs
-- that contain characters not in the alphabet.
decodeFromAlphabet :: Alphabet -> String -> Int
decodeFromAlphabet a = sum . snd . mapAccumR changeBase 0 where
base = length a
changeBase index element = (index+1, val element * base^index)
val element = fromMaybe 0 (elemIndex element a)
Main.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12
module Main where
 
import Alphabet
 
-- A base 62 alphabet
a :: Alphabet
a = ['0'..'9'] ++ ['a'..'z'] ++ ['A'..'Z']
 
-- Print some examples
main = do
print $ map (encodeWithAlphabet a) [1, 15, 1000]
print $ map (decodeFromAlphabet a) ["01", "Z", "a5b"]

GHC warns me that is it inferring an Integral type restriction in the arguments of changeBase, but I didn't want to add a type signature and ugly-up the where clause. Any suggestions? I guess I could always create a separate function...

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.