Транспонирование вложенных списков в F # - PullRequest
Новая
       36

Транспонирование вложенных списков в F #

0 голосов
/ 03 октября 2019

Я бы хотел перенести вложенный список ('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

Более того, я старался избегать этого. Я знаю изменчивость массивов, поэтому я попытался решить эту проблему путем преобразования из '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?

Ответы [ 2 ]

2 голосов
/ 03 октября 2019

Один из способов сделать это - взять рекурсивное определение и перевести его на нерекурсивный. Например, следующее рекурсивное определение адаптировано из этого ответа с твиком, в котором используются списочные выражения: 

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
0 голосов
/ 05 октября 2019

Итак, я благодарен за ответ, но на самом деле я хотел узнать, как создать простейшую и наиболее компактную функцию для преобразования списка в список. Теперь я придумал кое-какую странную реализацию. Несмотря на компактность, я думаю, что это довольно сложно: 

let transpose (llst: 'a list list) : 'a list list = 
List.map (List.map List.head) (List.init llst.Head.Length (fun x -> List.fold (fun x f -> f x) llst (List.init x (fun x -> (List.map List.tail)))))

Можно сделать проще с некоторыми подфункциями, но мне забавно, как работает такая странная реализация. Спасибо.

...