Parser combinator in Typed Racket: how to define the type constructor for the parser?

Questions & Answers
1

I am trying to translate the nice Haskell tutorial by Stephen Diehl on parser combinators in Typed Racket. However, I am already stuck when trying to define the parametric Parser type.

Haskell: newtype Parser a = Parser { parse :: String -> [(a,String)] }

Racket: (struct (a) Parser ([parse : (-> String (Listof (Values a String)))]))

leads to the error "type name `Values' is unbound" (REPL). The main issue seems to be the tuple definition: neither values or Values works ...

Any suggestions?

2

Hi @yossarian,

After a very quick first look I think you should not use Values in this context, but rather Pairof or List. Both of the following typecheck:

(struct (a) Parser ([parse : (-> String (Listof (Pairof a String)))]))
(struct (a) Parser ([parse : (-> String (Listof (List a String)))]))

The first type is the exact translation of the type in Haskell. For various reasons using a List may sometimes be preferable, but I suggest you go with Pairof until you find a definite advantage to using List.

Values allows defining functions returning multiple values, which in Racket is different from functions returning pairs, lists or tuples of values.

1 Like