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 

#@
## 

当我调用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在所有行上映射函数来实现.