map type explanation

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

map type explanation

Galaxy Being
I'm looking at this

ghci> :type map
map :: (a -> b) -> [a] -> [b]


and wondering what the (a -> b) part is about. map takes a function and applies it to an incoming list. Good. Understood. I'm guessing that the whole Haskell type declaration idea is based on currying, and I do understand how the (a -> b) part "takes" an incoming list, [a] and produces the [b] output. Also, I don't understand a and b very well either. Typically, a is just a generic variable, then b is another generic variable not necessarily the same as a. But how are they being used in this type declaration?

LB

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

Re: map type explanation

David McBride
They are not parameters, they are the types of the parameters.

In this case a can really be anything, Int, Char, whatever, so long as the function takes a single argument of that type and the list that is given has elements of that same type.
It is the same for b, it doesn't matter what b ends up being, so long as when you call that function the function's return value is compatible with the element type of the list that you intended to return from the entire statement.

You can mess with it yourself in ghci to see how type inference works.

>:t show
:show :: Show a => a -> String
>:t map show
map show :: Show a => [a] -> [String]
> :t flip map [1::Int]
> flip map [1::Int] :: (Int -> b) -> [b]


On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]> wrote:
I'm looking at this

ghci> :type map
map :: (a -> b) -> [a] -> [b]


and wondering what the (a -> b) part is about. map takes a function and applies it to an incoming list. Good. Understood. I'm guessing that the whole Haskell type declaration idea is based on currying, and I do understand how the (a -> b) part "takes" an incoming list, [a] and produces the [b] output. Also, I don't understand a and b very well either. Typically, a is just a generic variable, then b is another generic variable not necessarily the same as a. But how are they being used in this type declaration?

LB
_______________________________________________
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: map type explanation

Galaxy Being
Thank you, but why in 

map :: (a -> b) -> [a] -> [b]

are there parentheses around a -> b ? In general, what is the currying aspect of this?


On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
They are not parameters, they are the types of the parameters.

In this case a can really be anything, Int, Char, whatever, so long as the function takes a single argument of that type and the list that is given has elements of that same type.
It is the same for b, it doesn't matter what b ends up being, so long as when you call that function the function's return value is compatible with the element type of the list that you intended to return from the entire statement.

You can mess with it yourself in ghci to see how type inference works.

>:t show
:show :: Show a => a -> String
>:t map show
map show :: Show a => [a] -> [String]
> :t flip map [1::Int]
> flip map [1::Int] :: (Int -> b) -> [b]


On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]> wrote:
I'm looking at this

ghci> :type map
map :: (a -> b) -> [a] -> [b]


and wondering what the (a -> b) part is about. map takes a function and applies it to an incoming list. Good. Understood. I'm guessing that the whole Haskell type declaration idea is based on currying, and I do understand how the (a -> b) part "takes" an incoming list, [a] and produces the [b] output. Also, I don't understand a and b very well either. Typically, a is just a generic variable, then b is another generic variable not necessarily the same as a. But how are they being used in this type declaration?

LB
_______________________________________________
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

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

Re: map type explanation

Ut Primum
Hi,

a -> b  is the type of a function taking arguments of a generic type (we call it a) and returning results of another type, that we call b.

So 
(a -> b ) -> [a] -> [b]
Means that you have a first argument that is a function (a-> b),  a second argument that is a list of elements of the same type of the function input, and that the returned element is a list of things of the type of the output of the function.

Cheers,
Ut

Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha scritto:
Thank you, but why in 

map :: (a -> b) -> [a] -> [b]

are there parentheses around a -> b ? In general, what is the currying aspect of this?


On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
They are not parameters, they are the types of the parameters.

In this case a can really be anything, Int, Char, whatever, so long as the function takes a single argument of that type and the list that is given has elements of that same type.
It is the same for b, it doesn't matter what b ends up being, so long as when you call that function the function's return value is compatible with the element type of the list that you intended to return from the entire statement.

You can mess with it yourself in ghci to see how type inference works.

>:t show
:show :: Show a => a -> String
>:t map show
map show :: Show a => [a] -> [String]
> :t flip map [1::Int]
> flip map [1::Int] :: (Int -> b) -> [b]


On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]> wrote:
I'm looking at this

ghci> :type map
map :: (a -> b) -> [a] -> [b]


and wondering what the (a -> b) part is about. map takes a function and applies it to an incoming list. Good. Understood. I'm guessing that the whole Haskell type declaration idea is based on currying, and I do understand how the (a -> b) part "takes" an incoming list, [a] and produces the [b] output. Also, I don't understand a and b very well either. Typically, a is just a generic variable, then b is another generic variable not necessarily the same as a. But how are they being used in this type declaration?

LB
_______________________________________________
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
_______________________________________________
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: map type explanation

Galaxy Being
Why is it not just

a -> b -> [a] -> [b]

again, why the parentheses?

On Fri, Dec 18, 2020 at 4:10 PM Ut Primum <[hidden email]> wrote:
Hi,

a -> b  is the type of a function taking arguments of a generic type (we call it a) and returning results of another type, that we call b.

