我正在嘗試遍歷L Shape中的串列串列。例如：lShapedTraverse [[1,2,3],[4,5,6],[7,8,9]]將導致[[1,2,3,6,9],[4,5,8],[7]]
我有以下演算法，可以提供所需的輸出。
lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse [] = []
lShapedTraverse [xs] = [xs]
lShapedTraverse (xs:xss) = let (rest, col) = ((map init xss), (map last xss))
in (xs col) : lShapedTraverse rest
這是遍歷串列串列 2 次以獲得initand last，我認為可以使用可以initAndLast在一次遍歷中完成的自定義函式來避免這種情況。
我想看看我是否可以做一個更有效的實作和慣用的 Haskell。任何輸入表示贊賞。
謝謝。
uj5u.com熱心網友回復：
我們可以撰寫initAndLast，但這對性能沒有太大幫助，因為對于結果的每個元素來說，這仍然需要做很多作業。
我們真的很想在串列的開頭作業，這樣我們就可以通過恒定的作業量來獲取元素。我們可以通過將矩陣從左到右翻轉來安排map reverse。現在我們總是使用第一行和第一列。我們只需要記住在生產它們時取消反轉行部分。
-- 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)
使用 slice 可以很好地拆分 Ls 的水平和垂直部分的元素，但垂直部分的排列方式并不實用。我們可以在矩陣的轉置上再次使用 slice 來將它們放在正確的串列中，而不是嘗試重新排列它們。最后我們把水平和垂直部分放在一起
zipWith ( )。
lShaped'' :: [[a]] -> [[a]]
lShaped'' [] = []
lShaped'' xss = zipWith ( ) rowParts (reverse colParts)
where
(rowParts, _) = slice width xss
(_, colParts) = slice width (transpose xss)
width = length (head xss)
我不知道我是否比手動遞回更喜歡這個解決方案，但確實如此。將長度和數字引入串列演算法總是有點遺憾，但目前我沒有看到更簡潔的方法。
uj5u.com熱心網友回復：
由于表示輸入矩陣有多種可能性，我們可以嘗試將“導航”（即元素的選擇）與實際矩陣表示分開。
為了實作這一點，我們可以輕松撰寫一個遞回函式，該函式生成要從輸入矩陣中提取的笛卡爾坐標的二維串列：
{-# 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 []
ghci在解釋器下檢查：
λ>
λ> coordList 3
[[(0,0),(0,1),(0,2),(1,2),(2,2)],[(1,0),(1,1),(2,1)],[(2,0)]]
λ>
coordList接下來，我們通過天真地使用低效的 !! 來測驗我們的新功能。串列提取運算子：
λ> printAsLines xs = mapM_ (putStrLn . show) xs
λ>
λ> xss = [[1,2,3], [4,5,6], [7,8,9]]
λ>
λ> printAsLines $ map (map (\(i,j) -> ((xss !! i) !! j))) $ (coordList 3)
[1,2,3,6,9]
[4,5,8]
[7]
λ>
這可能效率低下，但它是正確的。因此，我們可以通過用向量和串列替換串列來獲得更有效的版本！等價向量的運算子！操作員：
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]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/454314.html