You can absolutely write type-safe higher order functions without generics. You can't write generic higher order functions, but that's a tautology.

Also higher-order functions are a moot point. Higher-order functions give you convenience, but no increase in expressive power (defunctionalization is an homomorphism).

Of course, generics give you a true increase in power.