Back to Questions
2.8k
views8
comments
Recursive function type definition - how to?
f#compiler

No - I'm not asking how to define a recursive function!!! :-)

What I'm trying to do is to define a function type which is self referential - and the compiler is refusing to play ball.

I'm building an application which implements a (potentially complex) state machine to respond to incomong events and will multi-thread with potentially long delays between events. I'm doing it with a continuation passing style in which there's a table of event types and their corresponding event handlers that are small F# functions. Each event handler returns a tuple which includes a variety of state information including the next expected event(s) and the handler to be invoked when one of them is recognised in the input stream.

I have tried to define a function type for the event handler of the following form :

type Handler = Event -> string list -> (bool*string list*Handler*string list)

i.e. function which receives an Event record and a string list and returns a number of things including the Handler to be invoked next. Trouble is that the compiler throws this out with "This type definition involves an immediate cyclic reference through an abbreviation".

At the moment, I'm getting over it by defining the handler to return a string representing the name of the continuation function and maintaining a dictionary that maps function name to function. That works fine, but I'm looking for performance in this application and the repeated dictionary lookups will not help.

I've fiddled around with named types after reading some notes on the new explaining how to use them to create recursive record type definitions, but it doesn't seem to work properly for self-referential function types...

Any suggestions? Please?

.

I don't know what you need this for, but at least I made it compile:

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

type Handler<'a> = 
    Function of (Event<'a> 
                -> string list 
                -> (bool*string list*Handler<'a>*string list))

let rec stop = Function (fun (ev:Event<_>) (bindings:string list) 
                            -> (false, [], stop, [""]))

let (Function f) = stop

(*
type Handler<'a> =
  | Function of
    (Event<'a> -> string list ->
       bool * string list * Handler<'a> * string list)
val stop : Handler<'a>
val f :
  (Event<'a> -> string list -> bool * string list * Handler<'a> * string list)
*)
By on 12/24/2010 12:26 PM ()

Your "definition" of Handler is actually a type abbreviation, which can't be recursive. See [link:stackoverflow.com] for a related question and some potential approaches.

By on 12/7/2010 8:03 AM ()

Hmmm, ok - I understand that for self referential record type definitions, but it doesn't seem to work for self-referential function type definitions. I tried :

type Handler = Handler of (Event -> string list -> (bool*string list*Handler*string list))

which compiles cleanly, but the compiler doesn't seem to recognise it as a function type definition. If I try to compile the following :

let rec c : Handler = (fun (e, sl) -> (True,[],c1,[]))

and c1 : Handler = (fun (e, sl) -> (True,[],c,[]))

then I get the error message : "This function takes too many arguments, or is used in a context where a function is not expected"

I'm rapidly developing a love-hate relationship with F# - I'm an old Lisp programmer and F# obviously has the potential to be a worthy successor, but things like this drive me nuts! :-)

By on 12/7/2010 9:36 AM ()

There are just a few small issues with your code. First of all, you have to apply the Handler constructor on the right hand sides of your assignments (and once you do this, the types can be inferred, so you can remove the annotation from the left hand side). Secondly, your definition of the Handler takes a curried function type 

1

Event -> string list -> bool * string list * Handler * string list

but your recursive definitions are using a tupled argument (that is, your functions have type 

1

Event * string list -> bool * string list * Handler * string list

). Finally, the boolean constant should be in lowercase (true rather than True). Putting it all together:

1
2

let rec c = Handler(fun e sl -> true,[],c1,[])
and c1 = Handler(fun e sl -> true,[],c,[])
By on 12/7/2010 9:52 AM ()

many thanks - I'll try it out soon...

Martin

By on 12/7/2010 10:01 AM ()

OK - got delayed by more immediate concerns, but I've tried it now...

The type declararion and lets compile fine, but the compiler doesn't recognise the result as a functional type and I cannot invoke them.

As an example :

type Handler = Function of (Event -> string list -> (bool*string list*Handler*string list))

let rec stop = Function (fun (ev:Event) (bindings:string list) ->

(false, [], stop, [""]))

Compiles cleanly but:

stop ev list.Empty

Gives the error : "This value is not a function and cannot be applied"

Any suggestions?

Thanks in advance!

By on 12/20/2010 7:48 AM ()
1
2
3
4

let rec stop = Function (fun (ev:Event) (bindings:string list) -> (false, [], stop, [""]))
let (Function f) = stop
f ev list.Empty
By on 12/20/2010 9:20 AM ()

OK - I can't begin to understand the justification for that, but it works...

Thanks!

Martin

By on 12/20/2010 11:07 AM ()

    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