recursionf#

F# dynamically generated nested collection function signature cannot be unified


List.collect (fun l ->
        List.collect (fun ll ->
            List.collect (fun lll ->
                List.collect id lll
            ) ll
        ) l
    )  [
    [[[[[1;3]]]]]
    [[[[[2;4]]]]]
]


List.collect (fun ll ->
            List.collect (fun lll ->
                List.collect id lll
            ) ll
        ) [
    [[[[1;3]]]]
    [[[[2;4]]]]
]

I want to have something to dynamically generate the nested function to accecpt different input type signature list like int list list list list list or int list list list list list list to get int list list

But when trying to compose a functioin like this

let rec llf i ll : 'T list = 
    let rec f n =
        if n = 1 then
            fun l -> 
                List.collect id l
        else
            fun ln ->
                List.collect (llf (n - 1)) ln
    f i ll

It says

error FS0001: Type mismatch. Expecting a
    ''T list list'    
but given a
    ''T list'    
The types ''T' and ''T list' cannot be unified.

How could I fix my code?


Solution

  • The challenge posed by type unification may be overcome with a discriminated union. Here, the union case A carries values, whose type is int list, and B marks the levels of nesting for removal, resulting in int list list in the examples below.

    type 'a AB =
    | A of 'a
    | B of 'a AB list
    
    let rec foo xs = [
        match xs with
        | A y -> yield y
        | B ys-> for y in ys do yield! foo y ]
    
    A[1; 2] |> foo
    B[A[1; 2]] |> foo
    B[B[A[1; 2]]] |> foo
    // val it : int list list = [[1; 2]]
    
    B[A[1; 3]; A[2; 4]] |> foo
    B[B[A[1; 3]; A[2; 4]]] |> foo
    B[B[B[A[1; 3]]; B[A[2; 4]]]] |> foo
    B[B[B[B[A[1; 3]]]; B[B[A[2; 4]]]]] |> foo
    B[B[B[B[B[A[1; 3]]]]; B[B[B[A[2; 4]]]]]] |> foo
    // val it : int list list = [[1; 3]; [2; 4]]