Back to Questions
767
views1
comment
Inconsistent Tail Call Detection?
f#

Hi all,

I'm running into a weird issue with my merge function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

let merge1 (l, r) =
    let merged = Array.zeroCreate ((List.length l) + (List.length r))
    let rec merge index (l, r) = 
        let complete = List.iteri (fun i -> Array.set merged (index + i))
        match (l, r) with
        | (_, []) -> complete l | ([], _) -> complete r
        | (hl::tl, hr::tr) -> 
            let set x = Array.set merged index x; merge (index + 1)
            if hl < hr then set hl (tl, r) else set hr (l, tr)
    merge 0 (l, r)
    List.ofArray merged
 
let merge2 (l, r) =
    let merged = Array.zeroCreate ((List.length l) + (List.length r))
    let rec merge index (l, r) = 
        let complete = List.iteri (fun i -> Array.set merged (index + i))
        match (l, r) with
        | (_, []) -> complete l | ([], _) -> complete r
        | (hl::tl, hr::tr) -> 
            if hl < hr
            then Array.set merged index hl; merge (index + 1) (tl, r)
            else Array.set merged index hr; merge (index + 1) (l, tr)
    merge 0 (l, r)
    List.ofArray merged

Why does merge2 get a tail-call optimization, while merge1 doesn't?

My tests are:

1
2
3

merge1 ([1..10000], [1..10000])

merge2 ([1..10000], [1..10000])

The call to merge1 gives a StackOverflowException, but not merge2.

Thanks!

.

Inner lambdas that return unit don't get tail-call-ified, due to some weird interactions with 'unit' versus 'void'. You can work around it like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let merge1 (l, r) =
    let merged = Array.zeroCreate ((List.length l) + (List.length r))
    let rec merge index (l, r) = 
        let complete = List.iteri (fun i -> Array.set merged (index + i))
        match (l, r) with
        | (_, []) -> complete l; 0 | ([], _) -> complete r; 0 // note, return dummy 0
        | (hl::tl, hr::tr) -> 
            let set x = 
                Array.set merged index x
                merge (index + 1)
            if hl < hr then 
                set hl (tl, r) 
            else 
                set hr (l, tr)
    merge 0 (l, r) |> ignore // ignore dummy
    List.ofArray merged

so that the recursive bit returns 'int' rather than 'unit'.

By on 10/10/2010 3:14 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper