Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Possible to type a function to a particular constructor?
(Ken Overton)
2. Re: Possible to type a function to a particular constructor?
(Brent Yorgey)
3. Re: Possible to type a function to a particular constructor?
(Daniel Fischer)
4. RE: Possible to type a function to a particular constructor?
(Ken Overton)
----------------------------------------------------------------------
Message: 1
Date: Sun, 2 May 2010 09:54:11 -0400
From: Ken Overton <[email protected]>
Subject: [Haskell-beginners] Possible to type a function to a
particular constructor?
To: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="us-ascii"
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?
Thanks,
kov
------------------------------
Message: 2
Date: Sun, 2 May 2010 10:42:42 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Possible to type a function to a
particular constructor?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
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
------------------------------
Message: 3
Date: Sun, 2 May 2010 16:45:50 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Possible to type a function to a
particular constructor?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Sonntag 02 Mai 2010 15:54:11 schrieb Ken Overton:
> 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'"
You can't do that, at least not directly.
>
> 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, V is a data constructor of type String -> T. If
freev :: T -> [V String]
were a correct type signature, you would somewhere have defined a type
constructor V of kind (* -> *), like data V a = Nought | An a.
You can introduce a newtype for variables,
newtype Var = Var String
, change the definition of T,
data T = V Var | A T T | L String T -- or L Var T, don't know what's better
deriving Eq
, and then have
freev :: T -> [Var]
Or you could use a GADT and phantom types,
{-# LANGUAGE GADTs, EmptyDataDecls #-}
data Var
data Compound
data T x where
V :: String -> T Var
A :: T a -> T b -> T Compound
L :: String -> T a -> T Compound
deriving Eq
freev :: T a -> [T Var]
freev v@(V _) = [v]
freev (A t1 t2) = ...
freev (L str t) = ...
, but then
V "x" == A (V "x") (V "y")
would give a type error. Therefore newtype-ing Var would probably be the
better method.
>
> Thanks,
>
> kov
------------------------------
Message: 4
Date: Sun, 2 May 2010 12:10:11 -0400
From: Ken Overton <[email protected]>
Subject: RE: [Haskell-beginners] Possible to type a function to a
particular constructor?
To: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="us-ascii"
Oops, didn't respond to the group --
at any rate, thanks Daniel and Brent!
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 23, Issue 2
****************************************
