Generic tree type. Related blog post: http://fsharpforfunandprofit.com/posts/recursive-types-and-folds-3b/

RecursiveTypesAndFold-3b-tree.fsx

(*
RecursiveTypesAndFold-3b-tree.fsx

Related blog post: http://fsharpforfunandprofit.com/posts/recursive-types-and-folds-3b/
*)

// ==============================================
// PART 3b - Generic tree type
// ==============================================

// ==============================================
// Model tree after original FileSystem design
// ==============================================

module FileSystem_Original = 

    type FileSystemItem =
        | File of FileInfo
        | Directory of DirectoryInfo
    and FileInfo = {name:string; fileSize:int}
    and DirectoryInfo = {name:string; dirSize:int; subitems:FileSystemItem list}


// ==============================================
// Tree implementation
// ==============================================

type Tree<'LeafData,'INodeData> =
    | LeafNode of 'LeafData
    | InternalNode of 'INodeData * Tree<'LeafData,'INodeData> seq

module Tree = 

    let rec cata fLeaf fNode (tree:Tree<'LeafData,'INodeData>) :'r = 
        let recurse = cata fLeaf fNode  
        match tree with
        | LeafNode leafInfo -> 
            fLeaf leafInfo 
        | InternalNode (nodeInfo,subtrees) -> 
            fNode nodeInfo (subtrees |> Seq.map recurse)
(*
val cata :
  fLeaf:('LeafInfo -> 'r) ->
  fNode:('INodeData -> 'r seq -> 'r) ->
  tree:Tree<'LeafInfo,'NodeInfo> -> 
  'r
*)

    let rec fold fLeaf fNode acc (tree:Tree<'LeafData,'INodeData>) :'r = 
        let recurse = fold fLeaf fNode  
        match tree with
        | LeafNode leafInfo -> 
            fLeaf acc leafInfo 
        | InternalNode (nodeInfo,subtrees) -> 
            // determine the local accumulator at this level
            let localAccum = fNode acc nodeInfo
            // thread the local accumulator through all the subitems using Seq.fold
            let finalAccum = subtrees |> Seq.fold recurse localAccum 
            // ... and return it
            finalAccum 
(*
val fold :
  fLeaf:('r -> 'LeafData -> 'r) ->
  fNode:('r -> 'INodeData -> 'r) ->
  acc:'r -> 
  tree:Tree<'LeafData,'INodeData> -> 
  'r
*)

    let rec map fLeaf fNode (tree:Tree<'LeafData,'INodeData>) = 
        let recurse = map fLeaf fNode  
        match tree with
        | LeafNode leafInfo -> 
            let newLeafInfo = fLeaf leafInfo
            LeafNode newLeafInfo 
        | InternalNode (nodeInfo,subtrees) -> 
            let newSubtrees = subtrees |> Seq.map recurse 
            let newNodeInfo = fNode nodeInfo
            InternalNode (newNodeInfo, newSubtrees)
(*
val map :
  fLeaf:('LeafData -> 'a) ->
  fNode:('INodeData -> 'b) ->
  tree:Tree<'LeafData,'INodeData> -> 
  Tree<'a,'b>
*)

    let rec iter fLeaf fNode (tree:Tree<'LeafData,'INodeData>) = 
        let recurse = iter fLeaf fNode  
        match tree with
        | LeafNode leafInfo -> 
            fLeaf leafInfo
        | InternalNode (nodeInfo,subtrees) -> 
            subtrees |> Seq.iter recurse 
            fNode nodeInfo
            
// ==============================================
// Refactor FileSystem to use Tree 
// ==============================================

module FileSystem_Tree = 

    type FileInfo = {name:string; fileSize:int}
    type DirectoryInfo = {name:string; dirSize:int}

    type FileSystemItem = Tree<FileInfo,DirectoryInfo>

    let fromFile (fileInfo:FileInfo) = 
        LeafNode fileInfo 

    let fromDir (dirInfo:DirectoryInfo) subitems = 
        InternalNode (dirInfo,subitems)
   
    // ----------------------------
    // Sample data
    // ----------------------------

    let readme = fromFile {name="readme.txt"; fileSize=1}
    let config = fromFile {name="config.xml"; fileSize=2}
    let build  = fromFile {name="build.bat"; fileSize=3}
    let src = fromDir {name="src"; dirSize=10} [readme; config; build]
    let bin = fromDir {name="bin"; dirSize=10} []
    let root = fromDir {name="root"; dirSize=5} [src; bin]

    // ----------------------------
    // Define and test "totalSize"
    // ----------------------------

    let totalSize fileSystemItem =
        let fFile acc (file:FileInfo) = 
            acc + file.fileSize
        let fDir acc (dir:DirectoryInfo)= 
            acc + dir.dirSize
        Tree.fold fFile fDir 0 fileSystemItem 

    readme |> totalSize  // 1
    src |> totalSize     // 16 = 10 + (1 + 2 + 3)
    root |> totalSize    // 31 = 5 + 16 + 10

    // ----------------------------
    // Define and test "largestFile"
    // ----------------------------

    let largestFile fileSystemItem =
        let fFile (largestSoFarOpt:FileInfo option) (file:FileInfo) = 
            match largestSoFarOpt with
            | None -> 
                Some file                
            | Some largestSoFar -> 
                if largestSoFar.fileSize > file.fileSize then
                    Some largestSoFar
                else
                    Some file

        let fDir largestSoFarOpt dirInfo = 
            largestSoFarOpt

        // call the fold
        Tree.fold fFile fDir None fileSystemItem

    readme |> largestFile  
    // Some {name = "readme.txt"; fileSize = 1}

    src |> largestFile     
    // Some {name = "build.bat"; fileSize = 3}

    bin |> largestFile     
    // None

    root |> largestFile    
    // Some {name = "build.bat"; fileSize = 3}