How to calculate type of (.)(.) in Haskell? I know that it should be
(.)(.) :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c
But how to calculate it without computer?
-
1W h a t H a v e Y o u T r i e d ?leftaroundabout– leftaroundabout2015-04-26 09:11:19 +00:00Commented Apr 26, 2015 at 9:11
-
i know that (.) :: (b->c)->(a->b) -> (a->c).Jan kowalski– Jan kowalski2015-04-26 09:16:27 +00:00Commented Apr 26, 2015 at 9:16
-
I think that (.)(.) should be (d->c)->(b->c)->(a->b)->(a->d) but it is wrongJan kowalski– Jan kowalski2015-04-26 09:17:16 +00:00Commented Apr 26, 2015 at 9:17
-
Alright, but how did you come by that conjecture?leftaroundabout– leftaroundabout2015-04-26 09:23:37 +00:00Commented Apr 26, 2015 at 9:23
Add a comment
|
3 Answers
(.) :: (b -> c ) -> ((a -> b) -> (a -> c))
(.) :: ((e -> f) -> ((d -> e) -> (d -> f)))
(.)(.) :: ((a -> (e -> f)) -> (a -> ((d -> e) -> (d -> f))))
(.)(.) :: (a -> (e -> f)) -> (a -> ((d -> e) -> (d -> f)))
(.)(.) :: (a -> e -> f) -> a -> ((d -> e) -> (d -> f))
(.)(.) :: (a -> e -> f) -> a -> (d -> e) -> (d -> f)
(.)(.) :: (a -> e -> f) -> a -> (d -> e) -> d -> f
Comments
by (manual) pattern-matching and rewriting types-variables
(.) has type (b -> c) -> ((a -> b) -> a -> c) so the first argument should have type b -> c.
Now if we use it again we have to substitute b with b' -> c' and c with (a' -> b') -> a' -> c') (the second (.) should have type (b' -> c') -> ((a' -> b') -> a' -> c')) and we get
(a -> b' -> c') -> a -> (a' -> b') -> a' -> c'
which is (after renaming) the same as above.
Note that I used a -> b -> c = a -> (b -> c) here
using GHCi
yeah I know - you want it by hand - but GHCi is such a valuable tool that you really should use it to confirm your manual labor.
Here from a terminal:
$ ghci
GHCi, version 7.10.1: http://www.haskell.org/ghc/ :? for help
Prelude> :t (.)(.)
(.)(.) :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c
Prelude>
as you can see the type is (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c
btw: :t is short for :type and you can see all commands with :help from inside a GHCi session.
8 Comments
ThreeFx
I think the OP wants to know how to figure this out using pen & paper.
Jan kowalski
Yes, i want solution without computer (as i wrote above).
Jan kowalski
Why you need to substitute c with (a' -> b') -> a' -> c') ?
Random Dev
becase this is the second argument of the function I put into
(.) (the second (.))Random Dev
see: you can look at
(.) of beeing a function, that waits for a function b -> c and then returns a function ((a -> b) -> a -> c) now this function is (.) again and I don't want to mess up the types and so added ticks (') to differentiate |
Since I wasn't particularly satisfied with the missing explanations in the accepted answer, I give my POV as well:
-- this is the original type signature
(.) :: (b -> c) -> (a -> b) -> a -> c
-- now because of haskell polymorphism,
-- even 'b' and 'c' and so on could be functions
--
-- (.)(.) means we shove the second function composition
-- into the first as an argument.
-- Let's give the second function a distinct type signature, so we
-- don't mix up the types:
(.) :: (e -> f) -> (d -> e) -> d -> f
-- Since the first argument of the initial (.) is of type (b -> c)
-- we could say the following if we apply the second (.) to it:
(b -> c) == (e -> f) -> (d -> e) -> d -> f
-- further, because of how currying works, as in
(e -> f) -> (d -> e) -> d -> f == (e -> f) -> ((d -> e) -> d -> f)
-- we can conclude
b == (e -> f)
c == (d -> e) -> d -> f
-- since we passed one argument in, the function arity changes,
-- so we'd actually only have (a -> b) -> a -> c left, but that
-- doesn't represent the types we have now, so we have to substitute
-- for b and c, so
(a -> b) -> a -> c
-- becomes
(.)(.) :: (a -> (e -> f)) -> a -> (d -> e) -> d -> f
-- and again because of currying we can also write
(.)(.) :: (a -> e -> f) -> a -> (d -> e) -> d -> f
