Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In F# it is necessary to use the rec keyword. In Haskell there is no need to explicitly tell if a given function is recursive or not.

Given the role of recursion in functional programming, the F# design seems rather odd to me. Is it a good language design decision or does it only exist for historical reason or because of an implementation constraint?

share|improve this question
up vote 13 down vote accepted

There is inherent difference in haskell and f# semantics. In haskell function call does not perform any real calculation, but allocates heap object known as 'thunk'. It is perfectly ok for thunk to have link to itself or other thunk. However, in f# function call is an actual call, making expression like let x = 1 : 2 : x in x invalid - as it requires x to be constructed before 1 : 2 : x is constructed. However, it is still more or less reasonable definition for infinite list, some way to define it should exist. Here lies roots for rec. If you want more, search and read for operational semantics for SML and Haskell - it is different.

share|improve this answer
AFAIK, Haskell purposefully doesn't have an operational semantics. – dan_waterworth Aug 28 '12 at 14:32
@dan_waterworth it is impossible to compile without operational semantics defined. – permeakra Aug 28 '12 at 19:13
The language Haskell doesn't define an operational semantics, but instead provides a denotational semantics. When you construct a compiler, an operational semantics is implicitly defined, but this doesn't mean that it is part of the Haskell language standard. – dan_waterworth Aug 28 '12 at 20:22
@dan_waterworth In practice there is only one implementation and standard of Haskell language: ghc, as well as there is only one F# standard: Microsoft's implementation of it. So theoretically you may be right, but practice is entirely different beast. – permeakra Aug 29 '12 at 4:19

This question has been answered on SO, and it includes some strong historic background for why "rec" is used.

Here is the important quote for posterity:

Functions are not recursive by default in the French CAML family of languages (including OCaml). This choice makes it easy to supercede function (and variable) definitions using let in those languages because you can refer to the previous definition inside the body of a new definition. F# inherited this syntax from OCaml.

share|improve this answer

A recursive let defines a significantly more complicated semantics than a normal one. Therefore, for a sake of simplicity and clean language design, there is a good reason to have both, just the same as having separate let, let* and letrec in Scheme.

Simple let x = y in z is equivalent to ((fun x -> z) y). A recursive let is much more complicated and may involve using a fixed point combinator.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.