Generic function

From CS 61A Wiki
(Redirected from Generic functions)
Jump to: navigation, search

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