4
\$\begingroup\$

This program was inspired by a Code Golf challenge that I wanted to do properly. It simply converts oOo to Brainfuck and vice-versa.

The oOo language basically uses UPPER / lower case information in groups of 3 to encode a Brainfuck program. For further info see the Esolang wiki page of oOo.

The main problem with this code is that I feel like there is repetition in the encode / decode functions because they seem to contain similar type of information. I am also worried that I did not declare any types as Haskell is type-centric.

import qualified Data.Char as C
import qualified Data.List.Split as L
import qualified Test.QuickCheck as Q
import qualified Test.HUnit as T

oToBrain :: String -> String
oToBrain = map chunkToBrain . L.chunksOf 3 . filter isAlphabetic

brainToO :: String -> String
brainToO = concatMap singleCharToO

singleCharToO :: Char -> String
singleCharToO x = case x of
  '>' -> "ooo"
  '<' -> "ooO"
  '[' -> "oOo"
  ']' -> "oOO"
  '-' -> "Ooo"
  '+' -> "OoO"
  '.' -> "OOo"
  ',' -> "OOO"
  _ -> ""

isAlphabetic :: Char -> Bool
isAlphabetic = (`elem` ['a'..'z']) . C.toLower

chunkToBrain :: String -> Char
chunkToBrain [a, b, c] = case  (C.isUpper a, C.isUpper b, C.isUpper c) of
  (False, False, False) -> '>'
  (False, False, True ) -> '<'
  (False, True,  False) -> '['
  (False, True,  True ) -> ']'
  (True,  False, False) -> '-'
  (True,  False, True ) -> '+'
  (True,  True,  False) -> '.'
  (True,  True,  True ) -> ','
chunkToBrain _ = error "`oOo` chunks can only be 3 chars long" 

brainChars :: Q.Gen String
brainChars = Q.listOf (Q.elements "<>[]+-.,")

doubleConversionIsId :: Q.Property
doubleConversionIsId = Q.forAll brainChars $ \x -> x == (oToBrain . brainToO) x

main = do
  T.assertEqual "Wiki example" ",[>,]<[.<]+" (oToBrain "PROgRam reVERsES giVeN iNPut sEqUENcE")
  Q.quickCheck doubleConversionIsId
\$\endgroup\$
3
  • \$\begingroup\$ Nice of you to post here rather than some other site. \$\endgroup\$ Feb 29 '16 at 1:05
  • \$\begingroup\$ @200_success Well, I had not intention to golf it, so here I am. \$\endgroup\$
    – Caridorc
    Feb 29 '16 at 6:41
  • \$\begingroup\$ found some time to edit my answer \$\endgroup\$ Mar 1 '16 at 0:33
2
\$\begingroup\$
import qualified Data.Char as C
import qualified Data.List.Split as L
import qualified Test.QuickCheck as Q
import qualified Test.HUnit as T

The qualified import here is good, but your module header is missing. Since there is no documentation you don't want to export some functions, for example the partial chunkToBrain.

oToBrain :: String -> String
oToBrain = map chunkToBrain . L.chunksOf 3 . filter isAlphabetic

While this might seem correct, the combination of chunkToBrain and L.chunksOf doesn't end well. According to esolangs, oOo code may have a non-divisible number of letters. The remaining ones are discarded. More on that later on chunkToBrain.

brainToO is fine, but isAlphabetic isn't, as elem ['a'..'z'] is C.isAsciiLower:

isAlphabetic = C.isAsciiLower . C.toLower

We will now take a look at your source of duplication, singleCharToO and chunkToBrain. Both suffer from somewhat the same problem: you need to define the map from Brainfuck instructions to oOo instructions and vice-versa. So let's define them:

oOoCode :: [String]
oOoCode = ["ooo", "ooO", "oOo", "oOO", "Ooo", "OoO", "OOo", "OOO"]

bfCode :: [Char]
bfCode  = [  '>',   '<',   '[',   ']',   '-',   '+',   '.',   ',']

bf2oOo :: [(Char, String)]
bf2oOo = zip bfCode oOoCode

oOo2bf :: [(String, Char)]
oOo2bf = zip oOoCode bfCode 

Now singleCharToO is

singleCharToO x = fromMaybe "" (lookup x bf2oOo)

where fromMaybe is from Data.Maybe. You can use maybe "" id instead if you don't want to import another module.

Now to chunkToBrain. We will write a single helper beforehand:

toO :: Char -> Char
toO x = if C.isUpper x then 'O' else 'o'

I think you can already guess what happens next:

chunkToBrain :: String -> Maybe Char
chunkToBrain xs = lookup xs oOo2bf

You can of course use other data structures with better asymptotic complexity, but since there are only \$2^3\$ instructions this might be an overkill and should be benchmarked.

But wait a minute: the return type has changed. That's because the text is allowed to have superflous characters. "oOoOO" and "oOo" are the same programs in oOo. This leads to a slight change in oToBrain:

oToBrain = mapMaybe chunkToBrain . L.chunksOf 3 . filter isAlphabetic

Where mapMaybe is again a function from Data.Maybe, that discards Nothing from the list. This version of oToBrain has the right semantics, it doesn't throw an error.

Last but not least, your tests are sufficient for this code, although you should include tests that have oOo programs with a length that's not divisible by three.


I am also worried that I did not declare any types as Haskell is type-centric.

