[Haskell-cafe] Re: distinguish functions from non-functions in
jonathanccast at fastmail.fm
Tue Dec 11 00:38:21 EST 2007
On 10 Dec 2007, at 11:33 AM, Dan Weston wrote:
> Questioning apfelmus definitely gives me pause, but...
> > id :: a -> a -- "arity" 1
> > id = ($) :: (a -> b) -> (a -> b) -- "arity" 2
> I agree with the arities given above (but without quotes) and see
> no ill-definedness to arity.
> But these are two different classes of functions. There are
> arguments of the first function that cannot be applied to the
> second (e.g. 5). The fact that the two have different type
> signatures shows that Haskell can distinguish them (e.g. in the
> instantiation of a type class)
Not really. The types of id and ($) can't be instances of a type
class, since an instance of a type class has to be a monomorphic
type. So the decision as to which instance to use has to be made
based on the particular monomorphic type id or ($) is used at. But
that monomorphic type may still contain free type variables; those
type variables themselves represent some single monomorphic type,
which may or may not be a function type. So we still don't know what
the arity of an arbitrary expression is. (We don't know what its
type is, even the way we know the type of id or ($), if it or any of
its free variables is lambda-bound).
> The difficulties of Haskell's type system in the presence/
> intersection of ad hoc/parametric polymorphism is an orthogonal
> issue. I think that every function application must have a unique
> monomorphic type at the call site of the "arity" function (assisted
> or not by type annotation), and this type is known to converge in a
> Template Haskell construction.
> > We have to specialize the type of id before
> > supplying it to wrap . For example,
> > wrap (id :: Int -> Int)
> > works just fine.
> The necessity of type annotation/restriction is an orthogonal issue
> to the above.
> Am I missing something more fundamental?
> apfelmus wrote:
>> Luke Palmer wrote:
>>> Hmm, this still seems ill-defined to me.
>>> compose :: (Int -> Int -> Int) -> (Int -> Int) -> Int -> Int -> Int
>>> Is a valid expression given that definition (with a,b = Int and c
>>> = Int -> Int),
>>> but now the arity is 4.
>> That's correct, the arity of a function is not well-defined due to
>> polymorphism. The simplest example is probably
>> id :: a -> a -- "arity" 1
>> id = ($) :: (a -> b) -> (a -> b) -- "arity" 2
>> Therefore, the polymorphic expression
>> wrap id
>> is problematic. It roughly has the type
>> wrap id ~~ [String] -> a
>> But it's clearly ambiguous: do we have
>> wrap id (x:_) = read x
>> wrap id (f:x:_) = wrap ($) (f:x:_) = read f (read x)
>> or what? (assuming a read instance for function types)
>> GHCi gives it a type
>> > :type wrap id
>> wrap id :: (FunWrap (a -> a) y) => [String] -> y
>> but trying to use it like in
>> > let x = wrap id ["1"] :: Int
>> yields lots of type errors. We have to specialize the type of id
>> before supplying it to wrap . For example,
>> wrap (id :: Int -> Int)
>> works just fine.
>> I don't like this behavior of wrap since it violates the nice
>> property of polymorphic expressions that it's unimportant when a
>> type variable is instantiated, like in
>> map ((+1) :: Int -> Int) [1..5]
>> = map (+1) ([1..5] :: [Int])
>> = (map (+1) [1..5]) :: [Int]
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe