[Haskell-cafe] Arrow instance of function type [a] -> [b]

[Steffen Schuldenzucker]

Hi Markus,

On 07/06/2011 03:04 PM, Markus Läll wrote:
> [...]
>
> import Control.Arrow
> import Control.Category
>
> type X a b = [a] ->  [b]
>
> instance Category X where
>     id = map Prelude.id
>     g . f = g Prelude.. f
>
> instance Arrow X where
>     arr f = map f
>     first f = unzip>>>  first f>>>  uncurry zip
>
> The problem is that it's not allowed to use partially applied type
> synonyms. It is however possible to define a type synonym which value
> is a partially applied type, but I haven't been able to figure out if
> I could somehow use that fact in defining the X... Is it at all
> possible, or is a newtype the only way to do it?
>

You should really use a newtype for that. Allowing partially applied 
type synonyms would greatly increase the expressiveness of the type 
language. (too much, actually)
In fact, you could write arbitrary type level lambdas, like that:

 > type Y b a = [a] -> [b]

But now, given instances like this:

 > instance Category X where ...
 >
 > instance Category Y where ...
 > -- uh, yeah, does it make sense in this case? Whatever, we *could* 
have an instance.

, any function of type [a] -> [b] will match both instances. So which 
instance to choose? We have two solutions:

a) The compiler discovers itself that we have overlaps here and complains.

This seems hard to me (is it even possible in finite time?). Note that 
it is easy if type synonyms are always fully applied because the 
compiler just has to fill in the definition of all the types and can 
then proceed to compare just the instance *heads*.

b) You somehow annotate which instance to choose for each specific case. 
But that's exactly what newtypes are for!

The problem does indeed occur in your example: What is (id :: [a] -> 
[b]) supposed to be, Prelude.id (as given by the general instance for 
functions) or map Prelude.id (given by your instance)?

-- Steffen