[Haskell-cafe] Deducing a type signature

Dan Weston westondan at imageworks.com
Wed May 19 19:23:49 EDT 2010


 > (i)  strange f g = g (f g)
 >
 > Assume g :: a -> b.  Then f :: (a -> b) -> c.  But since g :: a -> b,
 > f g :: a, so c = a.  Therefore, f :: (a -> b) -> a, and g (f g) :: a.
 > Therefore, strange :: ((a -> b) -> a) -> (a -> b) -> a.

Almost. The return type of strange is the same as the return type of g 
(the outermost function), namely b.

So strange :: ((a -> b) -> a) -> (a -> b) -> b.

Dan

R J wrote:
> Bird 1.6.3 requires deducing type signatures for the functions "strange" 
> and "stranger."
> 
> Are my solutions below correct?
> 
> (i)  strange f g = g (f g)
> 
> Assume g :: a -> b.  Then f :: (a -> b) -> c.  But since g :: a -> b,
> f g :: a, so c = a.  Therefore, f :: (a -> b) -> a, and g (f g) :: a.
> Therefore, strange :: ((a -> b) -> a) -> (a -> b) -> a.
> 
> (ii)  stranger f = f f
> 
> Assume f :: a -> b.  Since "f f" is well-typed, type unification requires
> a = b.  Therefore, f :: a -> a, and stranger :: (a -> a) -> a.
> 
> ------------------------------------------------------------------------
> Hotmail is redefining busy with tools for the New Busy. Get more from 
> your inbox. See how. 
> <http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_2>
> 



More information about the Haskell-Cafe mailing list