Difference between revisions of "Generic function"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
m ({{C-class}})
 
(2 intermediate revisions by one user not shown)
Line 1: Line 1:
{{Start-class}}
+
{{C-class}}
A '''generic function''' is a [[function]] that can take in different [[object]] types and operate on all of them. This is especially helpful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022| the variety of number representations] we learned in lecture.
+
A '''generic function''' is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.g3901816cf_022 the variety of number representations] we learned in lecture.
  
== Creating a generic function ==
+
== Techniques ==
The following techniques are convenient ways to create a generic function:
+
The following are techniques for creating generic functions:
 +
 
 +
=== Interfaces ===
 +
An interface manipulates different data types with the same function. For example, the <code>+</code> operator works with numbers, strings, and lists:
 +
<syntaxhighlight lang="python">
 +
>>> 1 + 2
 +
3
 +
>>> 'hi ' + 'there'
 +
'hi there'
 +
>>> [1, 2] + [3, 4]
 +
[1, 2, 3, 4]
 +
</syntaxhighlight>
  
 
=== Type dispatching ===
 
=== Type dispatching ===
''Type dispatching'' does exactly as its name suggests: depending on the type of the arguments passed in, the function will proceed in different ways. This is especially convenient because it means you can create a general function that will work for a variety of different things.  
+
''Type dispatching'' is a technique in which a function checks the type of the argument passed in and then executes code that is appropriate for the type. To accomplish this, we define a function for each type-operation combination.
  
====example: a <code>drive</code> function====
+
For example, consider the following <code>drive</code> function, which takes in a variety of <code>car</code> types and returns the correct <code>drive</code> method depending on the type given:
Consider the following <code>drive</code> function, which takes in a variety of <code> car </code> types and returns the correct <code>drive</code> method depending on the type given.
+
<syntaxhighlight lang="python">
<syntaxhighlight lang="python" highlight=3>
+
 
def drive(car):
 
def drive(car):
 
     if type(car) == SportsCar:
 
     if type(car) == SportsCar:
Line 22: Line 32:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
=== Coercion ===
+
==== Tag-based ====
Another way of implementing generic functions is through ''coercion'', which is simply converting our original object into a new type of object so that we can use the new object's methods. This is especially helpful when the two different objects have some similar properties, and when our original object can be seen as a the new type with certain modifications.
+
We can implement type dispatching using dictionaries. We define a function <code>type_tag</code> that returns a "tag" representing the type of the argument (the tag is stored in the <code>tags</code> dictionary):
 +
<syntaxhighlight lang="python">
 +
def type_tag(x):
 +
    return tags[type(x)]
  
====example: a function====
+
tags = {
 +
    <type1> : <tag1>
 +
    <type2> : <tag2>
 +
    ...
 +
}
 +
</syntaxhighlight>
  
 +
We also define a dictionary <code>implementations</code> that maps from a tuple of the two types to the function that carries out the operation on those types.
 +
<syntaxhighlight lang="python">
 +
implementations = {
 +
    (<tag1>, <tag1>): <fn1>,
 +
    (<tag1>, <tag2>): <fn2>,
 +
    (<tag2>, <tag2>): <fn3>
 +
}
 +
</syntaxhighlight>
  
 +
Then we can write a generic function as follows:
 +
<syntaxhighlight lang="python">
 +
def op(a, b):
 +
    return implementations[(type_tag(a),type_tag(b))](a, b)
 +
</syntaxhighlight>
  
== Sources ==
+
For example, here is a generic function to combine two lists (the two possible types are [[Linked list|<code>Link</code>]] and the built-in <code>[[list]]</code>):<ref>https://inst.eecs.berkeley.edu/~cs61a/sp13/labs/lab08/lab08.php</ref>
[https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p| CS61A Su14 Lecture 17]
+
<syntaxhighlight lang="python">
 +
def type_tag(x):
 +
    return tags[type(x)]
  
[http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf| CS61A Su14 Discussion 9]
+
tags = {
 +
    list : 'list'
 +
    Link : 'Link'
 +
}
  
[http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations| CS61A Fa11 2.7.3]
+
implementations = {
 +
    ('list', 'list'): lambda a, b: a.extend(b),
 +
    ('list', 'Link'): extend_list_with_link,
 +
    ('Link', 'Link'): extend_link_with_link,
 +
    ('Link', 'list'): extend_link_with_list
 +
}
 +
 
 +
def extend(lst1, lst2):
 +
    implementations[(type_tag(lst1), type_tag(lst2))](lst1, lst2)
 +
</syntaxhighlight>
 +
 
 +
<code>extend_list_with_link</code>, <code>extend_link_with_link</code>, and <code>extend_link_with_list</code> are not shown.
 +
 
 +
=== Coercion ===
 +
''Coercion'' is converting object A into object B so that A can use B's methods. The general process is:<ref>http://inst.eecs.berkeley.edu/~cs61a/fa12/slides/19-Generics_1pps.pdf</ref>
 +
# Attempt to coerce arguments into values of the same type
 +
# Apply type-specific operations
 +
 
 +
Example:<ref>http://shire.keeganmann.com/~ta/review-typedispatch.html</ref> we have a class representing metric distances:
 +
<syntaxhighlight lang="python">
 +
