Back to Questions
724
views3
comments
newbie: factorial questions
f#

Hello! I am new to F#. I tried this:

1

let rec f n = if n < 2 then 1 else n * f n-1;;

This pops the stack. I noticed in Expert F# that they have parens around the n-1. So this works:

1

let rec f n = if n < 2 then 1 else n * f (n-1);;

I find this puzzling because that looks like now I'm passing a tuple to f, but f is of type int -> int. If (n-1) is a tuple, then why can it be applied to the function f which takes int -- do single-element tuples implicitly cast to the type of their element? Or is (n-1) not a tuple?

And why did the original crash? Was it trying to evaluate f n before evaluating the remaining -1, thus setting up the infinite loop? So it is an order-of-operations issue?

Thanks,
Brad

.

Parentheses are used for both tuple creation as well as controlling execution order in expressions.

The problem is that function application binds before the arithmetic operators. Your first definition gets evaluated as

1
2
3
4

 

let rec f n = if n < 2 then 1 else n * (f n) - 1;;

This causes an infinite loop and thus pops the stack. Even the one from Expert F# will eventually overflow since it isn't tail recursive, but you overflow the int domain before you overflow the stack. If you use bigints, you can overflow the stack :-)

1
2
3
4
5
6

 

let rec f n = if n < 2I then 1I else n * f (n - 1I);;

f 20000I;;
By on 1/23/2008 4:33 PM ()

Hi Brad,
Yes - it is a problem with the order of evaluation - F# treats the first code as following:

1

let rec f n = if n < 2 then 1 else n * (f n) - 1;;

So it calls the function 'f' recursively with 'n' as the argument (without decrementing it), which explains the stack overflow. In the second case it doesn't treat braces surrounding the expression as a tuple - braces are used for tuples only when there is list of comma-separated values inside.

To experiment a bit you can for example try the following:

1
2
3
4
5
6
7
8
9

 
> let addOne n = n + 1;;
val addOne : int -> int

> addOne 1*2;;
val it : int = 4

> addOne (1 * 2);;
val it : int = 3

Regarding the tuples - I think it makes some sense to think about (n-1) as a tuple with just one value in it. The type of tuple containing two numbers would be int*int, so logically a tuple containing just a single number should have a type int (which is just an integer). Of course, internally types look like a tuples containing just a single value are not represented as tuples.

Hope this explains the problem!
T.

By on 1/23/2008 4:31 PM ()

Thank you, Tomas and LewisBruck.

I found the following definitions on the language specification page (should have looked before posting):

1
2
3
4
5
6
7
8
9

begin expr end                 -- block expression
( expr )                       -- block expression -- is this right?
expr , ... , expr              -- tuple expression
()                             -- the "unit" value
Parenthesized expressions. (e1) is a parentheses expression and evaluates e1 and has the same type as e1.

Tuple expressions. e1,...,en is a tuple expression and is of tuple type (t1 * ... * tn) according to the types of the components. Each expression is evaluated in order, and the expression evaluates to the resulting tuple value.

Binding expressions. let binds in expr is a binding expression and establishes bindings within the local lexical scope of expr and has the same type as e1.  -- what is e1?

Parenthesized expressions. (e1) is a parentheses expression and evaluates e1 and has the same type as e1.

Tuple expressions. e1,...,en is a tuple expression and is of tuple type (t1 * ... * tn) according to the types of the components. Each expression is evaluated in order, and the expression evaluates to the resulting tuple value.

Binding expressions. let binds in expr is a binding expression and establishes bindings within the local lexical scope of expr and has the same type as e1. -- what is e1?</quote> I read this all to mean that it's the commas, not the parentheses as I was thinking, which make an expression a tuple. Indeed: > 3, 4;; val it : int * int = (3, 4) > (3, 4);; val it : int * int = (3, 4) Interesting stuff.

By on 1/24/2008 11:14 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