CODEWITHSUNDEEP
recursionf#
tonyj444
tonyj444

Reputation: 483

Why do I get different results at runtime based on when I execute my recursive function?

I have a recursive function defined in a module like so:

module Domain:
    let rec myFunc params=
        // do some stuff

    let callFuncWithDefault () = 
        myFunc someDefaultParams

From my main function I can now call this and everything works as expected:

[<EntryPoint>]
let main argv = 
    let result = Domain.callFuncWithDefault()

However, if I change callFuncWithDefault to look like this:

let callFuncWithDefault = myFunc someDefaultParams

I would expect callFuncWithDefault to become the result of calling myFunc with the default params and allow me to access it in the main function like so:

let result = Domain.callFuncWithDefault

However, I find that the main function is never even executed in this scenario - I can only assume that myFunc is recursing infinitely (although I can't see how). What am I missing? Why would this work fine if I defer the execution to the main function but appear to not work if I try and calculate the value in my Domain module?

Edit: The actual code that is causing this problem is presented here:

open System


module Domain = 
    type Position = Position of int*int
    type Queen = {Position : Position}
    type Board = {Queens : Queen list}

    let canTake {Position = position1} {Position = (Position (x2,y2))} =
        let (Position (x1,y1)) = position1
        x1 = x2 || y1 = y2 || Math.Abs x1-x2 = Math.Abs y1-y2

    let canPlaceQueen {Queens = queens} queen = 
        let canTakeQueen = canTake queen
        List.exists canTakeQueen queens
        |>  not

    let rec solutionsForX x {Queens = queens} =
        match x with
        | i when i > 0 && i < 9 ->
            [1..8]
            |>  List.map (fun y -> {Position = Position (x,y)})
            |>  List.filter (canPlaceQueen {Queens = queens})
            |>  List.map (fun q -> {Queens = q::queens})
            |>  List.fold (fun solutions board -> List.append solutions (solutionsForX (x+1) board)) []
        | _     -> [{Queens = queens}]

    let print {Queens = queens} = 
        printfn "%A" queens 

    let findSolutions = solutionsForX 1 {Queens = []}

[<EntryPoint>]
let main argv = 
    printfn "starting..."
    let solutions = Domain.findSolutions
    solutions 
    |>  List.length
    |>  printfn "%i"
    solutions
    |>  List.iter Domain.print
    printfn "press any key to end"
    System.Console.ReadKey() |> ignore
    0 // return an integer exit code

I realise that some of this code (such as the function signature of canTake) are a bit odd - this is purely an exercise in teaching myself f# - but I can't see how any of it causes the problem...

Upvotes: 1

Views: 111

Answers (2)

latkin
latkin

Reputation: 16792

I think I might be able to reproduce your issue. When I run from command line, or start with Ctrl-F5 ("start without debugging"), it runs near-instantly (after removing the printing). When I run with F5 ("debug") it appears to hang before the first line of main is executed. Is that what you are seeing?

Well, it isn't completely hung, it is just running very slowly... Execution without the debugger takes under 1 second on my machine, but with debugger attached it takes over 2 minutes before the first line of main is executed. Have you tried letting it run for that long?

I also notice (in VS 2013) that if I enabled Tools -> Options -> Debugging -> General -> "Use Managed Compatibility Mode" (i.e. use "old" debugger, not the new one released with VS 2013), then the perf problem disappears. I'd suggest trying that, as well.

Upvotes: 2

Grzegorz Sławecki
Grzegorz Sławecki

Reputation: 1787

This simple code works fine for me:

module Domain =
    let rec myFunc ps=
        match ps with
        | [] -> 0
        | h::t -> h + (myFunc t) 

    let callFuncWithDefault () = 
        myFunc [1;2;3;4;5;6]

    let deferred = myFunc [1;2;3;4;5;6]

let result = Domain.callFuncWithDefault()
let result2 = Domain.deferred

printfn "%A" result
printfn "%A" result2

update: If You add main function it is also working:

[<EntryPoint>]
let main argv = 
    let result = Domain.callFuncWithDefault()
    let result2 = Domain.deferred

    printfn "%A" result
    printfn "%A" result2
    1 //just to return something

So it seems that the issue is somewhere inside Your myFunc function.

update 2: Your specific code executes on my machine and gives some result:

[{Queens = [{Position = Position (8,5);}; {Position = Position (7,2);}; {Position = Position (6,4);}; {Position = Position (5,7);}; {Position = Position (4,8);}; {Position = Position (3,6);}; {Position = Position (2,3);}; {Position = Position (1,1);}];};

...

Upvotes: -1

Related Questions