Difference between revisions of "Generic function"

From CS 61A Wiki
Jump to: navigation, search
[unchecked revision][checked revision]
m (Axis moved page Generic functions to Generic function: singular)
m ({{C-class}})
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
<p>A Generic Function is one that can take in different object types and operate on all of them.</p>
+
{{C-class}}
<p></p>
+
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.
 +
 
 +
== Techniques ==
 +
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'' 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 <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">
 +
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()
 +
</syntaxhighlight>
 +
 
 +
==== Tag-based ====
 +
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)]
 +
 
 +
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>
 +
 
 +
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>
 +
<syntaxhighlight lang="python">
 +
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)
 +
</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