Hiểu hàm chuyển vị ma trận này trong Haskell

Question

Chức năng chuyển vị ma trận này hoạt động, nhưng tôi đang cố gắng hiểu được việc thực hiện từng bước và tôi không hiểu.

transpose:: [[a]]->[[a]] 
    transpose ([]:_) = [] 
    transpose x = (map head x) : transpose (map tail x) 

với

transpose [[1,2,3],[4,5,6],[7,8,9]] 

nó sẽ trả về:

[[1,4,7],[2,5,8],[3,6,9]] 

Tôi không hiểu thế nào các nhà điều hành nối đang làm việc với bản đồ. Nó được nối mỗi đầu x trong cùng một hàm gọi? Làm sao?

là này

(map head x) 

tạo ra một danh sách các yếu tố đầu của mỗi danh sách?

Answer 1

Hãy nhìn vào những gì các chức năng làm ví dụ đầu vào của bạn:

transpose [[1,2,3],[4,5,6],[7,8,9]] 
<=> 
(map head [[1,2,3],[4,5,6],[7,8,9]]) : (transpose (map tail [[1,2,3],[4,5,6],[7,8,9]])) 
<=> 
[1,4,7] : (transpose [[2,3],[5,6],[8,9]]) 
<=> 
[1,4,7] : (map head [[2,3],[5,6],[8,9]]) : (transpose (map tail [[2,3],[5,6],[8,9]])) 
<=> 
[1,4,7] : [2,5,8] : (transpose [[3],[6],[9]]) 
<=> 
[1,4,7] : [2,5,8] : (map head [[3],[6],[9]]) : (transpose (map tail [[3],[6],[9]])) 
<=> 
[1,4,7] : [2,5,8] : [3, 6, 9] : (transpose [[], [], []]) 
<=> 
[1,4,7] : [2,5,8] : [3, 6, 9] : [] -- because transpose ([]:_) = [] 
<=> 
[[1,4,7],[2,5,8],[3,6,9]] 

Lưu ý rằng thứ tự mà tôi đã chọn để làm giảm các điều khoản, không phải là giống như Haskell trật tự thẩm định sẽ sử dụng, nhưng điều đó không thay đổi kết quả.

Chỉnh sửa: Đáp lại câu hỏi đã chỉnh sửa của bạn:

là này

(map head x) 

tạo ra một danh sách các yếu tố đầu của mỗi danh sách?

Vâng, đúng vậy.

Answer 2

Toán tử toán tử : đính kèm một đối tượng thuộc loại a vào danh sách loại [a]. Trong

(map head x) : transpose (map tail x) 

Các LHS là một danh sách (a = [b]), trong khi RHS là danh sách các danh sách ([a] = [[b]]), do đó, một công trình như vậy là hợp lệ. Kết quả là

[x,y,z,...] : [[a,b,...],[d,e,...],...] = [[x,y,z,...], [a,b,...],[d,e,...],...] 

---

Trong trường hợp của bạn, map head x và map tail x chia ma trận

x = [[1,2,3],[4,5,6],[7,8,9]] 

vào

map head x = [1,4,7] 
map tail x = [[2,3],[5,6],[8,9]] 

(và có, map head x là danh sách các yếu tố đầu của mỗi danh sách.) Phần 2 được hoán (cho các bước chi tiết thấy @sepp2k 's câu trả lời) để tạo thành

transpose (map tail x) = [[2,5,8],[3,6,9]] 

nên khuyết điểm-ing [1,4,7] này mang đến cho

map head x : transpose (map tail x) = [1,4,7] : [[2,5,8],[3,6,9]] 
            = [[1,4,7] , [2,5,8],[3,6,9]] 

Answer 3

ghci là bạn của bạn:

*Main> :t map head 
map head :: [[a]] -> [a] 
*Main> :t map tail 
map tail :: [[a]] -> [[a]]

Thậm chí nếu bạn không hiểu map (một vấn đề bạn muốn sửa nhanh!), Các loại biểu thức này nói nhiều về cách họ làm việc. Đầu tiên là một danh sách duy nhất được lấy từ danh sách các danh sách, vì vậy chúng ta hãy nạp một véc tơ đơn giản cho nó để xem điều gì xảy ra.

Bạn có thể muốn viết

*Main> map head [1,2,3] 

nhưng điều đó không typecheck:

<interactive>:1:14: 
    No instance for (Num [a]) 
     arising from the literal `3' at :1:14 
    Possible fix: add an instance declaration for (Num [a]) 
    In the expression: 3 
    In the second argument of `map', namely `[1, 2, 3]' 
    In the expression: map head [1, 2, 3]

Hãy nhớ rằng, kiểu của đối số là một danh sách liệt kê, vì vậy

*Main> map head [[1,2,3]] 
[1] 

Bắt một phức tạp hơn một chút

*Main> map head [[1,2,3],[4,5,6]] 
[1,4] 

Làm tương tự nhưng với tail thay vì head cho

*Main> map tail [[1,2,3],[4,5,6]] 
[[2,3],[5,6]] 

Như bạn thấy, định nghĩa về transpose được lặp đi lặp lại cắt ra khỏi “hàng” đầu tiên với map head x và transposing phần còn lại, đó là map tail x.

Answer 4

Nhân tiện, chức năng này không hoạt động khi được cung cấp đầu vào như [[1,2,3], [], [1,2]]. Tuy nhiên, chức năng chuyển đổi từ Data.List sẽ chấp nhận đầu vào này và trả lại [[1,1], [2,2], [3]].

Khi chúng tôi gọi mã đệ quy transpose, chúng tôi cần loại bỏ [].

Answer 5

Những điều này đều giống nhau:

map head xxs 
map (\xs -> head xs) xxs 

Đó là lambda thể hiện, có nghĩa là tôi trở người đứng đầu xs cho mỗi xs Ví dụ:

map head [[1,2,3],[4,5,6],[7,8,9]] 
-> map (\xs -> head xs) [[1,2,3],[4,5,6],[7,8,9]] 
-> [head [1,2,3], head [4,5,6], head [7,8,9]] 
-> [1,4,7] 

Nó đơn giản