class MetricDistance:
 +
    def __init__(self, x):
 +
        self.dist = x # assume x is in meters
 +
       
 +
    def compare(self, other):
 +
        """Returns '<', '>' or '=' when comparing self to other."""
 +
        if self.dist < other.dist:
 +
            return '<'
 +
        elif self.dist == other.dist:
 +
            return '='
 +
        else:
 +
            return '>'
 +
</syntaxhighlight>
 +
 
 +
We also have a class representing imperial distances:
 +
<syntaxhighlight lang="python">
 +
class ImperialDistance:
 +
    def __init__(self, x):
 +
        self.dist = x # assume x is in feet
 +
</syntaxhighlight>
 +
 
 +
We want to write a function to compare a <code>MetricDistance</code> and an <code>ImperialDistance</code>. Since <code>MetricDistance</code> already has a <code>compare</code> function, we coerce <code>ImperialDistance</code> to a <code>MetricDistance</code> so we can compare them:
 +
<syntaxhighlight lang="python">
 +
def coerce_imperial_to_metric(imperial):
 +
    return MetricDistance(imperial.dist * 0.3048)
 +
 
 +
def compare_imperial_and_metric(imperial, metric):
 +
    return coerce_imperial_to_metric(imperial).compare(metric)
 +
</syntaxhighlight>
 +
 
 +
== Sources ==
 +
<references/>
 +
* [https://docs.google.com/presentation/d/1AZSqH0-tbjwJXXZcaqaFnDnfCP-g4wMOxzVPz3aPc4M/edit#slide=id.p CS61A Su14 Lecture 17]
 +
* [http://inst.eecs.berkeley.edu/~cs61a/su14/discussion/discussion09/discussion09.pdf CS61A Su14 Discussion 9]
 +
* [http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#generic-operations CS61A Fa11 2.7.3]

Latest revision as of 22:42, 24 July 2014

A generic function is a function that can operate on multiple types of data. This is especially useful when the objects we are working with have multiple representations. A good example is the variety of number representations we learned in lecture.

Techniques

The following are techniques for creating generic functions:

Interfaces

An interface manipulates different data types with the same function. For example, the + operator works with numbers, strings, and lists:

>>> 1 + 2
3
>>> 'hi ' + 'there'
'hi there'
>>> [1, 2] + [3, 4]
[1, 2, 3, 4]

Type dispatching

Type dispatching is a technique in which a function checks the type of the argument passed in and then executes code that is appropriate for the type. To accomplish this, we define a function for each type-operation combination.

For example, consider the following drive function, which takes in a variety of car types and returns the correct drive method depending on the type given:

def drive(car):
    if type(car) == SportsCar:
        return car.drive_sportscar()
    elif type(car) == Van:
        return car.drive_van()
    elif type(car) == SemiTruck:
        return car.drive_semitruck()
    elif type(car) == Tractor:
        return car.drive_tractor()

Tag-based

We can implement type dispatching using dictionaries. We define a function type_tag that returns a "tag" representing the type of the argument (the tag is stored in the tags dictionary):

def type_tag(x):
    return tags[type(x)]
 
tags = {
    <type1> : <tag1>
    <type2> : <tag2>
    ...
}

We also define a dictionary implementations that maps from a tuple of the two types to the function that carries out the operation on those types.

implementations = {
    (<tag1>, <tag1>): <fn1>,
    (<tag1>, <tag2>): <fn2>,
    (<tag2>, <tag2>): <fn3>
}

Then we can write a generic function as follows:

def op(a, b):
    return implementations[(type_tag(a),type_tag(b))](a, b)

For example, here is a generic function to combine two lists (the two possible types are Link and the built-in list):[1]

def type_tag(x):
    return tags[type(x)]
 
tags = {
    list : 'list'
    Link : 'Link'
}
 
implementations = {
    ('list', 'list'): lambda a, b: a.extend(b),
    ('list', 'Link'): extend_list_with_link,
    ('Link', 'Link'): extend_link_with_link,
    ('Link', 'list'): extend_link_with_list
}
 
def extend(lst1, lst2):
    implementations[(type_tag(lst1), type_tag(lst2))](lst1, lst2)

extend_list_with_link, extend_link_with_link, and extend_link_with_list are not shown.

Coercion

Coercion is converting object A into object B so that A can use B's methods. The general process is:[2]

  1. Attempt to coerce arguments into values of the same type
  2. Apply type-specific operations

Example:[3] we have a class representing metric distances:

class MetricDistance:
    def __init__(self, x):
        self.dist = x # assume x is in meters
 
    def compare(self, other):
        """Returns '<', '>' or '=' when comparing self to other."""
        if self.dist < other.dist:
            return '<'
        elif self.dist == other.dist:
            return '='
        else:
            return '>'

We also have a class representing imperial distances:

class ImperialDistance:
    def __init__(self, x):
        self.dist = x # assume x is in feet

We want to write a function to compare a MetricDistance and an ImperialDistance. Since MetricDistance already has a compare function, we coerce ImperialDistance to a MetricDistance so we can compare them:

def coerce_imperial_to_metric(imperial):
    return MetricDistance(imperial.dist * 0.3048)
 
def compare_imperial_and_metric(imperial, metric):
    return coerce_imperial_to_metric(imperial).compare(metric)

Sources

  1. https://inst.eecs.berkeley.edu/~cs61a/sp13/labs/lab08/lab08.php
  2. http://inst.eecs.berkeley.edu/~cs61a/fa12/slides/19-Generics_1pps.pdf
  3. http://shire.keeganmann.com/~ta/review-typedispatch.html