12

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?

Improve this question
10
  • 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. Commented Jan 12, 2014 at 5:26
  • 9
    I wouldn't see records as an exception. Haskell's typing in general is very nominal, and not structural. Commented Jan 12, 2014 at 6:14
  • 1
    haskell.org/mailman/listinfo/haskell-cafe Commented Jan 13, 2014 at 4:23
  • 1
    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. Commented Jan 13, 2014 at 4:29
  • 4
    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.) Commented Mar 26, 2014 at 14:08

4 Answers 4

Reset to default
18

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

When you've written three lengthy comments in a row it's time to admit you might be answering. Converted to answer.
These three answers are the best colloquial descriptions of monomorphism and bounded/parametric polymorphism I've ever read. Thanks!
It is the mathematics deciding whether two types are equal or not, not the programmer. 2 == Two, no matter how programmers think of.
11

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!

Improve this answer

2 Comments

I don't think this answers the question.
@luqui - 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
2

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.

Improve this answer

Comments

1

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.