转置列表的列表

我试图做一个递归函数来获得列表的转置，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

转置列表的列表

回答

相关问题