Type patterns and generic classes in Haskell

Question

I'm trying to understand type patterns and generic classes in Haskell but can't seem to get it.

Could someone explain it in laymen's terms?

In [1] I've read that

"To apply functions generically to all data types, we view data types in a uniform manner: except for basic predefined types such as Float, IO, and →, every Haskell data type can be viewed as a labeled sum of possibly labeled products."

and then Unit, :*: and :+: are mentioned. Are all data types in Haskell automatically versions of the above mentioned and if so how do I figure out how a specific data type is represented in terms of :*:, etc? The users guide for generic classes (ch. 7.16) at haskell.org doesn't mention the predefined types but shouldn't they be handled in every function if the type patterns should be exhaustive?

[1] Comparing Approaches to Generic Programming in Haskell, Ralf Hinze, Johan Jeuring, and Andres Löh

Answer 1

They’re doing this by hand. It’s analogous to the “sum of products” form used in boolean algebra. Since every algebraic datatype is built out of sums and products, the transformation is probably quite similar as in boolean algebra, only in this case they’re extracting the structure and discarding some of the semantics.

Their example is List a, initially defined as

data List a = Nil | Cons a (List a)

but transformed to

data List a = Unit :+: (a :*: (List a)).

I only just skimmed the paper, but I can see some value in extracting the type constructors out of a declaration and building everything out of + and * operators.

Before they use these more generic structure types, they define an isomorphism to show that they are indeed the same. They also include tags with the name of the records and constructors, which I’m going to leave off:

from Nil = Unit
from (Cons x y) = x :*: y
to Unit = Nil
to (x :*: y) = Cons x y

Answer 2

Okay, you may not like hearing this, but you need to hear it. This is a research paper. This is not an instruction manual or cheat sheet on how to get it done. This is a specific exploration of how to do it in a new form that uses what Haskell already gives you (i.e., it's not standard library...yet...it's a way to make one, once, so you don't need to re-do it later).

It's like when you write code to make a stack or a queue - it's an exercise. If you can use it for something real, then more power to you, but in general, it's an illustration or what you could do in the language, not instruction for how you are meant to do it.

This is not to say that the paper is just a toy exercise, and could never be used for anything important, just that their point is to show how you can organize your program so that you're not writing as much boilerplate, or repeating yourself with no savings in effort.

As for the {|...|}(...) stuff, that's the authors' way to talk about both a type, and a value of that type. Specifically, the {|...|}is a way for the authors to represent a type as a value. It's just hand-waving suspended-disbelief thought experimentation. It's a sophisticated way of playing "Let's Pretend". The authors are saying, "Look, Haskell doesn't really allow us to pass a type to a function, so we're going to use this form as a shorthand way to say, "Remember that whole section we just went through to show how to get a representation of a type with all of the Con(structor) and Label types? Well pretend that we did that, and the result for some type a is what we mean by {|a|}." It's a notation to show that the function (encode, decodes, map, showP, et al.) is getting, and using, the type, as well as the value, of some term.

As to your other questions:

1. Wouldn't all pattern matching over Lists break if I start to redefine List? If you redefine it in a way that no longer matches its "current" definition, then of course it would! (Hint: that's the point of the {|...|} form: your function knows what type you're playing with, so it knows how to play with it, too! ;)

2. Is it even possible to redefine data types? Of course it is! (I feel like the #haskell @FAQ answerer, here...) See the Hint, above. :)

I hope that answers your question. If you have more questions, or want to hash it out with a live human being, you can always drop by the IRC channel on freenode (just in case you didn't know why I put that hash mark and 'at' sign in the sentence above). Very friendly, and helpful folks, frustrating to trolls everywhere! :)