Instantly share code, notes, and snippets.

What would you like to do?
Naive bijective function in Haskell.
module Alphabet (
) 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)
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"]

This comment has been minimized.

Copy link
Owner Author

crabmusket commented Jan 24, 2013

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...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment