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

Cariecaries

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.

Bertrambertrand

I'm having trouble defining turn as a function. If I say let turn = map reverse . transpose and run :t turn it gives me turn :: [[a]] -> [[a]]. When I use that as the type signature for turn in a function definition file, I get the following error: Couldn't match expected type [[a]] with actual type a0 -> c0 – Cariecaries

I can't diagnose exactly without seeing the code, but that message looks as though somewhere you're passing a function to turn. Something like turn turn or whatever. Can you post the exact problematic part somewhere? – Bertrambertrand

Taking your suggestion, turn = map reverse . transpose, which does work when passed a list of lists in the interpreter. Here's how I tried to define that as a function: turn :: [[a]] -> [[a]] turn xs = map reverse xs . transpose xs. This gives me the type error as shown in my previous comment. – Cariecaries

Ah, no. That's the wrong way to define it. You can define it point-free, turn = map reverse . transpose, or with argument, but then it would be turn xs = map reverse (transpose xs). In what you have, the first argument to the composition operator (.) is map reverse xs - which is a list of lists, has type [[a]], and so the second part, transpose xs, but (.) expects a function for both its arguments. – Bertrambertrand

So when I defined it point-free, I left off the function's type signature completely and it works. Is it bad practice not to include a type signature? Or does it not have a corresponding "correct" type signature since I've defined it this way? – Cariecaries

In this case, the signature makes no difference as far as the compiler is concerned, whether you define turn point-free or point-full. It's good practice to have a type signature on at least all exported entities, but ultimately, that's your own choice. I've left off the signature here out of pure laziness [ha, how fitting]. – Bertrambertrand

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"]]

Bereave

Or even: data Quilt a = Quilt { topLeft :: a, topRight :: a, bottomLeft :: a, bottomRight :: a } – Denude

@Denude True, but that won't generalise to when he wants to sew atoms together (although lists of lists probably won't either), and I'm tired and haven't got the energy to explain why he wants to do it that way (or even find a pre-written explanation somewhere). – Bereave