Posts Tagged ‘fractran’

Programming Praxis – Fractran

July 6, 2012

In today’s Programming Praxis exercise, our goal is to write an interpreter for the esotreric programming language Fractran and use it to execute a program that generates prime numbers. Let’s get started, shall we?

A quick import:

import Data.List

The fractran interpreter itself is pretty simple. We use tuples to represent the fractions rather than Ratios since this made for slightly more elegant code. Unfortunately the Prelude doesn’t have a function to swap the values of a tuple, or I could’ve use divMod rather than having to repeat the multiplication.

fractran :: [(Integer, Integer)] -> Integer -> [Integer]
fractran xs = unfoldr (\m -> fmap ((,) m) . lookup 0 $
    map (\(n,d) -> (mod (m*n) d, div (m*n) d)) xs)

Since we’re using tuples, we represent the primegame program as a zip.

primegame :: [(Integer, Integer)]
primegame = zip [17,78,19,23,29,77,95,77, 1,11,13,15,15,55]
                [91,85,51,38,33,29,23,19,17,13,11,14, 2, 1]

Finding the primes is a matter of finding the terms in the output of fractran primegame 2 that are powers of two.

primes :: [(Integer, Integer)]
primes = [(i,e) | (i,n) <- zip [1..] $ fractran primegame 2
                , let e = round $ log (fromIntegral n) / log 2, 2^e == n]

A test to see if everything is working properly:

main :: IO ()
main = mapM_ print $ take 26 primes