F # function to convert an n-dimensional list to a one-dimensional list

Question

I am trying to perform some small tasks in F # to help get a language descriptor.

I would like to write a function that takes an n-dimensional list and returns a 1-dimensional list containing all the elements from each dimension.

For example, if the input was the following 3-dimensional list: [[[1; 2]; [3; 4]]; [[5; 6]; [7; 8]]], output be: [1; 2; 3; 4; 5; 6; 7; 8]

For two-dimensionality → 1-dimensional function is quite simple:

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

Here is my attempt to generalize this to n-sizes:

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

When trying to compile the following error:

error FS0001: type mismatch. Waiting for a list of lists
but considering a list
The resulting type would be infinite when combining "a" and "list"

The problem is here:

List.collect(fun item -> item) list

, - . ​​?

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) 

Answer 2

F # . , .

Answer 3

, F #, #, , :

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

No, the problem is that it coalesceaccepts a list of lists, and the compiler does not know that it List.collect(fun item -> item) listalways returns a list of lists (in fact, the compiler cannot know that, since it is not true). However, since you pass the argument coalesce, the compiler must know what in order to resolve this call.

Answer 5

I accepted the idea of ​​a nested list and tried to write a neater version:

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