Parametrizing [] as an instance of the Functor type class

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Parametrizing [] as an instance of the Functor type class

Olumide
According to LYH, the list is an instance of the Functor type class:

instance Functor [] where
     fmap = map

Why does 'f' not appear in this expression?, considering that Functor is
defined as

class Functor f where
     fmap :: (a -> b) -> f a -> f b

Overall, I'm a bit confused about the relationship between the type
constructor f and [].

Thanks,

- Olumide

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

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

On 31/12/15 14:06, Olumide wrote:
> Overall, I'm a bit confused about the relationship between the type
>  constructor f and [].
f = []. In other words, [] *is* the type constructor.

In Haskell, [] is both the type constructor for lists *and* the term
level value for an empty list. This is unfortunate. In ghci you can
see this.

? :t []
[] :: [t] -- term level
? :k []
[] :: * -> * -- type level
- --
Alexander
[hidden email]
https://secure.plaimi.net/~alexander
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCgAGBQJWhSk5AAoJENQqWdRUGk8BPHcQAOHzfxcEQ+ZTQ5VMZjNo2cC5
5dXKFg2h0jGho4FhUNWeJ4EPSiyYHTEmyK3ZL2KSYoTVAPq/PyeZMdJFRgVRAeyz
Ktyv00E9oJQqjxUrZi7YiE+Y/KteqjE8Hy0X9QW7ICgcU1M9a13o6L+CLdoYrCj8
K6Dto35O7aZRLLQTjoZBm0I6VeDF9WDJPQwZrmXopXhixKrEad8EPne/Tt/yXlTr
Yl2Wya5w+f/xkD6G3T7nHz6Z2CtVhzfqTMO+9OoDkNnt8kFC1ZCsdDicbryEcvEA
0WlURPfjTMRCffrKz8N5SeyzgSF29EJATY2U9yg1l2gajiHxo+Veg1HXF2EMr5RZ
HF1DJyykXOOpel2VBY+ljtUsVP2J1gF7CoGjAzQnIQhGq3n/DOzmieRCZrZ4eC2W
8gUKyQwd4VPSI+YCZ+io9/NIXETpA+TIUdEYI5Goje4laN5lvddwAc0ADAbWPfyt
bsVjlmu3nC3EhG/7qw3KfA4KBiCXU8hH+8zvzDFYjBMX2bxnd/42jiJ8HyNVPYhW
s1FB3ndNUU/tHQzsSye3DXdL6mZ/PsDCT4RAcKc6HMTOP2K04DR8Nmo9Ag6RV0Pw
VomcJkESFZYYG1vPrdbxDRAWJgGIsMd1UpuPe5r6uzj06Xh9zmoLIqVxB3u2Um8k
AnGPKK8WBdguP09bjG0Q
=8v7y
-----END PGP SIGNATURE-----
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Daniel Trstenjak-2
In reply to this post by Olumide
On Thu, Dec 31, 2015 at 01:06:18PM +0000, Olumide wrote:
> Why does 'f' not appear in this expression?, considering that Functor is
> defined as

   instance Functor [] where
      fmap = map

is the eta reduced - search for eta reduction for the details - of a
version like:

   instance Functor [] where
      fmap g f = map g f


Greetings,
Daniel
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Olumide
In reply to this post by Alexander Berntsen
Can you please give an example of [] used as a type constructor? I'm
still learning Haskell and don't yet know what kind is. Is it related to
type constructors?

Regards,

- Olumide

On 31/12/15 13:10, Alexander Berntsen wrote:

>...
> On 31/12/15 14:06, Olumide wrote:
>> Overall, I'm a bit confused about the relationship between the type
>>   constructor f and [].
> f = []. In other words, [] *is* the type constructor.
>
> In Haskell, [] is both the type constructor for lists *and* the term
> level value for an empty list. This is unfortunate. In ghci you can
> see this.
>
> ? :t []
> [] :: [t] -- term level
> ? :k []
> [] :: * -> * -- type level

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: 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
[hidden email]
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-----
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Olumide
In reply to this post by Olumide
On 31/12/2015 13:06, Olumide wrote:
> ... considering that Functor is defined as
>
> class Functor f
 >    where fmap :: (a -> b) -> f a -> f b
>

Still on the subject, according to LYH, the above definition(?) is read
thusly: "fmap takes a function from one type as to another and a functor
value applied with one type and returns a functor value applied with
another type".

So if list is "a part of the part of the Functor type class" (quoting
LYH) how am I to grok a list e.g. [1,2,3] as a "functor value applied to
a type"?

Thanks,

- Olumide
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Olumide
In reply to this post by Alexander Berntsen
On 01/01/2016 19:41, Alexander Berntsen 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.

Out of curiosity, is [] defined as type constructor _and_ term level at
the library level or in the language/compiler? (BTW, google tells me
"term-level" has a special meaning that I do not yet know.)

Note: I've deferred reading your explanation of kinds because (1) I am
still trying to get to grips with Functors and (2) the section on kinds
is just two pages away from where I am in the book. So if these
questions are answered by kinds please let me know.

Thanks for your patience,

- Olumide

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Rein Henrichs
[1,2,3] is [Int] or [] Int (if we take the numbers to be Ints for simplicity). It is the [] type constructor applied to the Int type.