So 
(a -> b ) -> [a] -> [b]
Means that you have a first argument that is a function (a-> b),  a second argument that is a list of elements of the same type of the function input, and that the returned element is a list of things of the type of the output of the function.

Cheers,
Ut

Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha scritto:
Thank you, but why in 

map :: (a -> b) -> [a] -> [b]

are there parentheses around a -> b ? In general, what is the currying aspect of this?


On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
They are not parameters, they are the types of the parameters.

In this case a can really be anything, Int, Char, whatever, so long as the function takes a single argument of that type and the list that is given has elements of that same type.
It is the same for b, it doesn't matter what b ends up being, so long as when you call that function the function's return value is compatible with the element type of the list that you intended to return from the entire statement.

You can mess with it yourself in ghci to see how type inference works.

>:t show
:show :: Show a => a -> String
>:t map show
map show :: Show a => [a] -> [String]
> :t flip map [1::Int]
> flip map [1::Int] :: (Int -> b) -> [b]


On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]> wrote:
I'm looking at this

ghci> :type map
map :: (a -> b) -> [a] -> [b]


and wondering what the (a -> b) part is about. map takes a function and applies it to an incoming list. Good. Understood. I'm guessing that the whole Haskell type declaration idea is based on currying, and I do understand how the (a -> b) part "takes" an incoming list, [a] and produces the [b] output. Also, I don't understand a and b very well either. Typically, a is just a generic variable, then b is another generic variable not necessarily the same as a. But how are they being used in this type declaration?

LB
_______________________________________________
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
_______________________________________________
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

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

Re: map type explanation

Bruno Barbier

Hi Lawrence,

Lawrence Bottorff <[hidden email]> writes:

> Why is it not just
>
> a -> b -> [a] -> [b]
>
> again, why the parentheses?

In Haskell, (->) is a binary operator and is right associative. If you write:

   a -> b -> [a] -> [b]

it implicitly means:

   a -> (b -> ([a] -> [b]))

So here, you need explicit parenthesis:

   (a -> b) -> [a] -> [b]

to mean:
   (a -> b) -> ([a] -> [b])

It's more about parsing binary operators than about types.

Does it help ?

Bruno

> On Fri, Dec 18, 2020 at 4:10 PM Ut Primum <[hidden email]> wrote:
>
>> Hi,
>>
>> a -> b  is the type of a function taking arguments of a generic type (we
>> call it a) and returning results of another type, that we call b.
>>
>> So
>> (a -> b ) -> [a] -> [b]
>> Means that you have a first argument that is a function (a-> b),  a second
>> argument that is a list of elements of the same type of the function input,
>> and that the returned element is a list of things of the type of the output
>> of the function.
>>
>> Cheers,
>> Ut
>>
>> Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha
>> scritto:
>>
>>> Thank you, but why in
>>>
>>> map :: (a -> b) -> [a] -> [b]
>>>
>>> are there parentheses around a -> b ? In general, what is the currying
>>> aspect of this?
>>>
>>>
>>> On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
>>>
>>>> They are not parameters, they are the types of the parameters.
>>>>
>>>> In this case a can really be anything, Int, Char, whatever, so long as
>>>> the function takes a single argument of that type and the list that is
>>>> given has elements of that same type.
>>>> It is the same for b, it doesn't matter what b ends up being, so long as
>>>> when you call that function the function's return value is compatible with
>>>> the element type of the list that you intended to return from the entire
>>>> statement.
>>>>
>>>> You can mess with it yourself in ghci to see how type inference works.
>>>>
>>>> >:t show
>>>> :show :: Show a => a -> String
>>>> >:t map show
>>>> map show :: Show a => [a] -> [String]
>>>> > :t flip map [1::Int]
>>>> > flip map [1::Int] :: (Int -> b) -> [b]
>>>>
>>>>
>>>> On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]>
>>>> wrote:
>>>>
>>>>> I'm looking at this
>>>>>
>>>>> ghci> :type map
>>>>> map :: (a -> b) -> [a] -> [b]
>>>>>
>>>>> and wondering what the (a -> b) part is about. map takes a function
>>>>> and applies it to an incoming list. Good. Understood. I'm guessing that the
>>>>> whole Haskell type declaration idea is based on currying, and I do
>>>>> understand how the (a -> b) part "takes" an incoming list, [a] and
>>>>> produces the [b] output. Also, I don't understand a and b very well
>>>>> either. Typically, a is just a generic variable, then b is another
>>>>> generic variable not necessarily the same as a. But how are they being
>>>>> used in this type declaration?
>>>>>
>>>>> LB
>>>>> _______________________________________________
>>>>> 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
>>>>
>>> _______________________________________________
>>> 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
>>
> _______________________________________________
> 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: map type explanation

Galaxy Being
So in effect

a -> b -> [a] -> [b]

wants to be, would be

a -> (b -> ([a] -> [b]))

without the parens (which is a natural result of lambda calculus, perhaps?) -- which is not what is meant by map. But underlying a Haskell type declaration is currying, is it not? At the type declaration level, it's all currying, correct?

