Am Dienstag, 2. September 2008 18:30 schrieb Larry Evans:
On 09/01/08 13:21, Daniel Fischer wrote:
Jason beat me, but I can elaborate on the matter:
Am Montag, 1. September 2008 18:22 schrieb Larry Evans:
expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type) {- expr2null GramExpr returns a GramNull expression which indicates whether the GramExpr can derive the empty string. -}
[snip]
expr2null :: forall inp_type var_type. GramExpr inp_type var_type -> GramNull inp_type var_type
Cheers, Daniel
Thanks Jason and Daniel. It works beautifully.
Now, I'm trying to figure how to use Functor to define expr2null (renamed to gram2null in 1st attachement). My motivation for this goal is I've read that a Functor as defined in category theory is somewhat like a homomorphism, and gram2null is, AFAICT, a homomorphism between GramExpr adn NullExpr.
You can't do that :( We have class Functor f where fmap :: (a -> b) -> f a -> f b So a Functor is a type constructor, f, which takes one type, a, as argument and from that constructs another type, f a, in such a way that for any function fun :: a -> b you can define a function (fmap fun) :: f a -> f b (generically, i.e. you can't use any special properties of fun). The type of expr2null is GramExpr a b -> GramNull a b, so there are different type constructors applied to b on the two sides of the arrow, (GramExpr a) on the left and (GramNull a) on the right, while fmap requires the same type constructor applied to possibly different types. You can make (GramExpr inp_type) a Functor like instance Functor (GramExpr i) where fmap _ GramOne = GramOne fmap _ (GramInp i) = GramInp i fmap f (GramVar v) = GramVar (f v) fmap f (a :| b) = (fmap f a) :| (fmap f b) fmap f (a :>> b) = (fmap f a) :>> (fmap f b) analogously for NullableExpr, but that's something entirely different (maybe useful, maybe not).
However, I can't figure how to do it. The 2nd attachment how an example with comments which, I hope, explains where I'm stuck.
Perhaps you're looking for something like data Alg ty = Op0_0 | Op0_1 | Op1_0 ty | Op2_0 (Alg ty) (Alg ty) deriving (Show) instance Functor Alg where fmap _ Op0_0 = Op0_0 fmap _ Op0_1 = Op0_1 fmap f (Op1_0 v) = Op1_0 (f v) fmap f (Op2_0 a b) = Op2_0 (fmap f a) (fmap f b) ?
I've also looked at happy's sources and found no use of Functor; so, maybe haskell's Functor is not similar to category theory's Functor.
It is, with the restriction that Haskell only has Endofunctors, where the source category and the target category are the same, the category of Haskell types where the morphisms are functions between those types (glossing over the fact that this is not quite accurate).
Any help would be appreciated.
-regards, Larry