Skip to content

Instantly share code, notes, and snippets.

@crabmusket
Last active April 20, 2020 12:02
Show Gist options
  • Save crabmusket/4626401 to your computer and use it in GitHub Desktop.
Save crabmusket/4626401 to your computer and use it in GitHub Desktop.
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
Copy link
Author

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

@Icelandjack
Copy link

I recommend adding signatures to your where clauses

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