Understanding Folds. Related blog post: http://fsharpforfunandprofit.com/posts/recursive-types-and-folds-2b/

RecursiveTypesAndFold-2b.fsx

(*
RecursiveTypesAndFold-2b.fsx

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

// ==============================================
// PART 2b - Understanding Folds
// ==============================================


// ==============================================
// FileSystemExampleFold
// ==============================================

module FileSystemExampleFold = 

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

    // ---------------------------------
    // Sample data
    // ---------------------------------

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

    // ---------------------------------
    // define "foldFS"
    // ---------------------------------

    let rec foldFS fFile fDir acc item :'r = 
        let recurse = foldFS fFile fDir 
        match item with
        | File file -> 
            fFile acc file
        | Directory dir -> 
            let newAcc = fDir acc (dir.name,dir.dirSize) 
            dir.subitems |> List.fold recurse newAcc 

    (*
    val foldFS :
        fFile:('r -> File -> 'r) ->
        fDir:('r -> string * int -> 'r) -> 
        // accumulator
        acc:'r -> 
        // input
        item:FileSystemItem -> 
        // return value
        'r
    *)

    // ---------------------------------
    // define and test "totalSize"
    // ---------------------------------

    let totalSize fileSystemItem =
        let fFile acc (file:File) = 
            acc + file.fileSize
        let fDir acc (name,size) = 
            acc + size
        foldFS fFile fDir 0 fileSystemItem 

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

    // ---------------------------------
    // define and test "largestFile"
    // ---------------------------------

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

        let fDir largestSoFarOpt (name,size) = 
            largestSoFarOpt

        // call the fold
        foldFS 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}



// ==============================================
// How can you short circuit a fold?
// ==============================================

// Version 1 - use explicit recursion
module ShortCircuitFold_V1 = 

    /// return the first sum that is bigger than 100 
    let rec firstSumBiggerThan100 sumSoFar listOfInts =
        match listOfInts with
        | [] -> 
            sumSoFar // exhausted all the ints!
        | head::tail -> 
            let newSumSoFar = head + sumSoFar 
            if newSumSoFar > 100 then
                newSumSoFar 
            else
                firstSumBiggerThan100 newSumSoFar tail

    /// test
    [30;40;50;60] |> firstSumBiggerThan100 0  // 120
    [1..3..100] |> firstSumBiggerThan100 0  // 117

// Version 2 - use an "ignore" flag
module ShortCircuitFold_V2 = 

    let firstSumBiggerThan100 listOfInts =

        let folder accumulator i =
            let (ignoreFlag,sumSoFar) = accumulator
            if not ignoreFlag then
                let newSumSoFar = i + sumSoFar 
                let newIgnoreFlag  = newSumSoFar > 100 
                (newIgnoreFlag, newSumSoFar)
            else
                // pass the accumulator along
                accumulator 

        let initialAcc = (false,0)

        listOfInts 
        |> List.fold folder initialAcc  // use fold
        |> snd // get the sumSoFar

    /// test
    [30;40;50;60] |> firstSumBiggerThan100  // 120
    [1..3..100] |> firstSumBiggerThan100  // 117

// Version 3 - hide inside a computation expression
module ImperativeWorkflow =

    open System.Collections.Generic

    type ImperativeResult<'T> = 
      | ImpValue of 'T
      | ImpJump of bool
      | ImpNone 
  
    type Imperative<'T> = unit -> ImperativeResult<'T>

    type ImperativeBuilder() = 
      // When returning a value, we'll use the 'ImpValue' discriminator
      member x.Return(v) : Imperative<_> = 
        (fun () -> ImpValue(v))
      // Expression that doesn't represent any value returns 'ImpNone'
      member x.Zero() = (fun () -> ImpNone)
  
      // Create a delayed imperative computation from a function
      member x.Delay(f:unit -> Imperative<_>) = 
        (fun () -> f()())

      // Combine two delayed computations that may return or jump
      member x.Combine(a, b) = (fun () ->
        match a() with 
        // The computation doesn't have value - evaluate the next
        | ImpNone -> b() 
        // If the computation returned value or called break/return
        // we'll propagate the value representing the result
        | res -> res)
  
      // Execute the imperative computation given as the argument  
      member x.Run<'T>(imp) = 
        // When the computation returns 'ImpJump' it is an indication
        // that 'break' or 'continue' was used incorrectly.
        match imp() with
        | ImpValue(v) -> v
        | ImpJump _ -> failwith "Invalid use of break/continue!"
        | _ -> () // failwith "No value has been returned!"

    let imperative = new ImperativeBuilder()  

    type ImperativeBuilder with 
      // A local helper used when composing iterations of loops
      // in the 'For' and 'While' primitives below.
      member x.CombineLoop(a, b) = (fun () ->
        match a() with 
        // When the last iteration returns a value, propagate the result
        | ImpValue(v) -> ImpValue(v) 
        // The last iteration contained 'break', so we'll 
        // return missing value as the result from the loop
        | ImpJump(false) -> ImpNone
        // When the last iteration didn't contain any special construct
        // or when it ended with 'continue', we'll continue looping
        | ImpJump(true)
        | ImpNone -> b() )
  
      // 'For' and 'While' members that implement the looping constructs
      // are similar as in the previous version, with the exception that they
      // compose iterations using the special 'CombineLoop' primitive
      member x.For(inp:seq<_>, f) =
        let rec loop(en:IEnumerator<_>) = 
          if not(en.MoveNext()) then x.Zero() else
            x.CombineLoop(f(en.Current), x.Delay(fun () -> loop(en)))
        loop(inp.GetEnumerator())
      member x.While(gd, body) = 
        let rec loop() =
          if not(gd()) then x.Zero() else
            x.CombineLoop(body, x.Delay(fun () -> loop()))
        loop()         
  
      // A call to this member is inserted when we use the 'do!' construct. If the 'v'
      // value is either 'break' or 'continue', we will return 'ImpJump' as the result
      member x.Bind(v:Imperative<unit>, f : unit -> Imperative<_>) = (fun () ->
        match v() with
        | ImpJump(kind) -> ImpJump(kind)
        | _ -> f()() )
     
    // Primitives that return the 'ImpJump' value when executed 
    let break = (fun () -> ImpJump(false))
    let continue = (fun () -> ImpJump(true))

module ShortCircuitFold_V3 = 
    
    open ImperativeWorkflow

    /// return the first sum that is bigger than 100 
    let firstSumBiggerThan100 listOfInts =
        let mutable sumSoFar = 0
        imperative { 
            for x in listOfInts do 
                sumSoFar <- x + sumSoFar 
                if sumSoFar > 100 then do! break
        }
        sumSoFar

    /// test
    [30;40;50;60] |> firstSumBiggerThan100  // 120
    [1..3..100] |> firstSumBiggerThan100  // 117