CODEWITHSUNDEEP
listrecursionf#
user1120753
user1120753

Reputation: 639

recursive processing list and sublist of list gives a type mismatch

I try to put a branching diagram into lists and sublists layout is

And i want to walk the branching diagram top -> bottom going into each branch but it fails with

Error Type mismatch. Expecting a ('a * 'b list) list but given a 'b list The resulting type would be infinite when unifying ''a' and ''b * 'a list'

Can anybody gives me some ideas what could fix this?

open System

let msgDiagram1 = [ ("msg03",[]); ("msg04",[]) ]
let msgDiagram = [ ("msg01", []); ("msg02", msgDiagram1); ("msg05",[]) ]      

let listToString lst =
    let rec loop acc = function
        | []    -> acc
        | x::xs -> let node = x
                   let sublst = snd(node)                      
                   if not ( sublst = List.empty ) then                        
                        loop "" sublst
                   else 
                        loop (acc + (string x)) xs

    loop "" lst

printfn "%A" (listToString msgDiagram)

Upvotes: 2

Views: 261

Answers (1)

pad
pad

Reputation: 41290

Since msgDiagram1 and msgDiagram have different types, you cannot use the same loop function on them. One quick fix is to process differently on msgDiagram1:

let listToString lst =
    let rec loop acc = function
        | [] -> acc
        | (lbl, diag)::xs ->
            match diag with
            | [] -> loop (acc + string lbl + "\n") xs
            | _ ->
                let s = diag |> List.map (fun (label, _) -> "..." + label) 
                             |> String.concat "\n"
                loop (acc + string lbl + "\n" + s + "\n") xs
    loop "" lst

You chose a wrong data structure for the job; therefore, you cannot represent more than 2 levels of diagrams and these levels are forced to have different types. The right tool to use here is recursive tree data structure:

type Diagram = Branch of string * Diagram list

Now above values can be defined using the same type Diagram list:

let msgDiagram1 = [ Branch ("msg03",[]); Branch ("msg04", []) ]
let msgDiagram = [ Branch ("msg01", []); Branch ("msg02", msgDiagram1); 
                   Branch ("msg05", []) ]

and listToString can be rewritten to process Diagram list recursively in one batch.

Upvotes: 4

Related Questions