2012-02-29 149 views
5

我必須編寫一個展開列表清單的函數。展開列表清單

例如flatten [] = []flatten [1,2,3,4] = [1,2,3,4]flatten [[1,2],[3],4,5]] = [1,2,3,4,5]

我遇到的麻煩的是能夠匹配取決於什麼是考慮到扁平化的功能類型。

這是我有:

data A a = B a | C [a] deriving (Show, Eq, Ord) 

flatten::(Show a, Eq a, Ord a)=>A a -> A a 
flatten (C []) = (C []) 
flatten (C (x:xs)) = (C flatten x) ++ (C flatten xs) 
flatten (B a) = (C [a]) 

從我可以告訴的問題是,++運營商期待於它的兩個參數列表,我想給它A類型的東西。我添加了A類型,因此該函數可以獲取單個元素或元素列表。

有誰知道以不同的方式來做這個不同的,或解釋我能做些什麼來解決類型錯誤?

+0

我不知道你想要什麼。也許'flatten :: A [a] - > A a;展平(B xs)= C xs; flatten(C xss)= C(concat xss)'會幫助你嗎?基本上,你不能寫扁平化,以便它需要不同的嵌套列表並且與它們做不同的事情,除非你將它們包裝成新類型並通過構造函數區分這些情況。 – 2012-02-29 22:07:13

+1

函數的類型應該是'[[a]] - > [a]'。這意味着'flatten []'是有效的,並且'flatten [[1,2,3,4]]'是有效的,但是'flatten [1,2,3,4]'不是。 '[1,2,3,4]'不是列表的列表。如果你仔細想想並從頭開始,擺脫你的特殊類型,你會發現它更容易。 – 2012-02-29 22:10:42

+0

[列表中的操作| |列表中的操作可能重複如何](http://stackoverflow.com/questions/9477806/operation-on-list-of-lists-how) – rampion 2012-03-01 02:23:32

回答

20

這是有點不清楚你要求什麼,但扁平列表是一個標準功能concat在類型簽名[[a]] -> [a]前奏。

如果您嵌套列表的數據類型,你在上面開始,也許你想你的數據類型調整到這樣的事情:

data Lists a = List [a] | ListOfLists [Lists a] 

然後您可以拼合這些到一個列表;

flatten :: Lists a -> [a] 
flatten (List xs) = xs 
flatten (ListOfLists xss) = concatMap flatten xss 

作爲測試,

> flatten (ListOfLists [List [1,2],List [3],ListOfLists [List [4],List[5]]]) 
[1,2,3,4,5] 
9

首先,A型是在正確的軌道上,但我不認爲這是相當正確的。你希望它能夠拉平任意嵌套列表,所以類型的值「A是」應該能包含類型的值「A一」:

data A a = B a | C [A a] 

其次,函數的類型應該是稍微不一樣。您可能希望它只返回a的列表,而不是返回「A a」類型的值,因爲根據定義,函數總是返回一個扁平列表。所以類型簽名是這樣的:

flatten :: A a -> [a] 

另外請注意,沒有類型類的約束是必要的 - 這個功能是完全通用的,因爲它沒有在列表的元素,看起來都沒有。

這裏是我的實現:

flatten (B a) = [a] 
flatten (C []) = [] 
flatten (C (x:xs)) = flatten x ++ flatten (C xs) 
+2

'flatten(B a)= [a]; flatten(C xs)= flatten = << xs' – luqui 2012-03-01 01:27:00

0

這一個班輪將完成這項工作。雖然因爲它是由馬林提到的類型簽名是不同的:

flatten :: [[a]] -> [a]   
flatten xs = (\z n -> foldr (\x y -> foldr z y x) n xs) (:) [] 

簡單的測試

frege> li = [[3,4,2],[1,9,9],[5,8]] 
frege> flatten li 
[3,4,2,1,9,9,5,8] 
+0

關鍵是函數應該適用於簡單列表和嵌套列表。您的作品僅適用於簡單列表。 – Lii 2016-02-08 19:58:55