Search code examples
haskelltuplesalgebraic-data-typesvalue-constructor

What is the difference between value constructors and tuples?

It's written that Haskell tuples are simply a different syntax for algebraic data types. Similarly, there are examples of how to redefine value constructors with tuples.

For example, a Tree data type in Haskell might be written as

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

which could be converted to "tuple form" like this:

data Tree a = EmptyTree | Node (a, Tree a, Tree a)

What is the difference between the Node value constructor in the first example, and the actual tuple in the second example? i.e. Node a (Tree a) (Tree a) vs. (a, Tree a, Tree a) (aside from just the syntax)?

Under the hood, is Node a (Tree a) (Tree a) just a different syntax for a 3-tuple of the appropriate types at each position?

I know that you can partially apply a value constructor, such as Node 5 which will have type: (Node 5) :: Num a => Tree a -> Tree a -> Tree a

You sort of can partially apply a tuple too, using (,,) as a function ... but this doesn't know about the potential types for the un-bound entries, such as:

Prelude> :t (,,) 5
(,,) 5 :: Num a => b -> c -> (a, b, c)

unless, I guess, you explicitly declare a type with ::.

Aside from syntactical specialties like this, plus this last example of the type scoping, is there a material difference between whatever a "value constructor" thing actually is in Haskell, versus a tuple used to store positional values of the same types are the value constructor's arguments?

Solution

  • Well, coneptually there indeed is no difference and in fact other languages (OCaml, Elm) present tagged unions exactly that way - i.e., tags over tuples or first class records (which Haskell lacks). I personally consider this to be a design flaw in Haskell.

    There are some practical differences though:

    1. Laziness. Haskell's tuples are lazy and you can't change that. You can however mark constructor fields as strict:

      data Tree a = EmptyTree | Node !a !(Tree a) !(Tree a)

    2. Memory footprint and performance. Circumventing intermediate types reduces the footprint and raises the performance. You can read more about it in this fine answer.

      You can also mark the strict fields with the the UNPACK pragma to reduce the footprint even further. Alternatively you can use the -funbox-strict-fields compiler option. Concerning the last one, I simply prefer to have it on by default in all my projects. See the Hasql's Cabal file for example.

    Considering the stated above, if it's a lazy type that you're looking for, then the following snippets should compile to the same thing:

    data Tree a = EmptyTree | Node a (Tree a) (Tree a)

data Tree a = EmptyTree | Node {-# UNPACK #-} !(a, Tree a, Tree a)

    So I guess you can say that it's possible to use tuples to store lazy fields of a constructor without a penalty. Though it should be mentioned that this pattern is kinda unconventional in the Haskell's community.

    If it's the strict type and footprint reduction that you're after, then there's no other way than to denormalize your tuples directly into constructor fields.