Alex Rivera | Logout

Please confirm or correct my "English interpretation" of this Haskell code snippet

Asked 2009-04-22T04:48:41.677
14

I'm a C# developer who is working through "Real World Haskell" in order to truly understand functional programming, so that when I learn F#, I'll really grok it and not just "write C# code in F#", so to speak.

Well, today I came across an example which I thought I understood 3 different times, only to then see something I missed, update my interpretation, and recurse (and curse too, believe me).

Now I believe that I do actually understand it, and I have written a detailed "English interpretation" below. Can you Haskell gurus please confirm that understanding, or point out what I have missed?

Note: The Haskell code snippet (quoted directly from the book) is defining a custom type that is meant to be isomorphic to the built in Haskell list type.

The Haskell code snippet

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

EDIT: After some responses, I see one misunderstanding I made, but am not quite clear on the Haskell "parsing" rules that would correct that mistake. So I've included my original (incorrect) interpretation below, followed by a correction, followed by the question that still remains unclear to me.

EDIT: Here is my original (incorrect) "English interpretation" of the snippet

  1. I am defining a type called "List".
  2. The List type is parameterised. It has a single type parameter.
  3. There are 2 value constructors which can be used to make instances of List. One value constructor is called "Nil" and the other value constructor is called "Cons".
  4. If you use the "Nil" value constructor, then there are no fields.
  5. The "Cons" value constructor has a single type parameter.
  6. If you use the "Cons" value constructor, there are 2 fields which must be provided. The first required field is an ins
c# haskell types f# algebraic-data-types
Edit
Report

2 Answers

4

Analogies are usually lacking in all sorts of ways, but since you know C# I thought this might be helpful.

This is how I would describe the List a definition in C#, maybe this clears some things up (or more likely, confuses you even more).

class List<A>
{
}

class Nil<A> : List<A>
{
    public Nil() {}
}

class Cons<A> : List<A>
{
    public A Head;
    public List<A> Tail;

    public Cons(A head, List<A> tail)
    {
        this.Head = head;
        this.Tail = tail;
    }
}

As you can see;

  • the List type has a single type parameter (<A>),
  • the Nil constructor doesn't have any parameters,
  • and the Cons constructor has two parameters, a value head of type A and a value tail of type List<A>.

Now, in Haskell the Nil and Cons are just constructors for the List a data type, in C# they are also types in and of themselves, so that's where the analogy fails.

But I hope this gives you some intuitive sense of what the different A's represent.

(And please do comment on how this horrible comparison doesn't do justice to Haskell's data types.)

answered 2009-04-22T20:49:34.330
3

Yeah the data syntax is a little confusing, because it puns names and types and doesn't really make a syntactic distinction between them. In particular, in a constructor definition like:

Cons a (List a)

The first word is the name of the constructor; every other word is the name of some predeclared type. So both a and List a are already in scope (the a was brought in to scope by the a in "data List a"), and you're saying that those are the types of the parameters. Their role might be better demonstrated by stating the same thing using record syntax:

Cons { headL :: a, tailL :: List a }

I.e. a value of type List Int, if it was constructed with the Cons constructor, has two fields: an Int and a List Int. If it was constructed with Nil, it has no fields.

answered 2009-04-22T14:58:31.443

Your Answer