Conceptually, I understand how the a -> b "event" needs to be a "package" to apply to the list [a]. The map function commandeers the target function (which alone by itself does some a -> b evaluation) to be a new object that is then applied to each member of list [a]. Good. So (a -> b) then is a notation that signifies this "package-ness".

Does anyone have examples of other "packaging" where a function doing some a -> b is changed to (a -> b) ?

On Fri, Dec 18, 2020 at 5:18 PM Bruno Barbier <[hidden email]> wrote:

Hi Lawrence,

Lawrence Bottorff <[hidden email]> writes:

> Why is it not just
>
> a -> b -> [a] -> [b]
>
> again, why the parentheses?

In Haskell, (->) is a binary operator and is right associative. If you write:

   a -> b -> [a] -> [b]

it implicitly means:

   a -> (b -> ([a] -> [b]))

So here, you need explicit parenthesis:

   (a -> b) -> [a] -> [b]

to mean:
   (a -> b) -> ([a] -> [b])

It's more about parsing binary operators than about types.

Does it help ?

Bruno

> On Fri, Dec 18, 2020 at 4:10 PM Ut Primum <[hidden email]> wrote:
>
>> Hi,
>>
>> a -> b  is the type of a function taking arguments of a generic type (we
>> call it a) and returning results of another type, that we call b.
>>
>> So
>> (a -> b ) -> [a] -> [b]
>> Means that you have a first argument that is a function (a-> b),  a second
>> argument that is a list of elements of the same type of the function input,
>> and that the returned element is a list of things of the type of the output
>> of the function.
>>
>> Cheers,
>> Ut
>>
>> Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha
>> scritto:
>>
>>> Thank you, but why in
>>>
>>> map :: (a -> b) -> [a] -> [b]
>>>
>>> are there parentheses around a -> b ? In general, what is the currying
>>> aspect of this?
>>>
>>>
>>> On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
>>>
>>>> They are not parameters, they are the types of the parameters.
>>>>
>>>> In this case a can really be anything, Int, Char, whatever, so long as
>>>> the function takes a single argument of that type and the list that is
>>>> given has elements of that same type.
>>>> It is the same for b, it doesn't matter what b ends up being, so long as
>>>> when you call that function the function's return value is compatible with
>>>> the element type of the list that you intended to return from the entire
>>>> statement.
>>>>
>>>> You can mess with it yourself in ghci to see how type inference works.
>>>>
>>>> >:t show
>>>> :show :: Show a => a -> String
>>>> >:t map show
>>>> map show :: Show a => [a] -> [String]
>>>> > :t flip map [1::Int]
>>>> > flip map [1::Int] :: (Int -> b) -> [b]
>>>>
>>>>
>>>> On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]>
>>>> wrote:
>>>>
>>>>> I'm looking at this
>>>>>
>>>>> ghci> :type map
>>>>> map :: (a -> b) -> [a] -> [b]
>>>>>
>>>>> and wondering what the (a -> b) part is about. map takes a function
>>>>> and applies it to an incoming list. Good. Understood. I'm guessing that the
>>>>> whole Haskell type declaration idea is based on currying, and I do
>>>>> understand how the (a -> b) part "takes" an incoming list, [a] and
>>>>> produces the [b] output. Also, I don't understand a and b very well
>>>>> either. Typically, a is just a generic variable, then b is another
>>>>> generic variable not necessarily the same as a. But how are they being
>>>>> used in this type declaration?
>>>>>
>>>>> LB
>>>>> _______________________________________________
>>>>> 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
>>>>
>>> _______________________________________________
>>> 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
>>
> _______________________________________________
> 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: map type explanation

Jay Sulzberger

On Fri, 18 Dec 2020, Lawrence Bottorff <[hidden email]> wrote:

> So in effect
>
> a -> b -> [a] -> [b]
>
> wants to be, would be
>
> a -> (b -> ([a] -> [b]))

One difficulty in learning New Crazy Type Theory is that, by
tradition, parentheses are suppressed so thoroughly that a beginner
sometimes finds it hard to correctly parse the surface notation.

Let us suppose we have a thing called "a".  Another thing is called
"b".  a and b are, for the moment, just things.  a and b are things of
the same sort: they are both 'types'.  In type theory, like in group
theory, or ring theory, we have various algebras, with operations.  In
ring theory we ring elements, and operations: +, -, 0, 1, *.  A
particular ring, call the ring, say "Example" is given by the
following data:

1. An underlying set, call this set Substrate_of_Example.

2. A specified element of Substrate_of_Example, the 0.

3. A specified element of Substrate_of_Example, the 1.

4. A specified everywhere defined single valued function, the
    +: S_E x S_E -> S_E

5. A specified everywhere defined single valued function, the
    *: S_E x S_E -> S_E

6. 4. A specified everywhere defined single valued function, the
    -: S_E -> S_E

+ and * take two inputs and have one output.
- takes one input and has one output.

By the definition of the concept "ring", the ring substrate S_E and
the two constants, 0 and 1, and the three operations, +, *, and -,
must satisfy certain laws.  If case these laws are satisfied, we say
that the data give us a uniquely defined instance of the concept ring.
The sub-field of mathematics Ring Theory studies such things, that is,
rings.

