Haskell Quiz/Goedel/Solution Dolio
Latest revision as of 22:51, 11 February 2008
Encoding is quite simple in Haskell, as it's simply combining the stream of characters with a stream of primes in the right way. Extracting a message from the encoded number is somewhat more cumbersome, especially if one wants to implement the somewhat more efficient factoring discussed in the ruby quiz writeup. However, once such operations are defined for a single number, retrieving a stream is just an unfoldr away.
module Main (main) where import Control.Arrow import Data.Char import Data.List import System.Environment primes :: [Integer] primes = 2 : sieve [3,5..] where sieve (x:xs) = x : sieve (filter (\n -> n `mod` x /= 0) xs) goedel :: String -> Integer goedel = product . zipWith (^) primes . map ord letter :: ([Integer], Integer) -> Maybe (Char, ([Integer], Integer)) letter (_, 1) = Nothing letter (, _) = Nothing letter (p:ps,n) = Just (chr k, (ps, n')) where (n', k) = extract p n extract :: Integer -> Integer -> (Integer, Int) extract p n = foldl' extract' (n,0) eps where eps = map (id &&& (p^)) [64,32,16,8,4,2,1] extract' (n,s) (k,pp) | m /= 0 = (n,s) | otherwise = (d,s + k) where (d,m) = n `divMod` pp ungoedel :: Integer -> String ungoedel = unfoldr letter . (,) primes main = do (mode:_) <- getArgs case mode of 'e':_ -> interact $ show . goedel 'd':_ -> interact $ ungoedel . read _ -> putStrLn "Unrecognized mode. 'e' for encode, 'd' for decode."