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?

Bill the Lizard
  • 8,408
  • 9
  • 41
  • 92
Simon Bergot
  • 7,930
  • 3
  • 35
  • 54

3 Answers3

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.

Community
  • 1
Chris Pitman
  • 3,426
  • 1
  • 18
  • 21
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.

Community
  • 1
permeakra
  • 495
  • 2
  • 7
  • 2
    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
  • 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. – dan_waterworth Aug 28 '12 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 '12 at 04:19
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.

SK-logic
  • 8,497
  • 4
  • 25
  • 37