Similarly Type Theory studies "type systems".  The definition of a
type system is not as tightly defined as the concept of a ring, but
again, at least in the case of the Haskell_Type_System, we have these things:

1. An underlying set, call this set Substrate_of_Haskell_Type_System.
    This set is the set of types.  For convenience we write
    "T" for "Substrate_of_Haskell_Type_System".

2. An everywhere defined single valued function, the hom operator
    =>: T x T -> T
    (We have written "=>" rather than "->" to the left of the ":"
     above to avoid confusion with the "->" in the above line.)

3. An everywhere defined single valued function, the list operator
    []: T -> T.

    (Note [] is not the list operator of, say, Common Lisp, or Scheme,
     or Haskell.  [] operates on types, not on, ah, things which are
     not types, but rather have types.  Oi.)

A particular type system such as HTS is given by the above data, and
the system is a type system, because just as for rings, certain laws
are required to be obeyed.  (Usually a type system has more operations
than the above two.)

Let us suppose we have before us the ring of integers Z.  Here is an
expression in the language of rings, which language applies to Z,
because Z is a ring:

   (((1 + 1) * (0 + 1)) + ((- 1) * (1 + 1)))

The notation is un-ambiguous.  We know what it means, and we can
calculate the value of the expression by applying the operations of
the ring Z.

Now similarly, we have expressions in the HTS.  Here is one expression:

((Int -> Str) -> ([Int] -> [Str]))

The above expression is fully parenthesized, and, thus we know what
type it evaluates to.

Here is another expression:

(Int -> (Str -> ([Int] -> [Str])))

This expression too is fully parenthesized, and, thus we know what
type it evaluates to.

These two types specified by the two different expressions turn out
not to be the same type.  That is, the two expressions evaluate to
different types.

The concept of "currying" has come up.  Part of my difficulty in
learning a little bit of New Crazy Type Theory is that New Crazy Type
Theorists have syntactic conventions which permit them to, often,
reduce the number of parentheses in expressions.  For example, one
convention specifies that the string

"a -> b -> c"

should be translated to the fully parenthesized

(a -> (b -> c))

and not to the different expression

((a -> b) -> c)

The two expressions are different, and in general they evaluate to
different types.

And you are right: this convention has somewhat to do with currying.

We say no more about currying, except that, to define "currying" a
third operation on types is required: the product of types:

xx: T x T -> T

(Again, we write "xx" so that the operation on the left of ":" is not
  confused with the "x" on the right.  Oi.)

I speak now as a beginner.  There is a phrase which, when I was an
even more tenderly ignorant beginner than I am now, always confused
me:

   Such and such operation is binary and right-associative.

My delicate beginner's sensibilities were outraged.  No!  The operation
might indeed be binary, but "right-associative" refers to the system
of notation(s) for the operation(s), not to the operation.

Of course, the above occasions for confusion are just the first and
most simple, on the way to "hello world" in Haskell.

I remain, as ever, your fellow student of history and probability,
Jay Sulzberger


PS. Likely there are errors in above.


