Programming Praxis – Fractran

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