比方說，我有兩個這樣的串列：
["hello", "hi", "hey"] 和 ["apple", "an", "hey"]
我想檢查兩個串列是否包含相同數量的串列，并且相應的內部串列是否包含相同數量的元素。在這種情況下，此函式應回傳True。它也應該適用于無休止的串列（所以在像[[1..], [1..]]and[[1..], [3,4,5]]它應該回傳的情況下False，因為只有第一個串列的第二個元素是無限的，第二個串列的第二個元素不是）。
到目前為止，我想出了這個：
listsSize (x:xs) (y:ys)
| length x == length y && length xs == length ys = True
| otherwise = False
但它只檢查串列是否包含相同數量的串列，它不會評估內部串列。
uj5u.com熱心網友回復：
一個功能不完全的簡單版本是首先實作一個更簡單的函式，該函式只檢查兩個串列是否具有相同的形狀：
sameShape :: [a] -> [b] -> Bool
由于length永遠不會完成無限串列，因此您需要直接使用模式匹配：
sameShape [] [] = ...
sameShape [] (y:ys) = ...
sameShape (x:xs) [] = ...
sameShape (x:xs) (y:ys) = ...
需要注意的是，如果兩個串列都是無限的，sameShape則無法真正回傳True；不過，它應該能夠在有限的時間內為所有其他型別的輸入獲得正確的答案。
要檢查嵌套串列是否具有相同的形狀，您可以檢查外部串列是否具有相同的形狀以及每個內部串列對是否具有相同的形狀：
sameShapes :: [[a]] -> [[b]] -> Bool
sameShapes xss yss = and (sameShape xss yss : zipWith sameShape xss yss)
這是一個很好的組合解決方案，但它存在一個問題，即sameShape當某些串列是無限的而其他串列不是時，很難知道呼叫的順序。這是可能性，以及一個輸入示例，他們原則上可以計算答案但永遠旋轉：
- 首先檢查外部串列的形狀。（這就是
sameShapes上面所做的。）然后檢查串列repeat []并且"abc" : repeat []永遠不會完成。 - 首先檢查第一個元素的形狀。檢查串列
[repeat 'a', ""]，[repeat 'a', "abc"]永遠不會完成。 - 事實上，前面的專案符號概括了：如果你首先選擇任何特定元素位置的形狀，就會有一個反例。如果您首先查看索引n，那么檢查通過在兩個輸入中放置
repeat 'a'索引n和""/"abc"在索引n 1處形成的串列將永遠不會完成。
因此，不幸的是，這些檢查需要相互交錯。有一個相當標準的技巧叫做“對角化”，它使這種事情成為可能。將外部串列視為行的集合，將每個內部串列視為該行的列值的集合：
1 2 3 4 . . .
a a1 a2 a3 a4 . . .
b b1 b2 b3 b4 . . .
c c1 c2 c3 c4 . . .
d d1 d2 d3 d4 . . .
. . . . . .
. . . . . .
. . . . . .
您可以通過根據它們與左上角的距離進行排序來確保訪問每個位置，因此按此順序：
_/ _/ _/
|/_ _/ _/
_/ _/
_/ _/
|/_ _/
_/
_/
|/_
（等等）這些是證明名稱“對角化”合理的對角線。如果我們的兩個嵌套串列具有不同的形狀，這可以保證最終我們將嘗試查看一個越界而不是另一個的索引。
一個非常有效的實作有點復雜。幸運的是，低效版本并不太難。我們會慢慢看越來越多的行，跟蹤那些可見的xss，并yss與在我們還沒有開始尋找的那些xss'和yss'。每次查看時，我們都會查看每行中的一列。您可以在我的另一個答案中看到對另一個問題的類似解決方案的更多描述。這是它如何查找此問題*：
sameShapesDiagonal :: [[a]] -> [[b]] -> Bool
sameShapesDiagonal = go [] [] where
go xss yss xss' yss' = done || noMismatchYet where
done = and ([null xss', null yss'] map null xss map null yss)
noMismatchYet = True
&& null xss' == null yss'
&& and (zipWith (\xs ys -> null xs == null ys) xss yss)
&& go (xssh map (drop 1) xss) (yssh map (drop 1) yss) xsst ysst
(xssh, xsst) = splitAt 1 xss'
(yssh, ysst) = splitAt 1 yss'
If given any mismatching shapes, this function will return False in finite time. If given matching finite shapes, this function will return True in finite time. If given matching shapes with some infinite list, it will never return; but it is not possible to both return and satisfy the previous two correctness properties in such a case.
Here's some examples of using it:
> sameShapesDiagonal ["hello", "hi", "hey"] ["apple", "an", "hey"]
True
> sameShapesDiagonal [[1..], [1..]] [[1..], [3,4,5]]
False
> sameShapesDiagonal [[1..], [1..]] [[3,4,5], [1..]]
False
> sameShapesDiagonal (repeat []) ("abc" : repeat [])
False
> sameShapesDiagonal [repeat 'a', ""] [repeat 'a', "abc"]
False
*為免您將其復制并粘貼為您自己的學校練習解決方案，讓我向您保證，我的實作中有很多事情會引起希望對初學者代碼進行評分的人的注意。為避免懷疑，您需要了解這個答案，然后僅使用您和您的同行都覺得舒適的技術撰寫自己的實作（簡單的第一種演算法或更復雜的第二種演算法）。
uj5u.com熱心網友回復：
你不能*檢查一個串列是否是無限的，而不限制你如何制作無限串列。假設這樣，也不可能檢查兩個串列是否都是無限的——假設我們有這樣一個函式f :: [a] -> [a] -> Bool。然后我可以寫isEndless xs = f xs xs來實作“這個串列是無窮無盡的”檢查。
如果我們將問題限制為“最多一個串列可以是無限的”，那么就可以通過與檢查它們是否具有相同長度的相同方法來實作，即同時遍歷它們，直到其中之一用完了。如果你給它兩個無限串列，這將如預期的那樣回圈。
PS：
if b then True else False
和 just 一樣b。同樣，你的守衛可以轉換為只是length x == length y && length xs == length ys
* 假設我有一個isEndless :: [a] -> Bool只需要有限時間的，我可以解決停機問題。草圖：假設我有一些型別Program和Step，分別代表一個程式及其執行的單個步驟（例如在圖靈機中）。然后我可以寫給steps :: Program -> [Step]我一個程式將執行的“步驟”串列，因為我可以模擬程式運行。請注意 的結果如何steps可能是無限的。然后，
halts :: Program -> Bool
halts p = not (isEndless (steps p))
告訴我任意程式是否停止。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/370706.html