2012-02-29 64 views
5

Tôi phải viết một hàm làm phẳng danh sách danh sách.Làm phẳng danh sách các danh sách

Ví dụ flatten [] = [] hoặc flatten [1,2,3,4] = [1,2,3,4] hoặc flatten [[1,2],[3],4,5]] = [1,2,3,4,5]

Tôi đang gặp rắc rối với việc có thể để phù hợp với loại phụ thuộc vào những gì được trao cho các chức năng flatten.

Dưới đây là những gì tôi có:

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]) 

Từ những gì tôi có thể nói vấn đề là các nhà điều hành ++ đang mong đợi một danh sách cho cả hai đối số của nó và tôi đang cố gắng để cung cấp cho nó một cái gì đó kiểu A. Tôi đã thêm loại A để chức năng có thể lấy một phần tử đơn lẻ hoặc danh sách các phần tử.

Có ai biết cách khác để thực hiện việc này khác hay giải thích những gì tôi có thể làm để khắc phục lỗi loại?

+0

Tôi không chắc chắn chính xác những gì bạn muốn. Có lẽ 'flatten :: A [a] -> A a; flatten (B xs) = C xs; flatten (C xss) = C (concat xss) 'sẽ giúp bạn?Về cơ bản, bạn không thể viết flatten để nó có danh sách các tổ khác nhau và làm những việc khác nhau với chúng, trừ khi bạn bọc chúng thành một kiểu mới và phân biệt các trường hợp với hàm tạo. –

+1

Loại hàm của bạn phải là '[[a]] -> [a]'. Điều này có nghĩa là 'flatten []' là hợp lệ, và 'flatten [[1,2,3,4]]' là hợp lệ, nhưng 'flatten [1,2,3,4]' thì không. '[1,2,3,4]' không phải là danh sách các danh sách. Nếu bạn nghĩ về điều đó và bắt đầu từ đầu, loại bỏ loại đặc biệt của bạn, bạn sẽ thấy nó dễ dàng hơn nhiều. –

+0

có thể trùng lặp với [thao tác trên danh sách danh sách | cách] (http://stackoverflow.com/questions/9477806/operation-on-list-of-lists-how) – rampion

Trả lời

20

Đó là một chút không rõ ràng những gì bạn đang yêu cầu, nhưng san phẳng một danh sách các danh sách là một chức năng tiêu chuẩn được gọi là concat trong khúc dạo đầu với chữ ký loại [[a]] -> [a].

Nếu bạn thực hiện một kiểu dữ liệu của danh sách lồng nhau như bạn đã bắt đầu ở trên, có thể bạn muốn điều chỉnh kiểu dữ liệu của bạn để một cái gì đó như thế này:

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

Sau đó, bạn có thể làm phẳng những vào một danh sách;

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

Là một kiểm tra,

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

Thứ nhất, Một loại là đi đúng hướng nhưng tôi không nghĩ rằng nó khá chính xác. Bạn muốn nó để có thể san bằng danh sách tùy tiện lồng nhau, do đó, một giá trị của loại "A a" sẽ có thể chứa các giá trị của loại "A a":

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

Thứ hai, các loại chức năng nên hơi khác. Thay vì trả về một giá trị kiểu "A a", bạn có thể muốn nó trả về một danh sách của một, vì theo định nghĩa hàm luôn luôn trả về một danh sách phẳng. Do đó, chữ ký loại là:

flatten :: A a -> [a] 

Cũng cần lưu ý rằng không có ràng buộc về kiểu chữ nào - chức năng này hoàn toàn chung vì không nhìn vào các thành phần của danh sách.

Dưới đây là thực hiện của tôi:

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

0

lót này sẽ thực hiện công việc. Mặc dù như nó đã được đề cập bởi Malin chữ ký kiểu là khác nhau:

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

đơn giản kiểm tra

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

Vấn đề là chức năng nên hoạt động cho cả danh sách đơn giản và lồng nhau. Tác phẩm của bạn chỉ dành cho các danh sách đơn giản. – Lii

Các vấn đề liên quan