拉维·塞西(Ravi Sethi)在哈斯克尔(Haskell)中的小被子语言

Question

我正在尝试在Haskell中实现Ravi Sethi的Little Quilt语言。Sethi的小被子的概览可以在这里看到: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 
#@
## 

当我在原子a0上调用turn，并打印生成的原子时，我最终得到以下结果(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

根据概述，转弯时还需要旋转符号，''变成'/'，反之亦然，'-'变成'|'，反之亦然。这可以通过将turnChar :: Char -> Char函数映射到所有行来实现。

Answer 2

下面是一个例子:

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

显示方式如下:

AB
CD

这里的问题是，旋转(一维)列表的自然方式(将元素从一端弹出并将其推到另一端)不是旋转2x2正方形的方式。

我建议使用不同的数据结构来表示原子。例如，你可以将一个原子表示为一个列表的列表:

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