On Tue, Jan 5, 2016 at 5:59 AM Olumide <[hidden email]> wrote:
On 01/01/2016 19:41, Alexander Berntsen 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.

Out of curiosity, is [] defined as type constructor _and_ term level at
the library level or in the language/compiler? (BTW, google tells me
"term-level" has a special meaning that I do not yet know.)

Note: I've deferred reading your explanation of kinds because (1) I am
still trying to get to grips with Functors and (2) the section on kinds
is just two pages away from where I am in the book. So if these
questions are answered by kinds please let me know.

Thanks for your patience,

- Olumide

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Daniel Bergey
In reply to this post by Olumide
On 2016-01-05 at 08:59, Olumide <[hidden email]> wrote:
> On 01/01/2016 19:41, Alexander Berntsen wrote:
>> 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.
>
> Out of curiosity, is [] defined as type constructor _and_ term level at
> the library level or in the language/compiler? (BTW, google tells me
> "term-level" has a special meaning that I do not yet know.)

The special syntax of [] requires that the compiler (specifically, the
parser) treat lists specially.

We could define our own data type that behaves like lists,

List a = Nil | Cons a (List a)

but writing out literal lists would be a little clunky.  It's nice that
we can write:

[]
[1]
[1,2,3]

instead of:

Nil
Cons 1 Nil
Cons 1 (Cons 2 (Cons 3 Nil))

The [1,2,3] syntax requres that the Haskell parser be aware of this
type.

At the type level, we can write [Int], [Char], and so forth, instead of
List Int, List Char.  This also requires support in the parser.

bergey
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Daniel Bergey
In reply to this post by Olumide
On 2016-01-05 at 08:33, Olumide <[hidden email]> wrote:

> On 31/12/2015 13:06, Olumide wrote:
>> ... considering that Functor is defined as
>>
>> class Functor f
>  >    where fmap :: (a -> b) -> f a -> f b
>>
>
> Still on the subject, according to LYH, the above definition(?) is read
> thusly: "fmap takes a function from one type as to another and a functor
> value applied with one type and returns a functor value applied with
> another type".
>
> So if list is "a part of the part of the Functor type class" (quoting
> LYH) how am I to grok a list e.g. [1,2,3] as a "functor value applied to
> a type"?

The type of [1,2,3] is [Int] (or possibly [Integer], [Float], [Double],
or similar).  We read [Int] as "list of Ints".  "List" is the instance
of Functor, Int is the type to which "list" is applied.

This may be easier to understand for types which are written prefix,
rather than [], which is written around Int.  "List Int" or "Maybe Int"
look like a function List or Maybe applied to the argument Int, except
that the capitalization reminds us that these are types, not values /
terms.

The section on kinds, may help here.  Kinds give us a formal syntax for
expressing things like "list takes a type as input and gives back a new
type".

bergey
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Parametrizing [] as an instance of the Functor type class

Alexander Berntsen
In reply to this post by Olumide
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Rein and bergey covered most of it. As for

On 05/01/16 14:59, Olumide wrote:
> (BTW, google tells me "term-level" has a special meaning that I do
> not yet know.)

Term-level is the level "below" types. A term has a type and a type
has a kind.

- -- 3 is a term with type Int.
3   :: Int -- Here :: can be read "has-type"
- -- Int is a type with kind *.
Int :: *   -- Whilst here :: is "has-kind"
- --
Alexander
[hidden email]
https://secure.plaimi.net/~alexander
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCgAGBQJWj5k1AAoJENQqWdRUGk8BmLwP/1yCHs4TMwyZf3IjrQwYf+TN
CKj//05T6vxctnNeehP2B4088lW/0nJNBpOx1MxFe0TDDREpL7uts5CRW5I2xhhu
a5rn0hdshvlFXNXJ7OA+P+Rvlm+zAt0hbLkOst9/dVl70w3s2UqRiskkib0pMUsW
7R8GOX9aS4qUqQi5XH8JG2A2naKSGqWdtz8vI2AJ2jujGIx80zRUKIOrkDf5O6i/
DgQ4d019OaxUAyLJZP9CyuLAhg8up29VVPq0JxV9t3j7BYGnNK3AawEzisklUKlY
M3EfJqbV8OH1Munu/dxHdPzD+XtMEuWkfXe6qWEEytDn1jLcdEYb7YowKRykJron
5OJXLAB1jppO2KvjtZNA6YhVmf8WeEEtdZw6zHtkWgb4M6DHBV5sQ9Gg0R/M3C2u
NKHG+UPq2xL+S3CSQN9PbpVZPQuGuB3heqhfCHtQasvNqJPdqYkgsxRm3TmjW83k
6lvdHSzKWdowUHX72KMkoDGb0obG4ivXfTn2HkCJiVFAuoYwwwWOfzxJAlrmOvFk
7Dv0ZHuHu3AQUqz6IeybkLibFLYoQOqpj1ipKVDxb286CTpx80aF3ZvWkJv2rwoT
V9h8g/wO9gudRTPFS61uEZ9YEcWmAgzKNisMAmicAFATKH+/1Ezr4mh9JyNeafF8
bc5W94c5sGR9etkR8Y4p
=zgxs
-----END PGP SIGNATURE-----
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners