Haskell：如何返回列表中可能的分割列表

Question

我正在嘗試編寫一個名爲split的函數，它需要一個列表並返回所有不同分割對的列表，例如，

split [4,3,6] = [([],[4,3,6]),([4],[3,6]),([4,3],[6]),([4,3,6],[])] 

現在我寫這

split :: [a] -> [([a],[a])] 
split []  = [([],[])] 
split (x:xs) = ([],(x:xs)):(zip (map (x:) (map fst split(xs))) (map snd split(xs))) 

一段代碼和擁抱，我的選擇的解釋讓我這個

ERROR file:.\split.hs:3 - Type error in application 
*** Expression  : map snd split xs 
*** Term   : map 
*** Type   : (e -> f) -> [e] -> [f] 
*** Does not match : a -> b -> c -> d 

錯誤消息。我做錯了什麼？爲什麼（map snd split xs）的類型是
（a-> b - > c - > d）？

Answer 1

你錯位了你的parens。嘗試

split (x:xs) = ([],(x:xs)):(zip (map (x:) (map fst (split xs))) (map snd (split xs))) 

Haskell沒有以同樣的方式使用括號函數調用，就像這樣C和Java。當您編寫map fst split(xs)時，這與map fst split xs相同，即編譯器認爲您嘗試使用三個參數調用map。因此，您需要將split這個電話的父母號碼設爲：map fst (split xs)。

你有效地試圖寫的是一個簡單的zipper列表。實現它的最簡單的方法是

import Data.List (inits, tails) 

split xs = zip (inits xs) (tails xs) 

Answer 2

這裏是一個另類的定義：

splits :: [a] -> [(a, a)] 
splits xs = map (flip splitAt xs) [0 .. length xs] 

誠然，這不是很有效，但至少它的簡潔:-)

另一個版本，甚至更短，並可能更有效，使用inits和tails從Data.List：

splits :: [a] -> [(a, a)] 
splits xs = zip (inits xs) (tails xs) 

現在讓我們開心一點。我們可以寫inits和tails爲foldr，這裏，我們使用initsA和tailsA代表所謂的代數的褶皺：

inits :: [a] -> [[a]] 
inits = foldr initsA [[]] 

initsA :: a -> [[a]] -> [[a]] 
initsA x xss = [] : map (x:) xss 

tails :: [a] -> [[a]] 
tails = foldr tailsA [[]] 

tailsA :: a -> [[a]] -> [[a]] 
tailsA x xss = (x : head xss) : xss 

利用這些代數，我們可以進一步將它們合併：

splits :: [a] -> [([a], [a])] 
splits = foldr splitsA [([], [])] 

splitsA :: a -> [([a], [a])] -> [([a], [a])] 
splitsA xy xyss = zip (initsA xy xss) (tailsA xy yss) 
    where (xss, yss) = unzip xyss 

所以現在我們有定義爲單一foldrsplits！