Back to Questions
812
views3
comments
Stack overflow error
f#

Hi,

I have written two functions, both of which do essentially the same thing.

*****

(* This excerpt runs in about six seconds. *)

let drop_right n l =

let rec drop_right_helper n' l' =

match n', l' with

|0, _ -> []

|_, [] -> []

|_, h' :: t' -> List.append [h'] (drop_right_helper (List.length t' - n) t')

in

match n, l with

|0, _ -> l

|_, [] -> []

|_, _ -> drop_right_helper n l;;

drop_right 90000 [1 .. 100000];;

*****

(* This excerpt runs for smaller arguments, but overflows the stack for these arguments. *)

let rec take n l =

match n, l with

|0, _ -> []

|_, [] -> []

|_, h :: t -> h :: take (n - 1) t;;

take 90000 [1 .. 100000];;

*****

Any idea why this should be the case? If anything, I would have thought that the other one would have caused a stack overflow.

Thanks in advance for your help.

.

Are you sure you shouldn't be comparing

drop_right 10000 [1..100000]

to

take 90000 [1..100000]

?

Both of those blow up just fine on my computer.

By on 4/24/2009 12:15 PM ()

When crafting recursive functions like this, it's very important that they be tail recursive. Read Chris Smith's explanation.

Here is a tail-recursive version of your second function. It's common to write an inner, recursive version of the function that adds an accumulator parameter. The recursion unwraps with a list reversal since values are added to the list in reverse order:

1
2
3
4
5
6
7
8
9
10

#light
let take n l =
    let rec take' acc n l =
        match n, l with
        |0, _      -> List.rev acc
        |_, []     -> List.rev acc
        |_, h :: t -> take' (h :: acc) (n - 1) t
    take' [] n l

take 90000 [1 .. 100000]
By on 4/23/2009 10:59 AM ()

Hi RayV,

Thanks a lot for your response.

I guess now I need to figure out why the other function did not overflow the stack even though its implementation is not tail recursive.

But thanks for letting me know where to start looking.

By on 4/24/2009 9:10 AM ()

    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