Haskell's typeclasses (which are almost identical to traits) support polymorphic nominal subclassing just fine.

Haskell actually has whole program type inference (unlike Scala, which only does local inference), so fold/map will always return the right type as well, but you also get to not have to put types anywhere if you don't want to (including function signatures).

Scala's main advantage over Haskell is being able to call into Java.