Язык маленького стеганого одеяла Рави Сетхи в Хаскеле

Question

Я пытаюсь реализовать язык Little Quilt Рави Сетхи в Haskell. Обзор маленького стеганого одеяла Сетхи можно увидеть здесь: http://poj.org/problem?id=3201

Вот функции, которые у меня есть до сих пор:

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  

Я реализовал rotate использовать в моем turn функция, так как она просто вращает список n раз влево.

Вот пример атома:

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

Чтобы проиллюстрировать, как выглядят атомы, я буду использовать функцию printAtom:

printAtom a0 

#@
## 

Когда я звоню turn на атоме a0и распечатать полученный атом, я получаю следующее (turn должен представлять поворот на 90 градусов по часовой стрелке на весь атом):

##
#@

который является ожидаемым выходом для первого хода. Это будет соответствовать ориентированному атому a1, Поворот на атом a1 должен дать:

@#
## 

однако, учитывая ограничения turn функция, он просто возвращает атом обратно в a0 государство. Чтобы бороться с этим, я попытался реализовать функцию, newTurn, который использует охрану на основе теста с использованием chunksOf 2 atom, показанный здесь:

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 

Я почти уверен, что не понимаю, как использовать охранники, и я точно знаю, что не совсем понимаю ограничения типов, накладываемые на определение функции. Когда я пытаюсь импортировать newTurn функция в ghci, я получаю эту ошибку:

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 `[["#", "@"], ["#", "#"]]'

После этого многословного объяснения моей проблемы, по сути, мне нужно знать, как я могу изменить свой turn функция для представления фактического поворота атома на 90 градусов по часовой стрелке? (Примечание: это первый проект, который я попытался реализовать в Haskell, поэтому я уверен, что мой код довольно грязный.)

Answer 1

Давайте сначала сосредоточимся на терне. Для атома [a, b, c, d]звонит grid 2 на нем для печати дает

a b
c d

Поворот на 90° по часовой стрелке приведет к

c a
d b

который идет из списка [c, a, d, b], Так что поворот по часовой стрелке не является циклической заменой элементов списка. Если необходимо учитывать только 2×2 атома, естественная реализация turn используя плоский список будет

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

Но, согласно обзору, все не так просто, вы можете шить стеганые одеяла, поэтому вы можете получить стеганые одеяла любого размера m×n где оба m а также n четные Таким образом, использование плоского представления списка для стеганых одеял не лучшая идея.

Предположим, вы представляли стеганые одеяла в виде списка списков, каждая строка в одном списке, например,

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

для 2×4 стегать. Поворот на 90° по часовой стрелке дает 4×2 стегать

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

Теперь нет ничего в стандартных библиотеках, которые делают это напрямую, но, в Data.List, у нас есть transpose, который преобразует 2×4 стеганое одеяло выше в

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

и мы тогда на полпути:

turn = map reverse . transpose

Согласно обзору, при повороте нужно также повернуть символы, '\' becoems '/' и наоборот, '-' становится '|' и наоборот. Это будет достигнуто путем картированияturnChar :: Char -> Char функция по всем строкам.

Answer 2

Вот пример атома:

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

А вот как вы это показываете:

AB
CD

Проблема здесь в том, что естественный способ поворота (одномерного) списка (вытолкнуть элемент с одного конца и вставить его на другой) НЕ является способом поворота квадрата 2x2.

Я рекомендую использовать другую структуру данных для представления атома. например, вы можете представить атом в виде списка списков:

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