Why does Haskell not have records with structural typing?

Question

I have heard Haskell described as having structural typing. Records are an exception to that though as I understand. For example foo cannot be called with something of type HRec2 even though HRec and HRec2 are only nominally different in their fields.

data HRec = HRec { x :: Int, y :: Bool }
data HRec2 = HRec2 { p :: Int, q :: Bool }

foo :: HRec -> Bool

Is there some explanation for rejecting extending structural typing to everything including records?

Are there statically typed languages with structural typing even for records? Is there maybe some debate on this I can read about for all statically typed languages in general?

Answer 1

Haskell has structured types, but not structural typing, and that's not likely to change.*

The refusal to permit nominally different but structurally similar types as interchangeable arguments is called type safety. It's a good thing. Haskell even has a newtype declaration to provide types which are only nominally different, to allow you to enforce more type safety. Type safety is an easy way to catch bugs early rather than permit them at runtime.

In addition to amindfv's good answer which includes ad hoc polymorphism via typeclasses (effectively a programmer-declared feature equivalence), there's parametric polymorphism where you allow absolutely any type, so [a] allows any type in your list and BTree a allows any type in your binary tree.

This gives three answers to "are these types interchangeable?".

1. No; the programmer didn't say so.
2. Equivalent for a specific purpose because the programmer said so.
3. Don't care - I can do the same thing to this collection of data because it doesn't use any property of the data itself.

There's no 4: compiler overrules programmer because they happened to use a couple of Ints and a String like in that other function.

*I said Haskell is unlikely to change to structural typing. There is some discussion to introduce some form of extensible records, but no plans to make (Int,(Int,Int)) count as the same as (Int, Int, Int) or Triple {one::Int, two::Int, three::Int} the same as Triple2 {one2::Int, two2::Int, three2::Int}.

Answer 2

Haskell records aren't really "less structural" than the rest of the type system. Every type is either completely specified, or "specifically vague" (i.e. defined with a typeclass).

To allow both HRec and HRec2 to f, you have a couple of options:

Algebraic types:

Here, you define HRec and HRec2 records to both be part of the HRec type:

data HRec = HRec  { x :: Int, y :: Bool }
          | HRec2 { p :: Int, q :: Bool }

foo :: HRec -> Bool

(alternately, and maybe more idiomatic:)

data HRecType = Type1 | Type2
data HRec = HRec { hRecType :: HRecType, x :: Int, y :: Bool }

Typeclasses

Here, you define foo as able to accept any type as input, as long as a typeclass instance has been written for that type:

data HRec  = HRec  { x :: Int, y :: Bool }
data HRec2 = HRec2 { p :: Int, q :: Bool }

class Flexible a where
   foo :: a -> Bool

instance Flexible HRec where
   foo (HRec a _) = a == 5 -- or whatever

instance Flexible HRec2 where
   foo (HRec2 a _) = a == 5

---

Using typeclasses allows you to go further than regular structural typing -- you can accept types that have the necessary information embedded in them, even if the types don't superficially look similar, e.g.:

data Foo = Foo { a :: String, b :: Float }
data Bar = Bar { c :: String, d :: Integer }

class Thing a where
   doAThing :: a -> Bool

instance Thing Foo where
    doAThing (Foo x y) = (x == "hi") && (y == 0)

instance Thing Bar where
    doAThing (Bar x y) = (x == "hi") && ((fromInteger y) == 0)

We can run fromInteger (or any arbitrary function) to get the data we need from what we have!

Answer 3

I'm aware of two library implementations of structurally typed records in Haskell:

HList is older, and is explained in an excellent paper: Haskell's overlooked object system (free online, but SO won't let me include more links)

vinyl is newer, and uses fancy new GHC features. There's at least one library, vinyl-gl, using it.

I cannot answer the language-design part of your question, though.

Answer 4

To answer your last question, Go and Scalas definitely have structural typing. Some people (including me) would call that "statically unsafe typing", since it implicitly declares all samely- named methods in a program to have the same semantics, which implies "spooky action at a distance", relating code in on source file to code in some library that the program has never seen.

IMO, better to require that the same-named methods to explicitly declare that they conform to a named semantic "model" of behavior.

Yes, the compiler would guarantee that the method is callable, but it isn't much safer than saying:

 f :: [a] -> Int

And letting the compiler choose an arbitrary implementation that may or may not be length.

(A similar idea can be made safe with Scala "implicits" or Haskell (GHC?) "reflection" package.)