At this point, we're slowly drifting out of the simple exercise and completely into parsing, pretty printing and (possibly) interpretation. What's a fitting data type for your code? No, let's have a look at the greater picture. What's a fitting data type for a Brainfuck or oOo program?

type Program = [Instruction]
data Instruction = IncVal | DecVal
                 | IncPos | DecPos
                 | Put    | Get
                 | Repeat Program

You'll notice that this will only allow syntactic correct programs, e.g. those that have the right pairings of [ and ]. You can use StartRepeat and EndRepeat instead, but that could make evaluation tricky.

You can then define two parsers:

-- or any other type with an erroneous state    
oOoParser :: String -> Either String Program 
bfParser  :: String -> Either String Program 

Getting code again can be done similar to your previous code, although you need to apply the codegen recursively for Repeat.

toBF  :: Program -> String
tooOo :: Program -> String

The conversions can be defined in terms of the other four:

bf2oOo, oOo2bf :: String -> Either String String
bf2oOo = fmap toBF . oOoParser
oOo2bf = fmap tooOo . bfParser

This approach also allows you to define your own evaluation function without worrying about the loops:

eval :: Program -> String -> String
eval prog input = ...

But that's out of scope of this answer. Note that eval gets harder if you don't use the recursive Repeat variant, but parsing gets easier (and vice-versa).

\$\endgroup\$
1
\$\begingroup\$

First of all - your solution is quite readable, and you have already pointed out the features it lacks: types and repeated code.

I chose to put this in a library/module to show that if you want to hide certain pieces of your implementation this would be the way to go.

module Languages ( Brainfuck
                 , OoO
                 , mkBrainFuck
                 , mkOoO
                 , encode
                 , decode)
                 where

both types Brainfuck and OoO are just synonyms one for String, the other for [String], I chose the latter to have triplets of characters as the basic encoding entity in OoO. But with the constructors hidden the user of this library doesn't even have to know about this, for him/her this is just something "like a String", as it can be created from a String by using mk....

This also provides a basic type of documentatation - which would be automatically produced by haddock (the documentation tool).

import Data.List.Split as L
import Data.Char (isLower,isLetter)
import qualified Data.Map.Lazy as M
import Data.Maybe (fromMaybe)

newtype Brainfuck = Brainfuck String deriving (Show, Eq)
newtype OoO = OoO [String] deriving (Eq)
instance Show OoO where
    show (OoO strs) = unwords strs

this handcrafted Show instance just joins the triplets with a space for better readability.

type OoOExp = String
type BrainfuckExp = Char

oooExps :: [OoOExp]
oooExps = [ "ooo", "ooO", "oOo", "oOO", "Ooo", "OoO", "OOo", "OOO"]

bfExps :: [BrainfuckExp]
bfExps = ['>', '<', '[', ']', '-', '+', '.', ',']

these two lists will be used as the "translation table" and for sanity checks in the "smart" constructors.

encode :: OoO -> Brainfuck
encode (OoO o)= Brainfuck $ map convert o
  where msg = "Error: encountered invalid OoO expression: "
        convert :: OoOExp -> BrainfuckExp
        convert x = fromMaybe (error $ msg ++ show x) $
                             M.lookup x table
        table = M.fromList $ zip oooExps bfExps

In my opinion encode is a better name than oToBrain because on the one side it captures its task in a simple word and the type says what it encodes.

The encoding itself is rather straightforward, what might be a bit interesting to the newcomer is the convert function - we use a lookup table of Map OoOExp BrainfuckExp - which is the functional equivalent of a "hashmap" or associative array. Note that this lookup yields a Maybe value as the searched expression (potentially) can't be found.

I still chose to throw an error because I take care by construction that no invalid OoO are possible input values.

decode :: Brainfuck -> OoO
decode (Brainfuck bf )= OoO $ map convert bf
  where msg = "Error: encountered invalid Brainfuck expression: "
        convert :: BrainfuckExp -> OoOExp
        convert x = fromMaybe (error $ msg ++ show x) $
                              M.lookup x table
        table = M.fromList $ zip bfExps oooExps

decode is just the same thing in reverse, which is still a duplicate code, one could abstract this a bit further by introducing a typeclass for convertible classes. I chose to just reverse the arguments for the lookup table and changing the error message accordingly.

mk... are the heart of this piece - they construct types from Strings in a "smart" way, i.e. for mkOoO it checks if the chunks have proper size, getting rid of non letter characters and normalizing letters to 'o's and 'O's, and for mkBrainFuck we check just for the elements of the String being one of the valid characters.

Both functions yield a Nothing in the case of failure and Just value in the case of success, which can then be used with fmap or <$> to use encode/decode for conversion.

In a real world example I would use a proper parser like parsec which makes better error messages.

mkOoO :: String -> Maybe OoO
--here I would really use a parser to get rid of such things as comments
mkOoO str = checkOoOs $ chunksOf 3 $ [if isLower x then 'o' else 'O'| x <- str,isLetter x]
  where checkOoOs ooos = if all (`elem` oooExps) ooos
                            then Just $ OoO ooos
                            else Nothing

mkBrainFuck :: String -> Maybe Brainfuck
--here I would really use a parser to get rid of such things as comments
mkBrainFuck str = if all (`elem` bfExps) str
                     then Just $ Brainfuck str
                     else Nothing
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.