[Haskell-beginners] map type explanation

[David James]

Hello - some additional comments:


  1.  You should probably read this<http://learnyouahaskell.com/higher-order-functions>, 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: Lawrence Bottorff<mailto:borgauf at gmail.com>
Sent: 19 December 2020 03:37
To: Bruno Barbier<mailto:brubar.cs at gmail.com>
Cc: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell<mailto:beginners at haskell.org>
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 <brubar.cs at gmail.com<mailto:brubar.cs at gmail.com>> wrote:

Hi Lawrence,

Lawrence Bottorff <borgauf at gmail.com<mailto:borgauf at gmail.com>> 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 <utprimum at gmail.com<mailto:utprimum at gmail.com>> 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 <borgauf at gmail.com<mailto:borgauf at gmail.com>> 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 <toad3k at gmail.com<mailto:toad3k at gmail.com>> 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 <borgauf at gmail.com<mailto:borgauf at gmail.com>>
>>>> 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
>>>>> Beginners at haskell.org<mailto:Beginners at haskell.org>
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>>
>>>> _______________________________________________
>>>> Beginners mailing list
>>>> Beginners at haskell.org<mailto:Beginners at haskell.org>
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners at haskell.org<mailto:Beginners at haskell.org>
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org<mailto:Beginners at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org<mailto:Beginners at haskell.org>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20201219/bb283754/attachment-0001.html>