-- L shapes from top left to top right then down to bottom right
lShaped :: [[a]] -> [[a]]
lShaped = lShaped' . map reverse
-- L shapes from top right backwards to top left then down to bottom left
lShaped' :: [[a]] -> [[a]]
lShaped' [] = []
lShaped' ([]:_) = []
lShaped' (xs:xss) = (reverse xs ++ map head xss) : lShaped' (map tail xss)
我们需要两个基本情况来处理比它们高的矩形 宽并且比高度还宽 - 你的代码缺少一个 这些。
或者,我们可以尝试使用库函数而不是这样做 手动递归。
该函数沿向上倾斜的线将矩形切成两部分。 n 是 上/左部分第一行的长度,或者如果 n 更大 比矩形的宽度你必须把它想象成一个坐标 在定义切割右上角点的矩形之外 行,这样一些完整的行就会出现在之前的上/左部分 我们开始讨论。
slice :: Int -> [[a]] -> ([[a]], [[a]])
slice n xss = unzip (zipWith splitAt [n,n-1 ..] xss)
使用切片可以很好地分割元素的水平和 L 的垂直部分,但垂直部分没有排列成 有用的方法。我们可以再次使用切片,而不是尝试重新排列它们 对矩阵进行转置以使它们进入正确的列表。 最后我们将水平和垂直部分放在一起 zipWith (++)。
We could write initAndLast, but it wouldn't help performance very much because that would still be a lot of work to do for each element of the result.
We really want to be working at the beginning of the lists so we can get at the elements with only a constant amount of work. We can arrange this by flipping the matrix left-to-right with map reverse. Now we always work with the first row and column. We just have to remember to un-reverse the row parts as we produce them.
-- L shapes from top left to top right then down to bottom right
lShaped :: [[a]] -> [[a]]
lShaped = lShaped' . map reverse
-- L shapes from top right backwards to top left then down to bottom left
lShaped' :: [[a]] -> [[a]]
lShaped' [] = []
lShaped' ([]:_) = []
lShaped' (xs:xss) = (reverse xs ++ map head xss) : lShaped' (map tail xss)
We need the two base cases to deal with rectangles taller than they are wide as well as wider than they are tall - your code is missing one of these.
Alternatively we could try to use library functions rather than doing manual recursion.
This function slices a rectangle into two parts along an upward-sloping line. n is the length of the first row of the upper/left part, or if n is greater than the width of the rectangle you have to imagine it as a coordinate outside the rectangle defining the top-right point of the cutting line, so that some full rows will appear in the upper/left part before we get down to the cut.
slice :: Int -> [[a]] -> ([[a]], [[a]])
slice n xss = unzip (zipWith splitAt [n,n-1 ..] xss)
Using slice splits up the elements nicely for the horizontal and vertical parts of the Ls, but the vertical parts aren't arranged in a useful way. Rather than try to rearrange them we can use slice again on the transpose of the matrix to get them in the right lists. Finally we put the horizontal and vertical parts together with zipWith (++).
I don't know if I like this solution better than the manual recursion but there it is. It's always a bit of a shame to introduce lengths and numbers into a list algorithm but I don't see a cleaner way at the moment.
{-# LANGUAGE TupleSections #-}
-- returns 2D list of Cartesian coordinates for entries of L-shaped matrix:
coordList :: Int -> [[(Int,Int)]]
coordList n = go n 0 n where -- rl: Row Length sr: Starting Row
go n sr rl = ((map (sr,) [0..(rl-1)]) ++ (map (,rl-1) [(sr+1)..(n-1)]) ) :
if (rl > 1) then go n (sr+1) (rl-1) else []
import qualified Data.Vector as V
-- vector-based version:
lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse xss =
let
rank = length (head xss) -- matrix rank
pairs = coordList rank -- 2D list of Cartesian coordinates
matrix = V.fromList (map V.fromList xss) -- 2D vector
in
map (map (\(i,j) -> ((matrix V.! i) V.! j))) $ pairs
测试程序:
printAsLines :: Show α => [α] -> IO ()
printAsLines xs = mapM_ (putStrLn . show) xs
main :: IO ()
main = do
let xss = [[1,2,3], [4,5,6], [7,8,9]]
lMat1 = lShapedTraverse xss
putStrLn $ "res1 = "
printAsLines lMat1
程序输出:
res1 =
[1,2,3,6,9]
[4,5,8]
[7]
As there are several possibilities to represent the input matrix, we can try to separate the “navigation”, i.e. choice of elements, from the actual matrix representation.
In order to achieve this, we can easily write a recursive function that produces the 2D list of Cartesian coordinates to be extracted from the input matrix:
{-# LANGUAGE TupleSections #-}
-- returns 2D list of Cartesian coordinates for entries of L-shaped matrix:
coordList :: Int -> [[(Int,Int)]]
coordList n = go n 0 n where -- rl: Row Length sr: Starting Row
go n sr rl = ((map (sr,) [0..(rl-1)]) ++ (map (,rl-1) [(sr+1)..(n-1)]) ) :
if (rl > 1) then go n (sr+1) (rl-1) else []
This might be inefficient, but it is correct. And so we can have a more efficient version of this by replacing lists by vectors and the list !! operator by the equivalent vector ! operator:
import qualified Data.Vector as V
-- vector-based version:
lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse xss =
let
rank = length (head xss) -- matrix rank
pairs = coordList rank -- 2D list of Cartesian coordinates
matrix = V.fromList (map V.fromList xss) -- 2D vector
in
map (map (\(i,j) -> ((matrix V.! i) V.! j))) $ pairs
Test program:
printAsLines :: Show α => [α] -> IO ()
printAsLines xs = mapM_ (putStrLn . show) xs
main :: IO ()
main = do
let xss = [[1,2,3], [4,5,6], [7,8,9]]
lMat1 = lShapedTraverse xss
putStrLn $ "res1 = "
printAsLines lMat1
发布评论
评论(2)
我们可以编写
initAndLast
,但它对性能没有太大帮助因为每个元素仍然需要做很多工作
结果。
我们真的希望在列表的开头工作,这样我们就可以
只需付出恒定的工作量即可获得元素。我们可以
通过使用
map reverse
从左到右翻转矩阵来排列它。现在我们总是使用第一行和第一列。我们只需要
请记住在我们生产行部分时取消反转它们。
我们需要两个基本情况来处理比它们高的矩形
宽并且比高度还宽 - 你的代码缺少一个
这些。
或者,我们可以尝试使用库函数而不是这样做
手动递归。
该函数沿向上倾斜的线将矩形切成两部分。
n
是上/左部分第一行的长度,或者如果 n 更大
比矩形的宽度你必须把它想象成一个坐标
在定义切割右上角点的矩形之外
行,这样一些完整的行就会出现在之前的上/左部分
我们开始讨论。
使用切片可以很好地分割元素的水平和
L 的垂直部分,但垂直部分没有排列成
有用的方法。我们可以再次使用切片,而不是尝试重新排列它们
对矩阵进行转置以使它们进入正确的列表。
最后我们将水平和垂直部分放在一起
zipWith (++)
。我不知道我是否比手动递归更喜欢这个解决方案
但它就在那里。引入长度总是有点遗憾
和数字到列表算法中,但我没有看到更干净的方法
片刻。
We could write
initAndLast
, but it wouldn't help performance verymuch because that would still be a lot of work to do for each element
of the result.
We really want to be working at the beginning of the lists so we can
get at the elements with only a constant amount of work. We can
arrange this by flipping the matrix left-to-right with
map reverse
.Now we always work with the first row and column. We just have to
remember to un-reverse the row parts as we produce them.
We need the two base cases to deal with rectangles taller than they are
wide as well as wider than they are tall - your code is missing one
of these.
Alternatively we could try to use library functions rather than doing
manual recursion.
This function slices a rectangle into two parts along an upward-sloping line.
n
isthe length of the first row of the upper/left part, or if n is greater
than the width of the rectangle you have to imagine it as a coordinate
outside the rectangle defining the top-right point of the cutting
line, so that some full rows will appear in the upper/left part before
we get down to the cut.
Using slice splits up the elements nicely for the horizontal and
vertical parts of the Ls, but the vertical parts aren't arranged in a
useful way. Rather than try to rearrange them we can use slice again
on the transpose of the matrix to get them in the right lists.
Finally we put the horizontal and vertical parts together with
zipWith (++)
.I don't know if I like this solution better than the manual recursion
but there it is. It's always a bit of a shame to introduce lengths
and numbers into a list algorithm but I don't see a cleaner way at the
moment.
由于表示输入矩阵有几种可能性,因此我们可以尝试将“导航”(即元素选择)与实际矩阵表示形式区分开。
为了实现这一目标,我们可以轻松地编写一个递归功能,该功能产生2D列表,从输入矩阵中提取的笛卡尔坐标列表:
在
ghci
解释下检查下:接下来,我们测试我们的新
coordList 通过幼稚使用效率低下的功能!列表提取操作员:
这可能是低效的,但这是正确的。因此,我们可以通过用向量和列表替换列表来获得更有效的版本!!等效向量的运营商!操作员:
测试程序:
程序输出:
As there are several possibilities to represent the input matrix, we can try to separate the “navigation”, i.e. choice of elements, from the actual matrix representation.
In order to achieve this, we can easily write a recursive function that produces the 2D list of Cartesian coordinates to be extracted from the input matrix:
Checking under the
ghci
interpreter:Next, we test our new
coordList
function by naïvely using the inefficient !! list extraction operator:This might be inefficient, but it is correct. And so we can have a more efficient version of this by replacing lists by vectors and the list !! operator by the equivalent vector ! operator:
Test program:
Program output: