轉置列表的列表

我試圖做一個遞歸函數來獲得列表的轉置，n x p到p x n。但我無法這樣做。我已經能夠做出一個函數來轉列表的3 x n列表到n x 3之一：轉置列表的列表

let rec drop1 list= 
    [(match (List.nth list 0) with [] -> [] | a::b -> b); 
    (match (List.nth list 1) with [] -> [] | a::b -> b); 
    (match (List.nth list 2) with [] -> [] | a::b -> b);] 

let rec transpose list= 
    if List.length (List.nth list 0) == 0 then [] 
    else [(match (List.nth list 0) with [] -> 0 | a::b -> a); 
      (match (List.nth list 1) with [] -> 0 | a::b -> a); 
      (match (List.nth list 2) with [] -> 0 | a::b -> a)] 
     :: transpose (drop1 list)

但我不能概括它。我一定在錯誤的方向思考。這是普遍化的嗎？有更好的解決方案嗎？請幫忙。

來源

2010-10-21 lalli

let rec transpose list = match list with 
| []    -> [] 
| [] :: xss -> transpose xss 
| (x::xs) :: xss -> 
    (x :: List.map List.hd xss) :: transpose (xs :: List.map List.tl xss)

來源

2010-10-21 16:42:07 sepp2k

+1，哇！我不知道List.map函數。手冊說它不是尾遞歸的。如果我在更大的代碼中使用它，會產生什麼影響？ – lalli 2010-10-21 16:56:03

@lalli：對於非常大的列表，它可能導致堆棧溢出。在這種情況下，應該使用'List.rev_map'來代替，然後遍歷最後的列表並將其反轉。但是請注意，我對'轉置'的定義也不是尾遞歸（你的也不是）。 – sepp2k 2010-10-21 17:14:18

你一開始不應該擔心尾部遞歸;嘗試有一個簡單明瞭的實現。無論如何，對列表非常大的（'列表列表）使用「轉置」功能可能是一個非常糟糕的主意。如果你有很多數據，其他的數據結構（例如一個由（int * int）索引的矩陣，它具有一個常數時間的「轉置」函數）可能更合適。 – gasche 2010-10-21 19:06:42

轉置列表的列表

回答

相關問題