>
> without the parens (which is a natural result of lambda calculus, perhaps?)
> -- which is not what is meant by map. But underlying a Haskell type
> declaration is currying, is it not? At the type declaration level, it's all
> currying, correct?
>
> Conceptually, I understand how the a -> b "event" needs to be a "package"
> to apply to the list [a]. The map function commandeers the target function
> (which alone by itself does some a -> b evaluation) to be a new object that
> is then applied to each member of list [a]. Good. So (a -> b) then is a
> notation that signifies this "package-ness".
>
> Does anyone have examples of other "packaging" where a function doing some a
> -> b is changed to (a -> b) ?
>
> On Fri, Dec 18, 2020 at 5:18 PM Bruno Barbier <[hidden email]> wrote:
>
>>
>> Hi Lawrence,
>>
>> Lawrence Bottorff <[hidden email]> writes:
>>
>>> Why is it not just
>>>
>>> a -> b -> [a] -> [b]
>>>
>>> again, why the parentheses?
>>
>> In Haskell, (->) is a binary operator and is right associative. If you
>> write:
>>
>>    a -> b -> [a] -> [b]
>>
>> it implicitly means:
>>
>>    a -> (b -> ([a] -> [b]))
>>
>> So here, you need explicit parenthesis:
>>
>>    (a -> b) -> [a] -> [b]
>>
>> to mean:
>>    (a -> b) -> ([a] -> [b])
>>
>> It's more about parsing binary operators than about types.
>>
>> Does it help ?
>>
>> Bruno
>>
>>> On Fri, Dec 18, 2020 at 4:10 PM Ut Primum <[hidden email]> wrote:
>>>
>>>> Hi,
>>>>
>>>> a -> b  is the type of a function taking arguments of a generic type (we
>>>> call it a) and returning results of another type, that we call b.
>>>>
>>>> So
>>>> (a -> b ) -> [a] -> [b]
>>>> Means that you have a first argument that is a function (a-> b),  a
>> second
>>>> argument that is a list of elements of the same type of the function
>> input,
>>>> and that the returned element is a list of things of the type of the
>> output
>>>> of the function.
>>>>
>>>> Cheers,
>>>> Ut
>>>>
>>>> Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha
>>>> scritto:
>>>>
>>>>> Thank you, but why in
>>>>>
>>>>> map :: (a -> b) -> [a] -> [b]
>>>>>
>>>>> are there parentheses around a -> b ? In general, what is the currying
>>>>> aspect of this?
>>>>>
>>>>>
>>>>> On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]>
>> wrote:
>>>>>
>>>>>> They are not parameters, they are the types of the parameters.
>>>>>>
>>>>>> In this case a can really be anything, Int, Char, whatever, so long as
>>>>>> the function takes a single argument of that type and the list that is
>>>>>> given has elements of that same type.
>>>>>> It is the same for b, it doesn't matter what b ends up being, so long
>> as
>>>>>> when you call that function the function's return value is compatible
>> with
>>>>>> the element type of the list that you intended to return from the
>> entire
>>>>>> statement.
>>>>>>
>>>>>> You can mess with it yourself in ghci to see how type inference works.
>>>>>>
>>>>>>> :t show
>>>>>> :show :: Show a => a -> String
>>>>>>> :t map show
>>>>>> map show :: Show a => [a] -> [String]
>>>>>>> :t flip map [1::Int]
>>>>>>> flip map [1::Int] :: (Int -> b) -> [b]
>>>>>>
>>>>>>
>>>>>> On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]>
>>>>>> wrote:
>>>>>>
>>>>>>> I'm looking at this
>>>>>>>
>>>>>>> ghci> :type map
>>>>>>> map :: (a -> b) -> [a] -> [b]
>>>>>>>
>>>>>>> and wondering what the (a -> b) part is about. map takes a function
>>>>>>> and applies it to an incoming list. Good. Understood. I'm guessing
>> that the
>>>>>>> whole Haskell type declaration idea is based on currying, and I do
>>>>>>> understand how the (a -> b) part "takes" an incoming list, [a] and
>>>>>>> produces the [b] output. Also, I don't understand a and b very well
>>>>>>> either. Typically, a is just a generic variable, then b is another
>>>>>>> generic variable not necessarily the same as a. But how are they
>> being
>>>>>>> used in this type declaration?
>>>>>>>
>>>>>>> LB
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>>
>>>>> _______________________________________________
>>>>> 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
>>>>
>>> _______________________________________________
>>> 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: map type explanation

David James
In reply to this post by Galaxy Being

Hello - some additional comments:

 

  1. You should probably read this, if you haven’t already.

 

  1. You can think of the declaration

fmap :: (a -> b) -> [a] -> [b]

as meaning: fmap takes two arguments:

1st arg of type (a -> b) (i.e.  a function, which takes one argument (of type a) and returns a result (of type b)).

2nd arg of type [a]

and returns:

a result of type [b]

 

An example of a function that can be passed as the first argument would be

Data.Char.ord :: Char -> Int

If we pass this to map, we bind the type a to Char and the type b to Int. Then the second argument must be of type [Char], and the result will be of type [Int]. E.g.

map Data.Char.ord ['F', 'r', 'e', 'd']

gives

[70,114,101,100]

 

  1. Haskell allows “currying”. Which means all functions can be “partially applied”. For example, we can apply map to only one argument. E.g.

map Data.Char.ord

is partially applied, and has type

                [Char] -> [Int]

                You can see this by typing

:t map Data.Char.ord

 

                (If you just type in

map Data.Char.ord

you will get an error, same as if you just typed in

                Data.Char.ord

Haskell, reasonably, doesn’t know how to print a function)

 

In fact, all function applications are curried, so even when you do

map Data.Char.ord ['F', 'r', 'e', 'd']

It actually applies the 1st arg to get a function of type [Char] -> [Int], to which it then applies the second arg to get the final value, which it prints. You could write it as this:

(map Data.Char.ord) ['F', 'r', 'e', 'd']

 

i.e. function application is left-associative. If you don’t put in the brackets to explicitly state differently, you effectively get brackets to the left. This is the same as e.g.

                                7 – 4 – 1

                meaning

                                (7 – 4) – 1

                which equals 2. It does not mean

                                7 – (4 – 1)

                which equals 4. If you want the latter, you need to explicitly write the brackets.

 

                You could of course write

map (Data.Char.ord ['F', 'r', 'e', 'd'])

