CODEWITHSUNDEEP
f#
Narwe
Narwe

Reputation: 177

F# function to convert a n-dimensional list to 1-dimensional list

I'm attempting a few minor tasks in F# to help get a handle on the language.

I would like to write a function that takes a 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]]], the output would be: [1;2;3;4;5;6;7;8]

For 2-dimensions -> 1-dimension the function is pretty straightforward:

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

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

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

I get the following error when I try to compile:

error FS0001: Type mismatch. Expecting a
'a list list
but given a
'a list
The resulting type would be infinite when unifying ''a' and ''a list'

The issue is here: 

List.collect(fun item -> item) list

There's obviously something wrong with my thinking. What's the proper way to write this sort of function?

Upvotes: 3

Views: 849

Answers (5)

Marcom
Marcom

Reputation: 4751

I Took the nested List idea 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

Upvotes: 0

Brian
Brian

Reputation: 118895

This operation is not well-typed, but here's a sample that works on IEnumerables and returns a 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))

You can also write

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
    ]

which is more general, e.g.

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

EDIT

@Jon Harrop suggested another strategy - create a new type for nested lists:

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)

Upvotes: 3

J D
J D

Reputation: 48697

The F# type system cannot express this. The most common solution is to create a new type representing nested lists.

Upvotes: 2

STO
STO

Reputation: 10658

Sorry, I've a bit knowledge of F# syntax, this is solution in C#, may be it helps:

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;
            }
        }
    }
}

I belive it can be improved in F# by using pattern matching instead of casting and checking for null.

Upvotes: 1

sepp2k
sepp2k

Reputation: 370417

No, the problem is that coalesce takes a list of lists and the compiler doesn't know that List.collect(fun item -> item) list always returns a list of lists (as a matter of fact the compiler can't know that because it's not true). However since that's what you pass in as the argument to coalesce the compiler would need to know that in order to allow that call.

Upvotes: 0

Related Questions