Int
Char
Float
This is a good start, but we might want to allow the user to create some types.
data ? = ?' <something>* (| ?'' <something>* )*
Okay, I'm abusing several notations pretty badly ... let me explain what we have here.
data is a keyword that tells the compiler that the user is defining a new type.
? is a place holder for whatever the new type name is going to be ... the user needs to fill this in for it to compile.
?' and ?'' (and even ?''' etc) are different constructors for this type. We could just construct the type with a function by the same name as the type, but that's less interesting than letting the user provide many different possible constructor names. Specifically, because some of the constructor names might take different parameters.
<something> is a preexisting type. So we might see something like:
data Circle = Circle Float
data VennDiagram = Venn Circle Circle
The * on <something> indicates that we might have multiple somethings (or maybe zero) *and* they might be different somethings. In the above example we have a constructor "Venn" that takes two circles as parameters.
The ( ... )* indicates that we might have multiple constructors after the first one or we might have zero more constructs; each one following the same rules as the initial one.
Now we have primitive types and user defined types ... what about the types of functions?
<something> -> <something>
Okay, maybe an example that looks a little bit less pointy.
Int -> Int
Okay, cool. This is a function that takes an Int and returns another Int. So maybe negate or absolute value or something. However we can make things a little bit more complex.
Int -> Int
Int -> Int -> Int
Int -> (Int -> Int) -> Int
There's a mathematical process known as currying which basically states that a function that takes multiple parameters is equivalent to a function that takes a parameter and then returns a function that takes the next parameter and so on.
Additionally, the arrow (->) is right associative which means that
Int -> Int -> Int <=> Int -> (Int -> Int)
And the upshot of that is that if you want to write a function type that indicates you take a function as a parameter you need parens ... so
Int -> (Int -> Int) -> Int
That function type indicates a function that takes an integer, then a function that takes an integer and returns an integer, and finally returns an integer.
The simply typed language works, but it leaves something to be desired. If you want an array or a list or some other container, then you have to make it by hand ... once for each data type you want to use it with. Hardly ideal.
So how about parametric polymorphism. That means that instead of writing new data types that take specific existing data types, we get to write new data types that take arbitrary data types.
data List a = Cons a (List a) | Nil
The 'a' can be any data type ... this allows us to write functions that can operate over a List of any type.
List a -> Int
So that's probably a function that returns the number of items in the list. And we can also do things like this:
List Int -> Int
This one is probably a function that returns the sum or product of all the Ints in a List of Ints. This can also be generalized some.
List a -> ( a -> b ) -> List b
This function takes a List of as and a function that can convert an a into a b ... err and a function that can convert an "a" into a "b" and then returns a list of "b"s. This is called map or select in many different languages.
What if we do something like this:
Pair a b -> (c -> c) -> Pair a b
This function takes a Pair type which contains one item of type 'a' and one item of type 'b' and then it takes a function from 'c' to 'c' and finally returns another Pair (after running the function over both the items in the Pair). It seems about right, but it won't work in Haskell because the type checker will assume that 'c' is equal to 'a' (or actually 'b' if the first thing you do in the function is try to convert the second item in the Pair). The type checker will then signal an error because you try to feed a function that takes an 'a' an item that has type 'b'.
To get around this you have to do something like this:
forall c . Pair a b -> ( c -> c ) -> Pair a b
This invokes Universal Quantification, which allows the type checker to realize that even though 'c' is going to be equal to 'a' it can also be equal to 'b'. The whole point of going to parametric polymorphism was to allow functions that take arbitrary types after all, but the type checking algorithm has to be different if you're going to allow this type of higher order function type checking. In the Glasgow Haskell Compiler (GHC), this option has to be activated using the following pragma:
{-# LANGUAGE Rank2Types #-}
or
{-# LANGUAGE RankNTypes #-}
Alternatively, you can also activate this compiler extension by using a command line flag.
Other Haskell compilers might not support this option ... I don't really keep up with what all of them support, so you'll have to check in on it if you're looking into a compiler other than the Glasgow one.
So, parametric polymorphism is pretty nice, but sometimes we just want to do something specific when we have a specific type. This is where type classes come in.
class X a where
methodName :: a -> a
instance X Circle where
methodName a = a
instance X Square where
methodName a = a
(X a) => a -> a
The class introduces a type class.
The instance introduces a specific instance of this type class.
The (X a) => ... indicates that you have a function that can take a parameter of any 'a' as long as that 'a' also is an instance of the type class 'X'.
Okay, so I'm basically going to leave off here because things start to get really complicated. Type classes bring up the issue of kinds (the type of your types). And they also bring up the issue of "what if I want to do ..." to which the answer is "you can't ... unless you activate this compiler extension". As far as I can tell the Haskell type classes in the standard are actually pretty simple (but allow powerful things to happen). I haven't actually read the standard, but I'm just kind of inferring based off of all the compiler extensions GHC has.
The story that happens again and again with type systems is along the lines of, "why doesn't this work?" And the answer is usually, "yes that makes perfect sense, but we didn't write the algorithm that way because it's hard or impossible or we wanted it to be easy for other implementations to match our specification or etc." With Haskell it looks like they wanted to make the type system interesting and powerful, but also relatively easy to implement so that there would be lots of different implementations. With GHC it looks like they took the liberty to implement a bunch of other interesting but difficult features on top of what already exists within Haskell.
I hope to cover a bunch of these extensions later (starting with what's available with type classes). And yes this means that I'm going to be bumping into monads eventually ... although I'm going to try to avoid yet another "monads are really like ..." post. The internet already has enough of those and I actually wanted to start a series like that before I realized what I had done and pulled the plug. The gist, btw, is that monads are an abstract algebraic concept that is sort of related to Haskell because Haskell is only pure functions. If you want to learn what a monad is, learn category theory. If you want to learn how to use monads in Haskell, read a bunch of blog posts.
data VennDiagram = Venn Circle Circle
The * on <something> indicates that we might have multiple somethings (or maybe zero) *and* they might be different somethings. In the above example we have a constructor "Venn" that takes two circles as parameters.
The ( ... )* indicates that we might have multiple constructors after the first one or we might have zero more constructs; each one following the same rules as the initial one.
Now we have primitive types and user defined types ... what about the types of functions?
<something> -> <something>
Okay, maybe an example that looks a little bit less pointy.
Int -> Int
Okay, cool. This is a function that takes an Int and returns another Int. So maybe negate or absolute value or something. However we can make things a little bit more complex.
Int -> Int
Int -> Int -> Int
Int -> (Int -> Int) -> Int
There's a mathematical process known as currying which basically states that a function that takes multiple parameters is equivalent to a function that takes a parameter and then returns a function that takes the next parameter and so on.
λ x y z . x y z <=> λ x . λ y . λ z . x y z
Additionally, the arrow (->) is right associative which means that
Int -> Int -> Int <=> Int -> (Int -> Int)
And the upshot of that is that if you want to write a function type that indicates you take a function as a parameter you need parens ... so
Int -> (Int -> Int) -> Int
That function type indicates a function that takes an integer, then a function that takes an integer and returns an integer, and finally returns an integer.
The simply typed language works, but it leaves something to be desired. If you want an array or a list or some other container, then you have to make it by hand ... once for each data type you want to use it with. Hardly ideal.
So how about parametric polymorphism. That means that instead of writing new data types that take specific existing data types, we get to write new data types that take arbitrary data types.
data List a = Cons a (List a) | Nil
The 'a' can be any data type ... this allows us to write functions that can operate over a List of any type.
List a -> Int
So that's probably a function that returns the number of items in the list. And we can also do things like this:
List Int -> Int
This one is probably a function that returns the sum or product of all the Ints in a List of Ints. This can also be generalized some.
List a -> ( a -> b ) -> List b
This function takes a List of as and a function that can convert an a into a b ... err and a function that can convert an "a" into a "b" and then returns a list of "b"s. This is called map or select in many different languages.
What if we do something like this:
Pair a b -> (c -> c) -> Pair a b
This function takes a Pair type which contains one item of type 'a' and one item of type 'b' and then it takes a function from 'c' to 'c' and finally returns another Pair (after running the function over both the items in the Pair). It seems about right, but it won't work in Haskell because the type checker will assume that 'c' is equal to 'a' (or actually 'b' if the first thing you do in the function is try to convert the second item in the Pair). The type checker will then signal an error because you try to feed a function that takes an 'a' an item that has type 'b'.
To get around this you have to do something like this:
forall c . Pair a b -> ( c -> c ) -> Pair a b
This invokes Universal Quantification, which allows the type checker to realize that even though 'c' is going to be equal to 'a' it can also be equal to 'b'. The whole point of going to parametric polymorphism was to allow functions that take arbitrary types after all, but the type checking algorithm has to be different if you're going to allow this type of higher order function type checking. In the Glasgow Haskell Compiler (GHC), this option has to be activated using the following pragma:
{-# LANGUAGE Rank2Types #-}
or
{-# LANGUAGE RankNTypes #-}
Alternatively, you can also activate this compiler extension by using a command line flag.
Other Haskell compilers might not support this option ... I don't really keep up with what all of them support, so you'll have to check in on it if you're looking into a compiler other than the Glasgow one.
So, parametric polymorphism is pretty nice, but sometimes we just want to do something specific when we have a specific type. This is where type classes come in.
class X a where
methodName :: a -> a
instance X Circle where
methodName a = a
instance X Square where
methodName a = a
(X a) => a -> a
The class introduces a type class.
The instance introduces a specific instance of this type class.
The (X a) => ... indicates that you have a function that can take a parameter of any 'a' as long as that 'a' also is an instance of the type class 'X'.
Okay, so I'm basically going to leave off here because things start to get really complicated. Type classes bring up the issue of kinds (the type of your types). And they also bring up the issue of "what if I want to do ..." to which the answer is "you can't ... unless you activate this compiler extension". As far as I can tell the Haskell type classes in the standard are actually pretty simple (but allow powerful things to happen). I haven't actually read the standard, but I'm just kind of inferring based off of all the compiler extensions GHC has.
The story that happens again and again with type systems is along the lines of, "why doesn't this work?" And the answer is usually, "yes that makes perfect sense, but we didn't write the algorithm that way because it's hard or impossible or we wanted it to be easy for other implementations to match our specification or etc." With Haskell it looks like they wanted to make the type system interesting and powerful, but also relatively easy to implement so that there would be lots of different implementations. With GHC it looks like they took the liberty to implement a bunch of other interesting but difficult features on top of what already exists within Haskell.
I hope to cover a bunch of these extensions later (starting with what's available with type classes). And yes this means that I'm going to be bumping into monads eventually ... although I'm going to try to avoid yet another "monads are really like ..." post. The internet already has enough of those and I actually wanted to start a series like that before I realized what I had done and pulled the plug. The gist, btw, is that monads are an abstract algebraic concept that is sort of related to Haskell because Haskell is only pure functions. If you want to learn what a monad is, learn category theory. If you want to learn how to use monads in Haskell, read a bunch of blog posts.
No comments:
Post a Comment