This is syntactically valid, but would attempt to apply Data.Char.ord to the list of characters, which would give a type error. (And a second type error for attempting to apply map to the result of Data.Char.ord.

 

  1. In type declarations function application is right-associative, so

a -> b -> [a] -> [b]

means

                a -> (b -> ([a] -> [b]))

which represents a function of one argument (of type a), which returns a result of type (b -> ([a] -> [b])). I’m not sure it would be possible to write such a function, but it would certainly not be the same as map.

 

If you want the brackets in a different place (and we do), then we need to put them explicitly, i.e.

(a -> b) -> ([a] -> [b])

                Or, we could you the right-associative default to omit the second pair:

(a -> b) -> [a] -> [b]

 

  1. Note that the associativity is simply a matter of syntax. The Haskell definition could have said you always need to put the brackets. Then 7 – 4 – 1 would be a syntax error, you’d need to put either (7 – 4) – 1 or 7 – (4 – 1). However, many people find typing without brackets helpful most of the time. (Though I must admit that I often “over-bracket” my code, either because I’m not sure of the associativity of different operators, or because I want to make the code more explicitly clear).

 

Haskell has defined function application to be left-associative because of currying, as described above. Even though

map Data.Char.ord ['F', 'r', 'e', 'd']

looks like applying two arguments, it really does (map Data.Char.ord) first.

 

Similarly, Haskell has defined functions in type declarations to be right-associative for the same reason. The function consumes the first arg first, so in

                (a -> b) -> [a] -> [b]

after consuming the (a -> b), you’re left with a function of type ([a] -> [b]).

 

Sorry, that ended up quite a bit longer than I expected, but I hope it helps and apologies if I’ve made any errors/etc.

 

David.

 

From: [hidden email]
Sent: 19 December 2020 03:37
To: [hidden email]
Cc: [hidden email]
Subject: Re: [Haskell-beginners] map type explanation

 

So in effect

 

a -> b -> [a] -> [b]

 

wants to be, would be

 

a -> (b -> ([a] -> [b]))

 

without the parens (which is a natural result of lambda calculus, perhaps?) -- which is not what is meant by map. But underlying a Haskell type declaration is currying, is it not? At the type declaration level, it's all currying, correct?

 

Conceptually, I understand how the a -> b "event" needs to be a "package" to apply to the list [a]. The map function commandeers the target function (which alone by itself does some a -> b evaluation) to be a new object that is then applied to each member of list [a]. Good. So (a -> b) then is a notation that signifies this "package-ness".

 

Does anyone have examples of other "packaging" where a function doing some a -> b is changed to (a -> b) ?

 

On Fri, Dec 18, 2020 at 5:18 PM Bruno Barbier <[hidden email]> wrote:


Hi Lawrence,

Lawrence Bottorff <[hidden email]> writes:

> Why is it not just
>
> a -> b -> [a] -> [b]
>
> again, why the parentheses?

In Haskell, (->) is a binary operator and is right associative. If you write:

   a -> b -> [a] -> [b]

it implicitly means:

   a -> (b -> ([a] -> [b]))

So here, you need explicit parenthesis:

   (a -> b) -> [a] -> [b]

to mean:
   (a -> b) -> ([a] -> [b])

It's more about parsing binary operators than about types.

Does it help ?

Bruno

> On Fri, Dec 18, 2020 at 4:10 PM Ut Primum <[hidden email]> wrote:
>
>> Hi,
>>
>> a -> b  is the type of a function taking arguments of a generic type (we
>> call it a) and returning results of another type, that we call b.
>>
>> So
>> (a -> b ) -> [a] -> [b]
>> Means that you have a first argument that is a function (a-> b),  a second
>> argument that is a list of elements of the same type of the function input,
>> and that the returned element is a list of things of the type of the output
>> of the function.
>>
>> Cheers,
>> Ut
>>
>> Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha
>> scritto:
>>
>>> Thank you, but why in
>>>
>>> map :: (a -> b) -> [a] -> [b]
>>>
>>> are there parentheses around a -> b ? In general, what is the currying
>>> aspect of this?
>>>
>>>
>>> On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
>>>
>>>> They are not parameters, they are the types of the parameters.
>>>>
>>>> In this case a can really be anything, Int, Char, whatever, so long as
>>>> the function takes a single argument of that type and the list that is
>>>> given has elements of that same type.
>>>> It is the same for b, it doesn't matter what b ends up being, so long as
>>>> when you call that function the function's return value is compatible with
>>>> the element type of the list that you intended to return from the entire
>>>> statement.
>>>>
>>>> You can mess with it yourself in ghci to see how type inference works.
>>>>
>>>> >:t show
>>>> :show :: Show a => a -> String
>>>> >:t map show
>>>> map show :: Show a => [a] -> [String]
>>>> > :t flip map [1::Int]
>>>> > flip map [1::Int] :: (Int -> b) -> [b]
>>>>
>>>>
>>>> On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]>
>>>> wrote:
>>>>
>>>>> I'm looking at this
>>>>>
>>>>> ghci> :type map
>>>>> map :: (a -> b) -> [a] -> [b]
>>>>>
>>>>> and wondering what the (a -> b) part is about. map takes a function
>>>>> and applies it to an incoming list. Good. Understood. I'm guessing that the
>>>>> whole Haskell type declaration idea is based on currying, and I do
>>>>> understand how the (a -> b) part "takes" an incoming list, [a] and
>>>>> produces the [b] output. Also, I don't understand a and b very well
>>>>> either. Typically, a is just a generic variable, then b is another
>>>>> generic variable not necessarily the same as a. But how are they being
>>>>> used in this type declaration?
>>>>>
>>>>> LB
>>>>> _______________________________________________
>>>>> 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
>>>>
>>> _______________________________________________
>>> 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
>>
> _______________________________________________
> 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: map type explanation

