# Difference between revisions of "Haskell Quiz/Goedel/Solution Dolio"

< Haskell Quiz | Goedel

Jump to navigation
Jump to search
Line 1: | Line 1: | ||

− | [[Category:Haskell Quiz |
+ | [[Category:Haskell Quiz solutions|Goedel]] |

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

## 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."
```