CODEWITHSUNDEEP
haskellfunction-composition
beardc
beardc

Reputation: 21063

How does composing with id change type

If the type of foldr is

> :t foldr
forall a b. (a -> b -> b) -> b -> [a] -> b

and

> :t id
forall a. a -> a

then I would expect foldr (.) id to have the same type as foldr, rather than

> :t foldr (.) id
forall b. [b -> b] -> b -> b

It appears I'm mistaken about how composition works, because I had thought that for a function f that f . id would give f(id(x)) == f(x), preserving the type of f. What am I misunderstanding that would clarify the meaning of foldr (.) id and composition more generally?

Upvotes: 4

Views: 158

Answers (3)

leftaroundabout
leftaroundabout

Reputation: 120741

This is not composition with id, as you'd get from foldr . id (notice the absence of parens). That would indeed be equivalent to foldr alone, perhaps the most important equivalency in category theory and thus also fundamental to Haskell.

Instead, what you've done there is, passed both (.) and id as arguments to foldr: putting . in parens makes it just another expression so ordinary Haskell function parsing applies, i.e. greedily use consecutive terms as arguments to the first one. You're lucky that this makes for a good type at all, for instance succ (.) id would have given the ridiculous signature Enum ((c -> c) -> (a -> c) -> a -> c) => (a -> c) -> a -> c.

How exactly it works with foldr can be seen by writing

 (.) :: (y->z) -> (x->y) -> (x->z)

unify (x->y) = (x->z) as in foldr's argument, i.e. y = z,

 (.) :: (y->y) -> (x->y) -> (x->y)

 foldr (.) :: (x->y) -> [y->y] -> (x->y)

Then id also requires x = y,

 foldr (.) id :: [x->x] -> (x->x)

Upvotes: 11

isekaijin
isekaijin

Reputation: 19772

You are not composing foldr with id. That would be foldr . id. What you are actually doing is applying foldr to (.), and then applying the result of such application to id.

Upvotes: 6

Emil
Emil

Reputation: 2167

What you are saying here is that you are going to be composing a list of functions who all have the same type (since they are in a list). id is the initial function that you'll be folding from. When you are done composing all of them, you'll get back a function. It might be easier to see the result type as [b -> b] -> (b -> b).

By the way, when you use an operator in Haskell and you want to infix it, you omit the parantheses. Only when you are using it as any other function do you include the parantheses.

Upvotes: 1

Related Questions