Ravi Sethi's Little Quilt Language in Haskell

Question

I'm trying to implement Ravi Sethi's Little Quilt language in Haskell. An overview of Sethi's little quilt can be seen here: http://poj.org/problem?id=3201

Here are the functions that I have so far:

import Data.List.Split

rotate :: Int -> [a] -> [a]
rotate n xs = iterate rot xs !! n 
    where 
        rot xs = last xs : init xs 

turn :: [a] -> [a]
turn x = rotate 2 x

grid :: Int -> [String] -> String
grid n = unlines . map concat . chunksOf n

printAtom :: [String] -> IO() 
printAtom x = putStrLn $ grid 2 x  

I implemented rotate to use in my turn function, as it simply rotates a list n times to the left.

Here is an example atom:

let a0 = ["#", "@", "#", "#"]

To illustrate how atoms are viewed, I will use the printAtom function:

printAtom a0 

#@
## 

When I call turn on atom a0, and print the resulting atom, I end up with the following (turn should represent a 90 degree clockwise turn to the entire atom):

##
#@

which is the expected output for the first turn. This would correspond to the oriented atom a1. A turn on atom a1 should yield:

@#
## 

however, given the constraints of the turn function, it simply returns the atom back to the a0 state. To combat this, I tried to implement a function, newTurn, that uses guards based on a test using chunksOf 2 atom, shown here:

newTurn :: [a] -> [a]
newTurn x
| chunksOf 2 x == [["#", "@"], ["#", "#"]] = rotate 2 x
| chunksOf 2 x == [["#", "#"], ["#", "@"]] = rotate 1 x 
| chunksOf 2 x == [["@", "#"], ["#", "#"]] = rotate 2 x 
| chunksOf 2 x == [["#", "#"], ["@", "#"]] = rotate 1 x 

I'm almost positive I'm not understanding how to use guards, and I absolutely know that I don't quite understand the type constraints put on a function definition. When I try to import the newTurn function into ghci, I'm getting this error:

functions.hs:19:29:
Couldn't match type `a' with `[Char]'
  `a' is a rigid type variable bound by
      the type signature for newTurn :: [a] -> [a] at functions.hs:18:1
In the expression: "#"
In the expression: ["#", "@"]
In the second argument of `(==)', namely `[["#", "@"], ["#", "#"]]'

After that long-winded explanation of my issue, essentially what I need to know is how could I change my turn function to represent an actual 90 degree clockwise turn of an atom? (Note: This is the first project I've tried to tackle in Haskell, so I'm sure my code is pretty messy.)

Answer 1

Let's first focus on the turn. For an atom [a, b, c, d], calling grid 2 on it for printing yields

a b
c d

Turning that 90° clockwise would result in

c a
d b

which comes from the list [c, a, d, b]. So a clockwise turn isn't a cyclic swapping of list elements. If only 2×2 atoms would need to be considered, the natural implementation of turn using a flat list would be

turn [a,b,c,d] = [c,a,d,b]
turn _         = error "Not an atom"

But, according to the overview, things are not that simple, you can sew quilts, so you can get quilts of any dimension m×n where both m and n are even. So using a flat list representation for quilts is not the best idea.

Suppose you represented quilts as a list of lists, each row one list, so for example

[ [a,b,c,d]
, [e,f,g,h] ]

for a 2×4 quilt. Rotating that 90° clockwise yields the 4×2 quilt

[ [e,a]
, [f,b]
, [g,c]
, [h,d] ]

Now, there's nothing in the standard libraries that does that directly, but, in Data.List, we have transpose, which transforms the 2×4 quilt above into

[ [a,e]
, [b,f]
, [c,g]
, [d,h] ]

and we're then halfway there:

turn = map reverse . transpose

According to the overview, when turning, one would also need to rotate symbols, '\' becoems '/' and vice versa, '-' becomes '|' and vice versa. That would be achieved by mapping aturnChar :: Char -> Char function over all rows.

Answer 2

Here is an example atom:

["A", "B", "C", "D"]

And here is how you are displaying it:

AB
CD

The problem here is that the natural way to rotate a (one dimensional) list (pop an element off one end and push it onto the other) is NOT the way to rotate a 2x2 square.

I recommend using a different data structure to represent an atom. e.g. you could represent an atom as a list of lists:

[["A", "B"], ["C", "D"]]