Функция F # для преобразования n-мерного списка в 1-мерный список

Question

Я пытаюсь выполнить несколько небольших задач в F #, чтобы помочь разобраться с языком.

Я хотел бы написать функцию, которая принимает n-мерный список и возвращает 1-мерный список, содержащий все элементы из каждого измерения.

Например, если в качестве входных данных использовался следующий трехмерный список: [[[1; 2]; [3; 4]]; [[5; 6]; [7; 8]]], выходные данные быть: [1; 2; 3; 4; 5; 6; 7; 8]

Для двухмерных -> одномерных функция довольно проста:

let coalesce list= List.collect(fun item -> item) list

Вот моя попытка обобщить это в n-измерениях:

let rec coalesce (list, dimension) = 
    if dimension = 1 then list 
    else coalesce (List.collect(fun item -> item) list, dimension - 1)

Я получаю следующую ошибку при попытке компиляции:

ошибка FS0001: несоответствие типов. Ожидая
'список списка
но учитывая
'список
Результирующий тип будет бесконечным при объединении 'a' и '' списка '

Проблема здесь:

List.collect(fun item -> item) list

Очевидно, что-то не так с моим мышлением. Как правильно написать такую ​​функцию?

Answer 1

Эта операция плохо набрана, но вот пример, который работает на IEnumerable s и возвращает list<obj>:

let rec coalesce(list:System.Collections.IEnumerable, dim) =
    [
        if dim=1 then for x in list do yield x
        else
            for x in list do
                match x with
                | :? System.Collections.IEnumerable as s ->
                    yield! coalesce(s, dim-1)
                | _ -> failwith "bad shape"
    ]
printfn "%A" (coalesce([1;2], 1))
printfn "%A" (coalesce([[1;2];[3;4]], 2))
printfn "%A" (coalesce([[[1;2];[3;4]];[[5;6];[7]]], 3))

Вы также можете написать

let rec flatten(list:System.Collections.IEnumerable) =
    [for x in list do
        match x with
        | :? System.Collections.IEnumerable as s -> yield! flatten(s)
        | _ -> yield x
    ]

который является более общим, например

let weird : obj list = [[box [1;2]; box 3]; 4; [box [5;6]; box 7]]
printfn "%A" (flatten weird)

EDIT

@ Джон Харроп предложил другую стратегию - создать новый тип для вложенных списков:

type NestedListElement<'T> = //'
    | L of NestedListElement<'T> list //'
    | V of 'T //'

let rec flatten nlist = 
    [for x in nlist do 
        match x with 
        | L l -> yield! flatten l
        | V v -> yield v
    ] 

let nested = [L[L[V 1;V 2]; V 3]; V 4; L[L[V 5;V 6]; V 7]] 
printfn "%A" (flatten nested) 

Answer 2

Система типа F # не может выразить это. Наиболее распространенным решением является создание нового типа, представляющего вложенные списки.

Answer 3

Извините, я немного знаком с синтаксисом F #, это решение в C #, может быть, оно поможет:

namespace FlatEnumerable
{
    class Program
    {
        static void Main(string[] args)
        {
            var arr = new int[,,] { { { 1, 2 }, { 3, 4 } }, { { 5, 6 }, { 7, 8 } } };
            foreach (var i in arr.Flat())
                Console.WriteLine(i);
        }
    }

    static class Enumerable2
    {
        public static IEnumerable Flat(this IEnumerable source)
        {
            foreach (var item in source)
            {
                var enu = item as IEnumerable;
                if (enu != null)
                    foreach (var c in enu.Flat())
                        yield return c;
                else
                    yield return item;
            }
        }
    }
}

Я верю, что его можно улучшить в F #, используя сопоставление с образцом вместо приведенияи проверка на ноль.

Answer 4

Я взял идею вложенного списка и попытался написать более точную версию:

type NestedListElement<'T> = //'
| L of NestedListElement<'T> list //'
| V of 'T //'

let nested = [L[L[V 1;V 2]; V 3]; V 4; L[L[V 5;V 6]; V 7]] 

let flatten n1 = 
            let rec traverseNestedList nl = match nl with      
                                            | V c -> [c]           
                                            | L a -> List.collect traverseNestedList a
            List.collect traverseNestedList n1 

let res7 = nested |> flatten

Answer 5

Нет, проблема в том, что coalesce принимает список списков, а компилятор не знает, что List.collect(fun item -> item) list всегда возвращает список списков (на самом деле компилятор не может этого знать, потому что это не так правда). Однако, поскольку это то, что вы передаете в качестве аргумента coalesce, компилятор должен знать это, чтобы разрешить этот вызов.