What you're trying to achieve is called "polymorphic recursion", where the same function is called at a different type within its own body (here, 'a*'a -> t<'a*'a> -> t<'a*'a>) than the type at which it is defined (here, 'a -> t<'a> -> t<'a>). In ML-like languages, you can't do this because it makes type inference undecidable. In F# you can't define a let-bound function which will do this, but you can define a method on a class to do it:

1
2
3
4
5
6

type Conser =
  static member cons<'a> (x:'a) : t<'a> -> t<'a> =
    function
    | Nil -> B(x,Nil)
    | A ps -> B(x,ps)
    | B(y,ps) -> A(Conser.cons<_> (x,y) ps);;

Typically you'll need to explicitly specify the argument and return types of such a function.

Hi,

I have the following definitions :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

type t<'a> =


  | Nil


  | A of t<'a * 'a>


  | B of 'a * t<'a * 'a>


  


let rec cons x = function


  | Nil -> B (x, Nil)


  | A ps -> B (x, ps)


  | B (y, ps) ->  


      A (cons (x,y) ps)

But it won't work : Type mismatch : expecting a t<'a * 'a> but given a t<'a> ... (on the last line)

I cannot see what's wrong...

- ps if of type t<'a * 'a>

- (x, y) is of type ('a * 'a)

- cons (x,y) ps should be t<'a * 'a> ... which is the expected type with the A constructor.

Might someone help me with what I'm doing wrong ?

Thanks a lot