F#函数：将n维列表转换为一维列表

Question

我正在尝试使用F#完成一些小任务，以便更好地掌握这门语言。

我想编写一个函数，该函数接受一个n维列表，并返回一个包含每个维度中所有元素的1维列表。

例如，如果输入是以下3维列表：[[[1;2];[3;4]];[[5;6];[7;8]]]，则输出将为：[1;2;3;4;5;6;7;8]

对于2维到1维的转换，该函数非常简单：

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)

当我尝试编译时，出现以下错误：

error FS0001: 类型不匹配。期望
'a list list
但给出了
'a list
当统一''a'和''a list'时，结果类型将是无限的

问题出在这里：

List.collect(fun item -> item) list

我显然在思考上有些问题。写这种函数的正确方式是什么？

- Narwe

---

相关链接：https://dev59.com/4kbRa4cB1Zd3GeqP0Gpf - kennytm

Answer 1

这个操作没有很好的类型，但是这里有一个在 IEnumerable 上起作用并返回一个 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)

编辑

@Jon Harrop提出了另一种策略 - 为嵌套列表创建一个新类型：

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) 

- Brian

---

此操作未经过良好的类型检查。在F#中出现问题，但其他语言当然没有问题。 - J D

Answer 2

F#类型系统无法表达此内容。最常见的解决方案是创建一个新类型来表示嵌套的列表。

- J D

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#中可以通过使用模式匹配来改进，而不是进行强制类型转换和空值检查。

- STO

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

- Marcom

Answer 5

不，问题在于coalesce需要一个列表的列表，而编译器并不知道List.collect(fun item -> item) list总是返回一个列表的列表（事实上，编译器无法知道这一点，因为它并不正确）。然而，由于这是您传递给coalesce的参数，编译器需要知道才能允许该调用。

- sepp2k

---

哎呀，你说得对。List.collect(fun item -> item)并不总是返回一个列表的列表。我会编辑我的原始帖子。 - Narwe