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

[Brandon Allbery]

On Wed, Jul 6, 2011 at 09:43, Steffen Schuldenzucker
<sschuldenzucker at uni-bonn.de> wrote:
>
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
brandon s allbery                                      allbery.b at gmail.com
wandering unix systems administrator (available)     (412) 475-9364 vm/sms