时间戳

首页 > 解决方案 > 在 F# 中转置嵌套列表

list - 在 F# 中转置嵌套列表

问题描述

我想'a list list在 F# 中转置一个嵌套列表 ( )。问题是，我不想使用递归。

但是，我发现为了不使用递归，我必须使用可变列表。在我看来，这有点问题。尽管如此，我还是尝试用一个 for 循环和两个可变列表来实现它：

let transpose (llst : 'a list list) : 'a list list =
   let mutable lst = llst
   let mutable result = [List.map List.head lst]
   for i = 1 to lst.Length do
      lst <- List.map List.tail lst
      result <- List.append result [List.map List.head lst]
   result

此外，我试图避免它。我知道数组的可变性，因此我尝试通过将 from 转换'a list list为 2darray ( [,]) 来解决该问题，但是，当尝试将结果转换回嵌套列表时，它会失败，因为List.ofArray仅适用于一维数组：

let transpose (llst : 'a list list) : 'a list list = [List.ofArray (Array2D.init (llst.ToArray.GetLength 1) (llst.ToArray.GetLength 0) (fun x y -> llst.ToArray.[y,x]))]

第一个代码有效，但我想要一个更简单的实现，没有 for 循环或可变列表。第二个代码不起作用，因为该函数List.ofArray仅适用于[]，而不适用于[,]。

我也试过

List.init (llst.[0].Length) (List.forall (fun SOMETHING) llst)

其中SOMETHING将包含一个函数，该函数采用两个子列表的第一列，然后删除第一列。（List.map List.head 和 List.map List.tail）。也许使用List.map?

标签： listf#nestedtranspose

解决方案

这样做的一种方法是采用递归定义并将其转换为非递归。例如，以下递归定义改编自此答案，并对其使用列表推导进行了调整：

let rec transpose xs = [
  match xs with
  | [] -> failwith "cannot transpose a 0-by-n matrix"
  | []::xs -> () 
  | xs -> 
      yield List.map List.head xs 
      yield! transpose (List.map List.tail xs) ]

这是尾递归的，因此很容易转换为循环。您只需使参数xs可变并用突变替换递归调用。我们还需要添加一个标志来终止循环：

let rec transpose xs = [
  let mutable xs = xs
  let mutable finished = false
  while not finished do
    match xs with
    | [] -> failwith "cannot transpose a 0-by-n matrix"
    | []::_ -> finished <- true
    | _ -> 
        yield List.map List.head xs 
        xs <- List.map List.tail xs ]

如果您想要一个没有序列推导的可变版本，您可以轻松地做到这一点 - 推导只是收集您使用添加的各个子列表yield。您可以将它们添加到可变列表中（然后反转列表以按正确顺序获取结果）：

let rec transpose xs = 
  let mutable result = []
  let mutable xs = xs
  let mutable finished = false
  while not finished do
    match xs with
    | [] -> failwith "cannot transpose a 0-by-n matrix"
    | []::_ -> finished <- true
    | _ -> 
        result <- (List.map List.head xs) :: result
        xs <- List.map List.tail xs 
  List.rev result

推荐阅读