"Composite" algebraic data types in Scala and Haskell

Question

While trying to describe a portion of Sql with Algebraic Data Types in Scala I met a neccessity to create subtraits of the root trait which represents the data type. Since meeting this requirement produced a code that I'm not sure is possible to represent with Haskell's ADTs, and since, in difference to Haskell, ADT is not a native construct to Scala, I am now wondering:

1. Am I right that it is impossible to represent a model such as a type Sql having a "subtype" Statement having a constructor Select in Haskell? (It seems like this may be related).
2. If so, is the term "ADT" applicable to the code that I produced?
3. If it is, does this make Scala actually more powerful than Haskell in that aspect?
4. If it doesn't, what are the reasons for this functionality not to be implemented in Haskell? It makes me think that I might be overcomplicating things in my model

Here's the model I'm talking about:

sealed trait Sql


sealed trait Statement 
  extends Sql

sealed case class Union 
  ( left : Statement, 
    right : Statement ) 
  extends Statement

sealed case class Select
  ( /** other fields don't matter **/
    where : Where )
  extends Statement


sealed trait Where 
  extends Sql

sealed case class And
  ( left : Where,
    right : Where )
  extends Where

sealed case class Or
  ( left : Where,
    right : Where )
  extends Where

sealed case class Equals
  ( /** fields don't matter **/ )
  extends Where

Answer 1

1. No, since your root trait is sealed, it is possible to represent the presented hierarchy as ADTs:

data Sql = Statement Statement | Where Where
        --           ^ This is the *type* called `Statement`
        -- ^ This is the *constructor* called `Statement`

data Statement = Union Statement Statement | Select Where

data Where = And Where Where | Or Where Where | Equals

It is possible in this case, because you are able to enumerate all of the "subclasses" of your data type (Sql in this case), which makes it possible to convert them into ADT constructors. It is only difficult to emulate type hierarchies as ADTs if you want to allow "constructors"/"sub-classes" to be added arbitrarily by the user.

2. The term ADT is never applicable to Scala code since Scala lacks ADTs in the language. However, the classes that you've presented behave similarly to ADTs, so I'd say "close enough."

3 & 4. The languages have different strengths and weaknesses.

Haskell can emulate every Scala language feature, and Scala can emulate every Haskell feature, since both languages are turing complete, and allow for different levels of meta-programming. Haskell does of course have Template Haskell, which allows for anything to be emulated -- you could probably use TH to be able to write Scala code in a Haskell file and have it be compiled as Haskell.

Objects and inheritance are not needed in Haskell, and ADTs are mostly not needed in Scala, so there's no reason to compare the two. Most object-oriented features can also be emulated with simple Haskell type classes and data types, and using module boundaries. ADTs can be emulated in Scala with case classes, and Haskell type classes can be emulated with implicit parameters and implicit object instances.

However, I'd say that it in general is easier to emulate certain Scala features in Haskell, though, because Haskell allows for more "implicit language extensions" than Scala does. What I mean by that is that if you want to emulate Haskell Monads in Scala, you have to write lots of code in the parts that use the Monads, while if you want to emulate, let's say, Scala's delimited continuations or implicit parameters in Haskell, you can simply write a Monad instance (for continuations) or a multi-param type class (for implicit parameters) once for that, and the code that you later write in your actual functions will look very close to the Scala code without much boiler plate. Many if not most of Scala's advanced features do also originate from either Haskell or OCaml, so they are already there and don't need to be translated.

In other words: The complex code required to add the new feature only has to be added in one location in Haskell, after which it can be used in multiple locations very easily, while you often have to add lots of "noise" everywhere in your Scala code if you want to emulate a Haskell feature.

Answer 2

You can imitate the Scala design in Haskell, although Haskell encourages using qualified types and sum types instead of Scala's inheritance and subtyping. Going off my limited knowledge of Scala, I wrote the same stuff in Haskell below.

• Traits are classes
• Case classes are ADTs
• Trait inheritance is class membership
• Trait-typed members are bounded existential types
• Class Typeable is used for downcasting

-- Define traits
class Typeable a => Sql a
class (Typeable a, Sql a) => Statement a
class (Typeable a, Sql a) => Where a

-- Define case classes
data Union  where Union     :: (Statement a, Statement b) => a -> b -> Union deriving (Typeable)
data Select where Select    :: Where a => a -> Select                        deriving (Typeable)          

data And    where And       :: (Where a, Where b) => a -> b -> And           deriving (Typeable)
data Or     where Or        :: (Where a, Where b) => a -> b -> Or            deriving (Typeable)
data Equals where Equals    :: Equals                                        deriving (Typeable)

-- Define subtyping
instance Sql Union
instance Statement Union
instance Sql Select
instance Statement Select
instance Sql And
instance Where And
instance Sql Or
instance Where Or
instance Sql Equals
instance Where Equals

In Haskell, you would probably use sum types instead of the Statement and Where classes.

class Sql a
instance Sql Statement
instance Sql Where

data Statement = Union Statement Statement | Select Where
data Where = And Where Where | Or Where Where | Equals

Answer 3

One possible answer to question 4:

Haskell's type inference (Hindley-Milner) would have problems in the presence of inheritance, so Scala has inheritance but a less powerfull type inferencer.