[Haskell-beginners] Possible to type a function to a particular constructor?

[Brent Yorgey]

On Sun, May 02, 2010 at 09:54:11AM -0400, Ken Overton wrote:
> 
> Hi fellow beginners (and everyone else),
> 
> As an exercise, I'm implementing a simple, untyped lambda calculus:
> 
> -- a term is a variable, an application, or abstraction (lambda)
> data T = V String | A (T) (T) | L String (T)
> 	deriving (Eq)
> 
> So I'm writing a function that returns a list of all the free variables in a term and descendants. I can only get it to compile with type:
> 
>     freev :: T -> [T]
> 
> It'd be nice for the type of that function to be restricted to just variables like:
> 
>     freev :: T -> [V String] -- compile error: "Not in scope: type constructor or class `V'"
> 
> Is there some way to express that?  The error seems to suggest maybe haskell could do it if I'd just say it correctly.  I mean, isn't "V String" a type constructor?

No, there's no way to do that.  V is a data constructor, not a type
constructor; V String is not a type.  There's no way to express
"values of such-and-such a type but restricted only to things built
with such-and-such a constructor" without resorting to fancy type
tricks, which you don't really need.

Instead, I would expect freev to have the type

  freev :: T -> [String]

It's much more usual to have freev just return the *names* of all the
free variables.

-Brent