Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Naive bijective function in Haskell. http://stackoverflow.com/questions/742013
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)
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"]
@crabmusket

This comment has been minimized.

Copy link
Owner Author

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
You can’t perform that action at this time.