Back to Questions
3.3k
views2
comments
F# does not support polymorphic (generic) recursion?
f#templates

This code works fine

1
2
3
4
5
6
7

let g y = ()

let rec f x =
  match x with
  | []   -> g 1
  | _::_ -> g true

But the following doesn't, just becuase we changed the order and made it recursive.

1
2
3
4
5

let rec f x =
  match x with
  | []   -> g 1
  | _::_ -> g true
and g y = ()

Anyone ever used Haskell even for really simple examples will know that there is no problem running the following Haskell code.

1
2
3

f []    = g 1
f (_:_) = g True
g y = ()

Haskell doesn't even care about the order of definition anyway, so may not be a fair comparisoin.

But even C++ supports generic recursion with function templates !!

Are there any plans for supporting generic recursion in F#?

This was a rather contrived example, but I've got bitten by F# not supporting polymorphic recursion in more practical programming codes.

.

In recent versions of F# (FSharp.Core 4.3.1.0) the following all compile:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let g y = ()
let rec f x =
    match x with
    | [] -> g 1
    | _::_ -> g true

let rec g' y = ()
    and f' x =
        match x with
        | [] -> g 1
        | _::_ -> g true

let rec f'' x =
        match x with
        | [] -> g 1
        | _::_ -> g true
    and g'' y = ()

g, g' and g'' are all 'a -> unit.

By on 12/11/2016 7:14 PM ()

Hi there,

You must currently fully type annotate the function or method being used at multiple type instantiations within the recursive block, e.g.

1
2
3
4
5
6
7
8
9
10
11
12

 

#light

let rec f x =
  match x with
  | []   -> g 1
  | _::_ -> g true

and g<'a> (y:'a) : unit = ()

Note you must include all of

  • the type paramater declarations
  • any type parameter constraints
  • the argument types
  • the return type

This can be a bit annoying when your code involved #types, whose full type annotation is somewhat longer. We're looking at some additions in this area to ease this.

Thanks

Don

By on 7/11/2008 6:40 PM ()

    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