If parametric polymorphism is dispatching without depending on the types of the parameters then what else is there to dispatch upon other than the arity? If it isn't the same could someone provide a counter example?
Is parametric polymorphism the same as dispatching on arity?
270 Views Asked by PuercoPop At
1
There are 1 best solutions below
Related Questions in TYPES
- How to know a Pod's own IP address from inside a container in the Pod?
- Who will decide the "specified number of pods" for replication controller in kubernetes?
- Access other containers of a pod in Kubernetes
- Kubernetes cluster using Vagrant not working after restart
- kubectl not installed with gcloud SDK
- How do I access the Kubernetes api from within a pod container?
- Exposing several services with Vagrant and Kubernetes on my own server
- Does Kubernetes provision new VMs for pods on my cloud platform?
- Any suggestion for running Aerospike on Kubernetes on CoreOS on GCE?
- Kubernetes - kubectl exec bash - session drop and line width
Related Questions in PROGRAMMING-LANGUAGES
- How to know a Pod's own IP address from inside a container in the Pod?
- Who will decide the "specified number of pods" for replication controller in kubernetes?
- Access other containers of a pod in Kubernetes
- Kubernetes cluster using Vagrant not working after restart
- kubectl not installed with gcloud SDK
- How do I access the Kubernetes api from within a pod container?
- Exposing several services with Vagrant and Kubernetes on my own server
- Does Kubernetes provision new VMs for pods on my cloud platform?
- Any suggestion for running Aerospike on Kubernetes on CoreOS on GCE?
- Kubernetes - kubectl exec bash - session drop and line width
Related Questions in TYPE-THEORY
- How to know a Pod's own IP address from inside a container in the Pod?
- Who will decide the "specified number of pods" for replication controller in kubernetes?
- Access other containers of a pod in Kubernetes
- Kubernetes cluster using Vagrant not working after restart
- kubectl not installed with gcloud SDK
- How do I access the Kubernetes api from within a pod container?
- Exposing several services with Vagrant and Kubernetes on my own server
- Does Kubernetes provision new VMs for pods on my cloud platform?
- Any suggestion for running Aerospike on Kubernetes on CoreOS on GCE?
- Kubernetes - kubectl exec bash - session drop and line width
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Parametric Polymorphism
The idea behind parametric polymorphism is that you don't dispatch—a parametrically polymorphic function is one that behaves in the same way for all input types. Let's consider a very simple example (I'm going to use Haskell1):
This defines a function named
id
which takes one argument,x
, and returns it. This is the identity function; it doesn't do anything. Now, what type shouldid
have? It's definitely a function, so it will have the typeinput -> output
for someinput
andoutput
. We could say thatid
has typeInt -> Int
; thenid 3
would evaluate to3
, butid True
wouldn't typecheck, which seems silly. Sayingid :: Bool -> Bool
is no better; the problem is reversed. We know that forid
, it doesn't matter what type the input is;id
ignores that structure and just passes the value around. So for any typea
,id
has typea -> a
, and we can write this explicitly:In Haskell, lowercase identifiers in types are are universally quantified variables—the above signature is the same as if I'd written
id :: forall a. a -> a
, except that writing theforall
explicitly is only valid with some language extensions.The identity function is the simplest example of a parametrically polymorphic function, and it highlights the idea that parametric functions simply pass data around. They can't examine the data to do anything with it.
Let's consider a slightly more interesting function: list reversal. In Haskell, lists of some type
a
are written[a]
, so thereverse
function isThe
reverse
function shuffles the elements of the list around, but it never manipulates them (and hence never "dispatches" on them). Hence,reverse
knows it must take and return lists of something—but it doesn't care what that something is.One last example of parametric polymorphism is the
map
function. This function takes a functionf
and a list, and applies that function to each element in the list. This description tells us that we don't care about the input or output types of the function, and nor do we care about the type of the input list—but they must match up appropriately. Thus, we haveNote that the input (respectively output) type of the passed-in function and the type of the elements of the input (respectively output) list must match; however, the input and output types can be distinct from each other or not, we don't care.
Parametric Polymorphism and Subtyping
You ask, in a comment, if parametric functions just accept values of the top type. The answer is no: subtyping is completely independent of parametric polymorphism. Haskell doesn't have any notion of subtyping at all: an
Int
is anInt
, and aBool
is aBool
, and never the twain shall meet. In Java, you have both generics and subtyping, but the two features are semantically unrelated (unless you use bounded polymorphism of the form<T extends Super>
, but this is more like a form of ad-hoc polymorphism, which I discuss below). Parametric polymorphism really is what it says: functions that accept any type. This is not the same as functions that accept a top type and rely on subsumption/implicit upcasting. One way to think about it is that parametric functions take an additional argument: the type of the parameter. So instead ofid 3
, you would haveid Int 3
; instead ofid True
, you would haveid Bool True
. In Haskell, you never need to do this explicitly, so there's no syntax for it. On the other hand, in Java, you sometimes need to, and so there's syntax which reflects this, as inCollections.<String>emptyList()
.Ad-hoc Polymorphism
Parametric polymorphism often contrasts with various forms of ad-hoc polymorphism: polymorphism that allows one function to behave in different ways at different types. This is where "dispatch" shows up; where parametric polymorphism is about uniformity, ad-hoc polymorphism is about differences. Sometimes you don't want a function to act the same way at every type!
Standard Java-like object-oriented subtype polymorphism, which is formally called nominal subtyping, is an example of this; in Java, for instance, the
boolean Object.equals(Object)
method uses subtype polymorphism to dispatch on its first argument and return the appropriate result. It's clear that you wouldn't want equality to be parametric; you can't write one function that accurately compares both strings and integers for equality! Note, however, that.equals
also usesinstanceof
to perform a "typecase" check of the run-time type of the argument; theint Object.hashCode()
method is an example of a purely subtype-polymorphic method.Haskell uses a different approach, called type-class polymorphism, to handle this. Here's a whirlwind tour of how that works. First, we say what it means to be comparable for equality (note that Haskell lets you define function names which are arbitrary operators, and then use them infix):
Then, we instantiate the type class; for instance, here we say how to compare booleans for equality.
And when we want to compare elements for equality, we specify that we must have a type which satisfies the appropriate constraint. For instance, the
elem
function which checks if an element occurs in a list has typeEq a => a -> [a] -> Bool
; we can read this as "for anya
which is an instance ofEq
,elem
expects ana
and a list ofa
s, and returns a boolean":Here, the
elem
function is not parametrically polymorphic, because we have some information about the typea
—we know that we can compare its elements for equality. Consequently,elem
will not behave in the same way for every input type (and there are some types we can't even compare for equality, such as functions), and so there's a form of type-based dispatch going on here, too.1 In case you're more familiar with languages like Java, the same function in Java would be (ignoring the containing class)
Note that Java, unlike Haskell, allows you to violate parametricity by using the
instanceof
operator or calling methods like.toString()
that are always available, but ourid
function doesn't do that.