Haskell to F# - declare a recursive types in f#

Question

I am trying to teach my self F# by porting some Haskell Code.

Specifily I am trying to port the Countdown Problem shown here

The Haskell Code is listed here

I am trying to create the following Haskell types in F#:

data Op      = Add | Sub | Mul | Div

data Expr    = Val Int | App Op Expr Expr

In F# I think Op type is defined as follows:

type Op = | Add | Sub | Mul | Div

I am having issues with the Expr type.

How does one create a recursive type? From this SO question it looks like one can not create the Expr type in F#.

Also what is the F# equivalent of 'App' type which apply s the Op type to the Expr type.

If it is not possible to directly port this code, could someone suggest an alternative data structure.

Answer 1

It's not a problem to define recursive types like this; what you can't do is create higher-kinded types, which are parameterized over type constructors (and which are not needed for this example). With any union type definition, you need to separate the constructor name from the constructor parameters with the keyword "of", and the parameters themselves should take the form of a tuple type (i.e. they should be separated by asterisks):

type Op = Add | Sub | Mul | Div
type Expr = Val of int | App of Op * Expr * Expr

Answer 2

@kvb posted the right answer.

See also

http://stackoverflow.com/questions/1378575/f-forward-type-declarations

for how to do things when you do need mutually recursive types.