Types as predicates in haskell

I've programmed in Haskell only a few times before, mostly in college - actually in Haskell related languages.  We also did some work with it when we worked on the RudolF whitepaper.

But largely I stayed away because I thought it added unnecessary boiler plate, compared with the Lisp dialect in Clojure (Clojure was my first Lisp).  But I've been doing some scala lately, and I noticed that all the tricky stuff is based on type switching, type inference, and obscure semantics.  So, I figured, I'd go through my freinds old "Real World Haskell" book.

But, suddenly, I realized that Haskell types aren't overengineered when I start using them as predicates.

This is what many strongly typed languages lack.  They give you rigor, but they dont give you strong primitives for leveraging that Rigor to write concise expressive programs.

So, here's a detailed adventure into one of the first non trivial exersizes in "Real World Haskell" which illustrates. this.

One of the more interesting exersizes (if you haven't seen alot of Haskell), was the following:

Write the converse of fromList for the List type: a function that takes a List a and generates a [a].

Where the List type is defined like this:

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

Cons, here, is just a value constructor: It doesn't have any special meaning in haskell.  You could just as easily create the same list like this:

data List2 aa = Cons2 aa (List aa)
    | Nil2
    deriving (Show)

How does the "a" get persisted without an explicit variable binding, and how do we dig it back out?

The above "data" declaration, indeed, is defining a constructor that stores a type of "a", and another type of "List" (where the list has a generic type of a).  To understand how this list works, lets look at a simpler Haskell type.

data BookInfo = Book Int String [String]

The data type in haskell defines a higher level data type, similar to a struct/pojo.    This data type is distinguished by the fact that haskell has primitives for deconstructing the types.  We can do this like so :

bookId (Book id title authors) = id 

Or in a more terse style, like this:

bookId2 (Book id _ _ ) = id

 Or best of all, we can declare our data structure from the beggining, like this:

data Book =Book { 
    id :: Int,
    title :: String,
    authors :: [String] 
}

So, how do we convert between data structures in Haskell? 

The solution is quite obvious, once you realize that data types in haskell natively allow destructuring and switching operations.   The strategy is simple: The List2 data structure is defined for 2 constructors.  The function takes one of those 2 functions as input, and reproduces the atomic unit of the corresponding haskell list (i.e. the [] type), for either function.  So, the first constructor is Cons2, which takes two elements.

fromList List2 (Cons2 aa aas) =  a : fromList2 aa

The second constructor, is Nil2, which is an empty list representation.

fromList Nil2 = []

Putting it all together

fromList (Cons2 aa aas) =  a : fromList2 aa
fromList Nil2 = []