[Haskell-beginners] Parametrizing [] as an instance of the Functor type class

[Alexander Berntsen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 01/01/16 20:17, Olumide wrote:
> Can you please give an example of [] used as a type constructor?
Whenever you write a list type, e.g. [Int], you are using [] as a type
constructor. The fact that you can write [Int] instead of '[] Int' is
simply syntax sugar.

We can imagine the simple function that returns the first element of a
list, if there is one.

head :: [a] -> Maybe a
head []     = Nothing
head (x:xs) = Just x

Here we use [] both on type and term level. On type level we use it to
mean a list of 'a's, and on term level we use it to mean the empty list.

If we desugar the type signature slightly, we can write 'head :: [] a
- -> Maybe a', which should make the type level use of [] even more
clear. Here [] would be the f in Functor f, just like Maybe would be
the f in the Functor Maybe instance.

> I'm still learning Haskell and don't yet know what kind is. Is it 
> related to type constructors?
Kinds are to types what types are to terms. In other words, a term has
a type, which has a kind. 3.0 can have the type Double, and Double has
the kind *.

You can read '*' as "the concrete type" -- i.e. a plain type such as
Double, Int, or String. [] and Maybe on the other hand have kind * -> *.

You can think about this in much the same way you'd think about
functions.

λ :t (+) -- A function
(+) :: Num a => a -> a -> a
λ :t 1 + 2 -- A value
1 + 2 :: Num a => a

λ :k Maybe -- A Type constructor
Maybe :: * -> *
λ :k Maybe Int -- A concrete type
Maybe Int :: *

So similarly to how 1 + 2 is a plain value of a plain type, the kind
of 'Maybe Int' is just the concrete *. But (+) by itself is a
function, and Maybe by itself is a type constructor. I.e. they need
arguments.

We call types of kind * -> *, such as Maybe and [], type constructors,
because they can't have terms on their own. There is no value for a
type like Maybe; it's just not possible, since it isn't a concrete type.


Hope that helps.
- -- 
Alexander
alexander at plaimi.net
https://secure.plaimi.net/~alexander
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIbBAEBCgAGBQJWhtZ5AAoJENQqWdRUGk8BfDwP+IU0aGnSqYer7kAOK+SRMA5J
60bYS9WNG7+vN4qr3gBoQXC6YFy3DfUqqPiuBpI7O7rb68KAlAmPj7q7ALG7U293
h7DJ9SYli6bmNsqVxE5a3zkMVKu5wdeH6nKBApKy6gMA4g0AOV8DJ5I+Z/0nqDGj
owjCwn0WrL7Avum160aOIqYzraoI20YgVvOXWflj70ljtSjclYlSp3iiy2sVdrQz
GXVSipGVRhrZ/8t55skB5gR3ASjr3X6+JRnuvO7qtywuWPF513jAiqNp0yfNQKkp
6yVtenWuuCsQh5eIjelD345vKdYCvnzA7v2iq4pnggj04DpKwyYbb5yZ0vUaYX44
9W5tYlyxL08jxuQHokwdDw0CWzk+3xIYNMXmj22OKpgW+QymDqTkB6UheaHHdCFN
1qvmvUKNjYF5y/h3Y+skR5fz6iHsemShuIIFTfgDVClpOaTn/bny18+PcoAzuNvH
WQD1NYTviE3IYXvP6vWQtizYKwW4ljlk3ilDLeYvcWQhK5P+KAYFDamKJtWGhnFC
L+vrXybqWn/IIAXjuV8DY+vhi1V5U6kr+ATA9IkDuXyv7cs0zu1lnrI9LC/YEDdJ
sNnDrquhlwUU80mVvVmEGKyOHgEQtlEmipGoL0dCg43Erd6ra3Bu95o9nUy6KHbc
bu+qp2ZxQA722UIwNUI=
=WV5c
-----END PGP SIGNATURE-----