34

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?

0

3 Answers 3

20

There is an inherent difference in Haskell and F# semantics. In Haskell, a function call does not perform any real calculation, but allocates a heap object known as a 'thunk'. It is perfectly okay for a thunk to have a link to itself or another thunk. However, in F#, a function call is an actual call, making expressions 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.

4
  • 2
    AFAIK, Haskell purposefully doesn't have an operational semantics. Aug 28, 2012 at 14:32
  • @dan_waterworth it is impossible to compile without operational semantics defined.
    – permeakra
    Aug 28, 2012 at 19:13
  • 9
    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. Aug 28, 2012 at 20:22
  • 6
    @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, 2012 at 4:19
21

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.

13

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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