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?

Quadratic

This seems more like a mailing list question, not a SO one – researching language evolution history and rationales isn't really a programming problem. But I'm not really committed to the idea. – Reversal

My wild guess: because the whole point of records is that the order of the fields in the definition isn't important. If it was, you could use a tuple instead. (Of course you might want a data structure where the order in which its parts are defined matters, and allows you to access them by name for convenience. Whether or not that's a good idea or worth the bother of adding another fundamental kind of data type is definitely not a debate for SO though.) – Reversal

I wouldn't see records as an exception. Haskell's typing in general is very nominal, and not structural. – Murat

@Reversal Which mailing list did you have in mind that I would ask on? – Quadratic

@Quadratic None in specific – I was going by experiences with Ruby and Python, where there's an obvious main place of discussion that people who maintain the language itself participate. In general, SO is better for questions of the form "How do I use / accomplish X?", rather than "Why did a third party make design choice X?" – Reversal

Current plans for GHC 7.10 include integrating an extension that works rather similarly to structural records, using the type class mechanism to specify things along the lines of "this type has a field named X with the type Y". – Alverson

haskell.org/mailman/listinfo/haskell-cafe – Allusion

This question doesn't make sense until someone provides a precise definition of "structural typing" for purposes of this question. The only sense of structural typing I know is a loose analogy with functions: a function of type (a -> b -> Bool) -> [a] -> b -> Bool accepts any matching function as its (first) argument. But that's not what people usually mean by "structural" or "duck" typing. – Allusion

@Allusion Structural and duck typing are related but distinct. Duck typing asks "Does it have a quack method?" whereas structural typing asks "Is it comprised of webbed feet, body, wings, head and beak?" Wikipedia: Structural type system – Yap

OCaml has structurally typed records, and it does not consider these record types to be structurally equivalent. You could say this is because it considers field names to be part of the structure of a record type. (This is also how OCaml treats structural equivalence in its object system: names matter.) – Fructificative

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}.

Yap

When you've written three lengthy comments in a row it's time to admit you might be answering. Converted to answer. – Yap

These three answers are the best colloquial descriptions of monomorphism and bounded/parametric polymorphism I've ever read. Thanks! – Tui

It is the mathematics deciding whether two types are equal or not, not the programmer. 2 == Two, no matter how programmers think of. – Beaird

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!

Daisy

I don't think this answers the question. – Eliathan

@Eliathan - to answer the question, I think all you need to say is "haskell doesn't really have structural typing." I added the solutions to show the OP the idiomatic ways to get the same effect in haskell – Daisy

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.

Cacoepy

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.)

Allusion