Why is everything a Functor and what about Monomorphic types

Question

I'm building an optimizer for various function calls in haskell, here's my AST

 data Expr = ExprCall { _fname :: Text, _fparams :: [Expr] }
              | ExprVar { _var :: Text }
              | ExprNat { _nat :: Int }

And here is an example of syntax, mod and random are external functions and their semantics are opaque to haskell.

mod(random(), 10)

All it has is the AST representation of the syntax, for the example above that would be:

ExprCall "mod" [ExprCall "random" [], ExprNat 10]

I have a lot of passes that have type Expr->Expr and I have a function called descend which traverses the AST and applies a pass to every Expr. Here is my descend function

{- # LANGUAGE RecordWildCards #-}
descend :: (Expr -> Expr) -> Expr -> Expr
descend f ExprCall   { .. } = ExprCall _fname $ map f _fparams
-- Base expressions
descend f other = f other

Now I realize this is exacatly what Data.Traversable does and I wanted to make my Expr an instance of that, however, all typeclasses in that hierarchy Functor, Foldable, Traversable etc only accept kinds * -> *. Why?

Is there some way I can make my Expr to a (* -> *) so that it makes sense logically? Alternatively, is there a way to have monomorphic traversables?

What are the advantages of declaring data as data Expr a compared to what I have, data Expr?

Answer 1

Polymorphism for these classes has some benefits: the types are more descriptive, and they prevent certain implementation mistakes.

The main reason for both of these advantages is that there are generally much fewer implementations of polymorphic types than more specialized ones. If we exclude exceptions and infinite loops, there are really only two ways to implement fmap :: (a -> b) -> Maybe a -> Maybe b, and one is a constant function, so only the other is really sensible:

fmap f (Just a) = Just (f a)
fmap f Nothing = Nothing

-- or

fmap f (Just _) = Nothing
fmap f Nothing = Nothing

In contrast, the type (Int -> Int) -> Maybe Int -> Maybe Int technically tells us very little about what such a function does. In particular, one can forget to use the first argument, which is not too far-fetched a mistake to make IMO:

fmap :: (Int -> Int) -> Maybe Int -> Maybe Int
fmap f (Just a) = Just a
fmap f Nothing = Nothing