Contents

module TreeBuilding

type Record = { RecordId: int; ParentId: int }
type Tree = 
    | Branch of int * Tree list
    | Leaf of int

let addOrAppend key value map =
    let list = defaultArg (Map.tryFind key map) []
    Map.add key (list @ [value]) map

let invalidNode previous x = 
    x.ParentId >= x.RecordId || 
    x.RecordId <> previous + 1

let rec recordsToMap previous map remainder =
    match remainder with
    | [] -> 
        map
    | x::_ when invalidNode previous x ->
        failwith "Invalid record"
    | x::xs ->
        let updatedMap = addOrAppend x.ParentId x.RecordId map
        recordsToMap x.RecordId updatedMap xs

let rec mapToTree map recordId =
    match Map.tryFind recordId map with
    | Some x -> Branch (recordId, x |> List.map (mapToTree map))
    | None   -> Leaf recordId        

let sortRecords records = List.sortBy (fun x -> x.RecordId) records

let buildTree records = 
    match records with
    | [] -> 
        failwith "Empty input"
    | _ ->
        let parentChildrenMap = recordsToMap -1 Map.empty (sortRecords records)
        mapToTree parentChildrenMap 0

Version data entries

38 entries across 38 versions & 1 rubygems

Version	Path
trackler-2.0.5.1	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.5.0	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.4.0	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.9	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.8	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.7	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.6	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.5	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.4	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.3	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.2	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.1	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.3.0	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.2.0	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.1.2	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.1.1	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.1.0	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.0.10	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.0.9	tracks/fsharp/exercises/tree-building/Example.fs
trackler-2.0.0.8	tracks/fsharp/exercises/tree-building/Example.fs