[Haskell-beginners] Nullable attribute of a language grammar howto

[Daniel Fischer]

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
>