Josh Friedlander
I'm a real beginner, but IIUC might the misunderstanding here be that OP was assuming that since all functions in Haskell take only one argument - and multiple-argument functions just hide this by currying - the same must apply to types; whereas in fact types may take multiple arguments?

On Sat, 19 Dec 2020, 13:02 David James, <[hidden email]> wrote:

Hello - some additional comments:

 

  1. You should probably read this, if you haven’t already.

 

  1. You can think of the declaration

fmap :: (a -> b) -> [a] -> [b]

as meaning: fmap takes two arguments:

1st arg of type (a -> b) (i.e.  a function, which takes one argument (of type a) and returns a result (of type b)).

2nd arg of type [a]

and returns:

a result of type [b]

 

An example of a function that can be passed as the first argument would be

Data.Char.ord :: Char -> Int

If we pass this to map, we bind the type a to Char and the type b to Int. Then the second argument must be of type [Char], and the result will be of type [Int]. E.g.

map Data.Char.ord ['F', 'r', 'e', 'd']

gives

[70,114,101,100]

 

  1. Haskell allows “currying”. Which means all functions can be “partially applied”. For example, we can apply map to only one argument. E.g.

map Data.Char.ord

is partially applied, and has type

                [Char] -> [Int]

                You can see this by typing

:t map Data.Char.ord

 

                (If you just type in

map Data.Char.ord

you will get an error, same as if you just typed in

                Data.Char.ord

Haskell, reasonably, doesn’t know how to print a function)

 

In fact, all function applications are curried, so even when you do

map Data.Char.ord ['F', 'r', 'e', 'd']

It actually applies the 1st arg to get a function of type [Char] -> [Int], to which it then applies the second arg to get the final value, which it prints. You could write it as this:

(map Data.Char.ord) ['F', 'r', 'e', 'd']

 

i.e. function application is left-associative. If you don’t put in the brackets to explicitly state differently, you effectively get brackets to the left. This is the same as e.g.

                                7 – 4 – 1

                meaning

                                (7 – 4) – 1

                which equals 2. It does not mean

                                7 – (4 – 1)

                which equals 4. If you want the latter, you need to explicitly write the brackets.

 

                You could of course write

map (Data.Char.ord ['F', 'r', 'e', 'd'])

