Haskell分割列表函數無限類型錯誤

Question

我正在研究Haskell中的一個函數，它將採用一個列表並將其分成兩個大小均勻的列表。以下是我有：

split (x:y:xs) = split2 ([((length(x:y:xs) `div` 2)-2) : x ++ y] : [xs]) 
split2 (x:xs:[y:ys]) = split2 ((x-1) : [xs] ++ y : [ys]) 
split2 (0:xs:[y:ys]) = (xs:[y:ys]) 

該函數將列表中的前兩個元素，並把它們一起放入列表＃2和追加第一列表作爲第二個元素。然後它得到列表的長度，並將它除以2以找出運行多少次，考慮到它已經從第一個列表中移除了兩個元素。然後，它將這兩條信息放入split2中，它將第一個列表中的另一個元素附加到第一個元素中的第二個列表中，並從運行次數中減1，然後再次運行。

問題是，當我運行它，我得到這個：

Functions.hs:19:49: 
    Occurs check: cannot construct the infinite type: t0 = [t0] 
    In the first argument of `(:)', namely `(y)' 

19指的是線2條，第split2功能。不完全確定如何去解決這個錯誤。有任何想法嗎？

Answer 1

很難知道從哪裏開始...

讓我們在split2定義從越來越大的表達的大塊功能。

f1 (x:y:xs) = (length(x:y:xs) `div` 2)-2 
f1 :: [a] -> Int 

好了，所以參數是東西的清單，並返回一個Int

f2 (x:y:xs) = ((length(x:y:xs) `div` 2)-2) : x 
f2 :: [[Int]] -> [Int] 

這裏，lengthInt被cons'd與x，所以x必須[Int]，所以(x:y:xs)必須是[[Int]]。我們還可以推斷y與x具有相同的類型，並且xs是相同類型的東西的列表; [[Int]]。所以x ++ y也將是[Int]。因此，[xs]將有類型[[[Int]]]。現在，我們與[xs]包裹結果列表中的構造，和缺點吧：

f3 (x:y:xs) = [((length(x:y:xs) `div` 2)-2) : x ++ y] : [xs] 
f3 :: [[Int]] -> [[[Int]]] 

我猜你沒想到的參數是Int小號列表的列表清單。現在

，如果我們看一下split2，論證模式(x:xs:[y:ys])意味着它是類型：

split2 :: [[a]] -> b 
    x :: [a] 
    xs :: [a] 
    y :: a 
    ys :: [a] 

split2嘗試的第一個定義的RHS通過連接(x-1) : [xs]和y : [ys]構建一個新的列表。但是，如果我們替換類型爲y : [ys]，我們發現：

y : [ys] :: a : [[a]] 

但由於(:) :: a -> [a] -> [a]，這意味着[[a]]必須是同一類型[a]，或a必須是自身的名單，這是不可能的。

(x-1)也是輸入錯誤，因爲它試圖從列表中減去一個。

我不能告訴你是否要將列表拆分爲偶數和奇數元素，或者分爲第一和第二半。

下面是分成第一半和第二半，下舍入（RD）或向上（RU），如果長度爲奇數兩個版本：

splitRD xs = splitAt (length xs `div` 2) xs 
splitRU xs = splitAt ((length xs + 1) `div` 2) xs 

下面是將列表分成甚至一個版本和奇數元素：

splitEO [] = ([], []) 
splitEO [e] = ([e], []) 
splitEO (e:o:xs) = (e:es, o:os) where (es, os) = splitEO xs 

Answer 2

幾點建議

• 寫類型的所有功能。它使代碼更具可讀性，並有助於捕獲錯誤。

• ++的類型是[a] -> [a] -> [a]並且您正在添加列表的長度以及元素。由於列表必須是統一類型，且長度返回Int類型，所以編譯器推斷split的類型爲 [[Int]] -> t（假設split2返回類型t）。

• 當您將([((length(x:y:xs) div 2)-2) : x ++ y] : [xs])傳遞給split2。 xs是[[Int]]類型，這意味着 [xs]是[[[Int]]] 類型的，所以編譯器推斷的split2類型[[[Int]]] -> t。

現在split2

split2 (x:xs:[y:ys]) = split2 ((x-1) : [xs] ++ y : [ys]) 

ys的定義是[[Int]]類型，因此y是[Int]類型。 xs類型爲[[Int]]，但是您在做[xs] ++ y，這意味着[xs]和y應該是相同類型（[a]對於某些a）。

既然你沒有提供任何類型的編譯器，完全搞不懂如何推斷這樣的類型。

如果你只是想列表分成相等的兩個部分，爲什麼不去做一些更簡單的像

split3 :: [a] -> ([a], [a]) 
split3 [] = ([],[]) 
split3 [x] = ([x],[]) 
split3 (x:y:xs) = let (xs',ys') = split3 xs in (x:xs',y:ys') 

Answer 3

在Haskell中，列表中的元素必須是所有同類型的。在你的函數中，列表包含Ints的混合物，原始列表的元素和原始列表的子列表，所有這些都可能是不同的類型。

對於如何附加列表和元素，您也有一些困惑。x ++ y只能在x和y是它們自己的列表時使用，而x：y只能在y是列表且x是列表元素時使用;創建一個包含x和y作爲元素的新列表，而不是使用[x，y]（儘管x：[y]也可以）。同樣，[xs] ++ y需要改爲xs ++ [y]。

不改變你的基本算法，最簡單的解決方案可能是讓split2取3個獨立的參數。

split (x:y:xs) = split2 ((length(x:y:xs) `div` 2)-2) [x,y] xs 
split2 n xs (y:ys) = split2 (n-1) (xs++[y]) ys 
split2 0 xs ys = [xs,ys] 

Answer 4

你似乎在列表周圍穿過狀態，而不是作爲值的功能，當它看起來好像你正在創建異質值的列表的編譯器，產生的問題，而列表在Haskell應該是同質類型的。

而不是

split2 (0:xs:[y:ys]) 

你應分別通過不同的參數/值的函數這樣

split2 n xs (y:ys) 

你要找也轉載於標準庫函數的功能。

halveList xs = splitAt (length xs `div` 2) xs