Implement Map

Computer Science Level 1

Map is a function which takes another function and applies it to each item in a list, returning the new list. 

1
2
3
 
def map(the_function, the_list):
    # return a new list with the_function
    # applied to each element in the_list

Using only head and tail as defined by the List ADT , implement map .

Use your implementation of map to apply the function 

1
2
 
def polynomial(x):
    return 3 * x * x - 5 * x + 1

to the list [ 32 , 57 , 16 , 8 , 38 ] [32, 57, 16, 8, 38] .

[ 992 , 3192 , 240 , 56 , 1406 ] [992, 3192, 240, 56, 1406] [ 928 , 3078 , 208 , 40 , 1330 ] [928, 3078, 208, 40, 1330] [ 2913 , 9463 , 689 , 153 , 4143 ] [2913, 9463, 689, 153, 4143] [ 5025 , 16075 , 1233 , 297 , 7107 ] [5025, 16075, 1233, 297, 7107]

Kristian Takvam by Kristian Takvam

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Kristian Takvam Staff
Mar 3, 2016

Using the Python implementation from the Lists wiki . 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
def polynomial(x):
    return 3 * x * x - 5 * x + 1


def map_list(the_function, the_list):
    if the_list.is_empty():
        return List()
    else:
        new_list = map_list(the_function, the_list.tail())
        new_list.prepend(the_function(the_list.head()))
        return new_list


some_numbers = List()
some_numbers.append(32)
some_numbers.append(57)
some_numbers.append(16)
some_numbers.append(8)
some_numbers.append(38)
print(map_list(polynomial, some_numbers))


1
 
[2913,9463,689,153,4143]

6 Helpful 0 Interesting 0 Brilliant 3 Confused

The question says you can only use head and tail, but at the very least you would also need the constructor function ("prepend" from the List ADT). Depending on list implementation you may also need a function to get the initial object ("new" from the List ADT). There is no way to implement map without them.

Kelden Cowan - 2 years, 5 months ago

I never used Python before, but I think that the results may be hand typed; here’s what I found: If you pick the number 8 and proceed with the formula, you won’t get the result that’s shown. Formula: 3 x x - 5*x+1 -> 3 * 8 * 8 = 24 * 8 = 172 -> 5 * 8 +1 = 41 So, 172 - 41 = 131, not 153. If I did something wrong, I’m struggling very hard to know what is it; Just wanna let you know ‘bout it. Excluding that little issue, I’m learning Python thanks to that guide, so don’t mind me if I’m wrong. Again, great job :)

Chark Rios - 2 years, 2 months ago

Log in to reply

Actually, 24*8 is 192. So: 192 - 40 + 1 => 153 p.s. you should always first do multiplication, divide or whatever is in the curly braces, after that you do -+

Nataly Osintseva - 1 year, 5 months ago
Kumaran Kumaran
Oct 8, 2018 
1
2
3
4
5
6
7
 
def map(the_function, the_list):
    new_list = List()
    current_list = the_list
    while not current_list.is_empty():
        new_list.append(the_function(current_list.head()))
        current_list = current_list.tail()
    return new_list

2 Helpful 0 Interesting 0 Brilliant 0 Confused 
1
2
3
4
5
6
7
8
9
 
def map(the_function, the_list):

    if not the_list.is_empty():
        current_node = the_list.head_node
        current_node.value = the_function(current_node.value)

        map(the_function, the_list.tail())

    return the_list

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...