This is syntactically valid, but would attempt to apply Data.Char.ord to the list of characters, which would give a type error. (And a second type error for attempting to apply map to the result of Data.Char.ord.

 

  1. In type declarations function application is right-associative, so

a -> b -> [a] -> [b]

means

                a -> (b -> ([a] -> [b]))

which represents a function of one argument (of type a), which returns a result of type (b -> ([a] -> [b])). I’m not sure it would be possible to write such a function, but it would certainly not be the same as map.

 

If you want the brackets in a different place (and we do), then we need to put them explicitly, i.e.

(a -> b) -> ([a] -> [b])

                Or, we could you the right-associative default to omit the second pair:

(a -> b) -> [a] -> [b]

 

  1. Note that the associativity is simply a matter of syntax. The Haskell definition could have said you always need to put the brackets. Then 7 – 4 – 1 would be a syntax error, you’d need to put either (7 – 4) – 1 or 7 – (4 – 1). However, many people find typing without brackets helpful most of the time. (Though I must admit that I often “over-bracket” my code, either because I’m not sure of the associativity of different operators, or because I want to make the code more explicitly clear).

 

Haskell has defined function application to be left-associative because of currying, as described above. Even though

map Data.Char.ord ['F', 'r', 'e', 'd']

looks like applying two arguments, it really does (map Data.Char.ord) first.

 

Similarly, Haskell has defined functions in type declarations to be right-associative for the same reason. The function consumes the first arg first, so in

                (a -> b) -> [a] -> [b]

after consuming the (a -> b), you’re left with a function of type ([a] -> [b]).

 

Sorry, that ended up quite a bit longer than I expected, but I hope it helps and apologies if I’ve made any errors/etc.

 

David.

 

From: [hidden email]
Sent: 19 December 2020 03:37
To: [hidden email]
Cc: [hidden email]
Subject: Re: [Haskell-beginners] map type explanation

 

So in effect

 

a -> b -> [a] -> [b]

 

wants to be, would be

 

a -> (b -> ([a] -> [b]))

 

without the parens (which is a natural result of lambda calculus, perhaps?) -- which is not what is meant by map. But underlying a Haskell type declaration is currying, is it not? At the type declaration level, it's all currying, correct?

 

Conceptually, I understand how the a -> b "event" needs to be a "package" to apply to the list [a]. The map function commandeers the target function (which alone by itself does some a -> b evaluation) to be a new object that is then applied to each member of list [a]. Good. So (a -> b) then is a notation that signifies this "package-ness".

 

Does anyone have examples of other "packaging" where a function doing some a -> b is changed to (a -> b) ?

 

On Fri, Dec 18, 2020 at 5:18 PM Bruno Barbier <[hidden email]> wrote:


Hi Lawrence,

Lawrence Bottorff <[hidden email]> writes:

> Why is it not just
>
> a -> b -> [a] -> [b]
>
> again, why the parentheses?

In Haskell, (->) is a binary operator and is right associative. If you write:

   a -> b -> [a] -> [b]

it implicitly means:

   a -> (b -> ([a] -> [b]))

So here, you need explicit parenthesis:

   (a -> b) -> [a] -> [b]

to mean:
   (a -> b) -> ([a] -> [b])

It's more about parsing binary operators than about types.

Does it help ?

Bruno

> On Fri, Dec 18, 2020 at 4:10 PM Ut Primum <[hidden email]> wrote:
>
>> Hi,
>>
>> a -> b  is the type of a function taking arguments of a generic type (we
>> call it a) and returning results of another type, that we call b.
>>
>> So
>> (a -> b ) -> [a] -> [b]
>> Means that you have a first argument that is a function (a-> b),  a second
>> argument that is a list of elements of the same type of the function input,
>> and that the returned element is a list of things of the type of the output
>> of the function.
>>
>> Cheers,
>> Ut
>>
>> Il ven 18 dic 2020, 23:02 Lawrence Bottorff <[hidden email]> ha
>> scritto:
>>
>>> Thank you, but why in
>>>
>>> map :: (a -> b) -> [a] -> [b]
>>>
>>> are there parentheses around a -> b ? In general, what is the currying
>>> aspect of this?
>>>
>>>
>>> On Fri, Dec 18, 2020 at 12:43 PM David McBride <[hidden email]> wrote:
>>>
>>>> They are not parameters, they are the types of the parameters.
>>>>
>>>> In this case a can really be anything, Int, Char, whatever, so long as
>>>> the function takes a single argument of that type and the list that is
>>>> given has elements of that same type.
>>>> It is the same for b, it doesn't matter what b ends up being, so long as
>>>> when you call that function the function's return value is compatible with
>>>> the element type of the list that you intended to return from the entire
>>>> statement.
>>>>
>>>> You can mess with it yourself in ghci to see how type inference works.
>>>>
>>>> >:t show
>>>> :show :: Show a => a -> String
>>>> >:t map show
>>>> map show :: Show a => [a] -> [String]
>>>> > :t flip map [1::Int]
>>>> > flip map [1::Int] :: (Int -> b) -> [b]
>>>>
>>>>
>>>> On Fri, Dec 18, 2020 at 1:31 PM Lawrence Bottorff <[hidden email]>
>>>> wrote:
>>>>
>>>>> I'm looking at this
>>>>>
>>>>> ghci> :type map
>>>>> map :: (a -> b) -> [a] -> [b]
>>>>>
>>>>> and wondering what the (a -> b) part is about. map takes a function
>>>>> and applies it to an incoming list. Good. Understood. I'm guessing that the
>>>>> whole Haskell type declaration idea is based on currying, and I do
>>>>> understand how the (a -> b) part "takes" an incoming list, [a] and
>>>>> produces the [b] output. Also, I don't understand a and b very well
>>>>> either. Typically, a is just a generic variable, then b is another
>>>>> generic variable not necessarily the same as a. But how are they being
>>>>> used in this type declaration?
>>>>>
>>>>> LB
>>>>> _______________________________________________
>>>>> 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
>>>>
>>> _______________________________________________
>>> 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
>>
> _______________________________________________
> 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

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

Re: map type explanation

coot
In reply to this post by Galaxy Being
Hi,

The `(a -> b)` in `map :: (a -> b) -> [a] -> [b]` is a type of function from a type `a` to a type `b`.   Haskell, by default, is using implicit quantification, however using `ScopedTypeVariables` extension you could write `map :: forall a b. (a -> b) -> [a] -> [b]` to make it explicit.  This way you see that both `a` and `b` are introduced by `forall`.  In particular, you can substitute any types, e.g. if you substitute `a` with `Char` and `b` with `Int`, you'll get `map :: (Char -> Int) -> [Char] -> [Int]`.  If you enable `TypeApplication` extension you can do that in `ghci`:  `:t map @Char @Int`  You can read the type of `map` as follows: given a function `f` from type `a` to some type `b`, `map f :: [a] -> [b]`, i.e. `map f` is a function from list of `a` to list of `b`'s.

Being able to write functions like `map`, is called parametric polymorphism. Using such  polymorphism you guarantee that the implentation of `map` cannot do any thing with `a`'s and `b`'s, as there's no knowledge about what they are, beside the recepe how to transform `a`'s into `b` given by `f`.  This limits what `map f` can do to a list of `a`'s.

Best regards,
Marcin Szamotulski

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, December 18th, 2020 at 19:30, Lawrence Bottorff <[hidden email]> wrote:

I'm looking at this

ghci> :type map
map :: (a -> b) -> [a] -> [b]


and wondering what the (a -> b) part is about. map takes a function and applies it to an incoming list. Good. Understood. I'm guessing that the whole Haskell type declaration idea is based on currying, and I do understand how the (a -> b) part "takes" an incoming list, [a] and produces the [b] output. Also, I don't understand a and b very well either. Typically, a is just a generic variable, then b is another generic variable not necessarily the same as a. But how are they being used in this type declaration?

LB

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

signature.asc (522 bytes) Download Attachment