[Haskell-cafe] Hoogle? [Stacking monads]

[Andrew Coppin]

Mitchell, Neil wrote:
> Hi
>
>   
>> Try doing a Hoogle search for "c1 (c2 x) -> c2 (c1 x)". 
>> Hoogle correctly states that Data.Traversable.sequence will 
>> do it for you.
>>
>> Now try doing "c1 k (c2 x) -> c2 (c1 k x)". The 'sequence' 
>> function will also do this, but now Hoogle returns 0 results.
>>
>> This is puzzling, since AFAIK, the above two type signatures 
>> are "equvilent" in some sense. (Specifically, replace every 
>> type X with type Y and you get from one to the other.) To me, 
>> this looks like a Hoogle bug. (It goes without saying that 
>> Hoogle also failed to find anything for the more specific 
>> type signature I was searching for, despite the fact that 
>> 'sequence' unifies with it.)
>>     
>
> Hoogle is not a "unification engine" - since that is very rarely what
> people want out of a type search engine. What it is is an approximate
> matcher. Let's compare the two types:
>
> Your search :: c1 k (c2 x) -> c2 (c1 k x)
>
> sequence :: Monad m => [m a] -> m [a]
>   

Actually, I was thinking more along the lines of 
Data.Traversable.sequence, which has

  sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

> Are you expecting c1 (:: * -> * -> *) to unify with [] (:: * -> *)? That
> seems kind incorrect at the very last. Additionally, those types don't
> look all that close.
>   

Well, as I said, replacing one term with another transforms one 
signature into the other. I guess you can't curry type constructors as 
easily as functions - or at least, Hoogle currently doesn't like it.

> But, let's briefly consider unification (and why Hoogle doesn't used
> it). Consider the search:
>
> Eq a => [(a,b)] -> a -> b
>
> What the user wants is lookup, which sadly doesn't unify. However,
> undefined unifies perfectly.
>   

I see...

I notice that x -> y doesn't unify with y -> x in any way, shape or 
form, but Hoogle has absolutely no problem with that. What *does* Hoogle 
actually use for matching? Just a set of huristics and a metric for how 
"similar" two signatures are so it can order by approximate similarity? 
Or is it something more scientific than that?