<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 関数型プログラミング (Functional Programming)
```
ASSIGNMENT METADATA
assignment_id
Step1:  lang
Step2:  lang
Step3:  lang
Step4:  lang
Step5:  lang
Step6:  lang
Step7:  lang
Step9:  5. Exercise
Step11:  5.2. Returning the First Item that Matches a Predicate
lang
Step13:  5.3. Filtering Items in a List
lang
Step15:  5.4. map
Step16:  Aside
Step17:  lang
Step18:  lang
Step19:  lang
Step21:  6. Exercise
<ASSISTANT_TASK:>
Python Code:
# A program that calculates the final grade for each student.
# Scores for Assignment 1, Assignment 2, and Final Exam.
sam_scores = [90, 80, 90]
yuko_scores = [90, 100, 80]
sam_weighted_score = 0.2 * sam_scores[0] + 0.2 * sam_scores[1] + 0.6 * sam_scores[2]
sam_grade = 'PASS' if sam_weighted_score > 60 else 'FAIL'
print('Sam\'s final score: {} => {}'.format(sam_weighted_score, sam_grade))
yuko_weighted_score = 0.2 * yuko_scores[0] + 0.2 * yuko_scores[1] + 0.6 * yuko_scores[2]
yuko_grade = 'PASS' if yuko_weighted_score > 60 else 'FAIL'
print('Yuko\'s final score: {} => {}'.format(yuko_weighted_score, yuko_grade))
Explanation: 関数型プログラミング (Functional Programming)
```
ASSIGNMENT METADATA
assignment_id: "Functional"
```
lang:ja
この講義では 関数型プログラミング (functional programming)というプログラミングスタイルを紹介し、それがプログラミングでどう役に立つかということを説明します。
関数型プログラミングの概念を全く知らなくてもPythonでプログラムを書くことはできますが、理解しておくとより良いプログラムを書くのに役立つでしょう。
lang:en
We will introduce a programming style called "functional programming" and explain how it's useful in Python programming.
Although you can write programs in Python without understanding functional programming, the concept of functional programming should help you to write better programs.
The goal of this lecture is to tell basic concepts of functional programming so that you can make use of them in practical programming.
1. 関数型プログラミングとは (What's functional programming)
lang:ja
この講義で扱う関数型プログラミング (functional programming)(または、関数プログラミング)というのは一般に、「入力から出力が一意に定まる"関数"の適用・合成によってプログラムを記述していくプログラミングスタイル」のことです。
関数型プログラミングには以下のような利点が期待できます:
* データの流れがわかりやすくなる
* プログラムの分割・結合・再利用がしやすくなる
* より高度な抽象化によって、複雑な処理がシンプルにかける
「関数型プログラミング」というようなプログラミングスタイルの分類のことを プログラミングパラダイム (programming paradigm) といいます。
他によく知られているパラダイムには以下のようなものがあります:
* 手続き型プログラミング (procedual programming)
* オブジェクト指向プログラミング (object-oriented programming)
* 宣言型プログラミング (declarative programming)
ただし、プログラミングパラダイムは、守らなければならない厳密なルールや絶対的なものではありません。
むしろ、これらは理論と実践に基づいた、良いとされるプログラミングアプローチのようなものです。
また、それぞれのパラダイムは対立するものではなく、独立な概念であるので、一つのプログラムでこれらのスタイルを共存させることもできます。
例えばオブジェクト指向プログラミングとは、データや処理を"オブジェクト"としてまとめるスタイルですが、PythonではこれはClassを用いることで実現できます。
この講義では、関数型プログラミングのいくつかの基本的な概念を紹介し、実際のプログラミングに役立てられる形で身につけてもらうことを目標とします。
lang:en
Functional programming is generally a programming style in which a program is written by applying / synthesizing a "function" that uniquely determines the output from the input.".
Functional programming can offer the following advantages:
* Easy to understand the flow of data
* Easy to split, combine and reuse programs
* Able to write complex procedures in a simple way
The classification of programming style like "functional programming" is called programming paradigm.
Other well known paradigms include the following:
* Procedural programming
* Object-oriented programming
* Declarative programming
Note that programming paradigm is not a strict rule.
Rather, they are like a good programming approach, based on theory and practice.
Usually these paradigms are not conflicting, but are independent concepts, so it is possible to have these styles coexist in one program.
For example, object-oriented programming is a style that combines data and processing as "objects", but in Python this can be achieved using Class.
2. 関数によるモジュール化 (Modularity)
lang:ja
これまでの講義のなかで、「関数」を使えば何度も繰り返される操作をくくりだすことができることを学んできました。
例えば次のプログラムを見てみましょう。ここでは、二人の学生の成績を計算しています。
lang:en
So far, we have learn that functions are a way to extract repeated sequences of instructions.
For example, consider the following program, which calculates the final letter grade for two students:
End of explanation
def calculate_grade(student_name, scores):
  weighted_score = 0.2 * scores[0] + 0.2 * scores[1] + 0.6 * scores[2]
  grade = 'PASS' if weighted_score > 60 else 'FAIL'
  return '{}\'s final score: {} => {}'.format(student_name, weighted_score, grade)
print(calculate_grade('Sam', sam_scores))
print(calculate_grade('Yuko', yuko_scores))
devon_scores = [60, 50, 60]
print(calculate_grade('Devon', devon_scores))
Explanation: lang:ja
プログラムのなかで Sam と Yuko の成績は同じ方法で計算をされています。
しかし、このプログラムをすこし見ただけでは、本当に全く同じ方法で行われていることを確認するのはなかなか大変です。
さらに、もし成績評価に関するパラメータを変えたくなったとした場合は、それぞれの学生に対する処理が同じになるよう、注意深くコードを変更する必要があります。
このような問題は、成績評価をするための一連の処理の流れを「関数」としてまとめることで解決できます。
以下のプログラムのように処理を関数にまとめれば、各学生に対し同じ関数を呼ぶだけで、同じ計算をしていることが保証できますし、パラメータを調整する際も変更箇所は関数の内側だけに限定されます。
lang:en
Sam and Yuko's grades are calculated in exactly the same way. However, it is currently very difficult to make sure that these calculations are carried out consistently. If we change how a particular assignment is weighed, or what is the criteria for passing, then we need to carefully make these changes for every single student.
To avoid this problem, we can group the sequence of instructions that calculates a student's grade into a function. We can then simply call this function for each student, and any change that we need to make to our assignment weights can happen inside this function.
End of explanation
print(calculate_grade('Sam', sam_scores))
print(calculate_grade('Sam', sam_scores))
# When we call the function again, the same message will be printed.
print(calculate_grade('Sam', sam_scores))
Explanation: lang:ja
このように関数でまとめると、あとから処理を変更しやすかったり、新たな学生を追加したりといったことが簡単になります。
このように処理を関数によって分割することをモジュール化といいます。プログラムをモジュール化することで、プログラムのデバッグや再利用が簡単になります。
lang:en
As shown above, it's much easier to change the function and add new students after using a function.
It is called modularization that a procedure is splited as functions in this way. By modularizing programs, it is easier to debug and reuse programs.
3. 純粋関数 (Pure Function)
lang:ja
ところで、上で実装した calculate_grade を何度も呼ぶと何が起こるでしょうか？
lang:en
By the way, what will happen if we call calculate_grade multiple times?
End of explanation
# Impure version
def calculate_grade_impure(student_name, scores):
  scores[0] *= 0.2
  scores[1] *= 0.2
  scores[2] *= 0.6
  weighted_score = scores[0] + scores[1] + scores[2]
  grade = 'PASS' if weighted_score > 60 else 'FAIL'
  return '{}\'s final score: {} => {}'.format(student_name, weighted_score, grade)
print(calculate_grade_impure('Sam', sam_scores))
print(calculate_grade_impure('Sam', sam_scores))
# When we call the function again, we get a different result!
print(calculate_grade_impure('Sam', sam_scores))
Explanation: lang:ja
もちろん同じ値が何度も返されます。
同じ値を引数にあたえているのだから当たり前に思えます。
では、次の関数 calculate_grade_impure はどうでしょうか？
lang:en
Of course, the same value is returned for each call.
It is natural because the same value is given to the argument.
So what about the following function calculate_grade_impure?
End of explanation
def square(x):
  return x ** 2
# We can assign a function `square` to a variable `my_square`
my_square = square
# The variable can be called since it contains a function.
print(my_square(3))
Explanation: lang:ja
関数を呼ぶたびにSamのscoreが減少してしまいました！ これは calculate_grade_impure の内部で score の値自体を変更してしまっているためです。
この calculate_grade_impure が行うような、返り値の計算に直接関係ない状態を変える処理などのことを 副作用　とよびます。副作用のない関数を純粋関数といいます。今回の場合、calculate_grade は純粋関数であり、calculate_grade_impure は非純粋関数です。
関数型プログラミングにおいて、非純粋関数よりも純粋関数のほうが推奨されます。
今回の例でみたように、非純粋関数を呼ぶ際にはデータがどのように変わるのかということに注意を払う必要があり、プログラムの複雑性が増すためです。
また、純粋関数のほうが、コードの再利用がしやすいという利点があります。
ただし、Pythonにおいて、非純粋関数を完全になくすことは現実的ではありませんし、純粋関数はパフォーマンス上不利になることもあります。
ただ、関数を定義する際や呼ぶ際にそれがどんな副作用を持つかどうかを意識するのは大切です。
lang:en
Every time you call the function calculate_grade_impure, the score of Sam has decreased! This is because score itself has been changed inside.calculate_grade_impure
Changeing the state not directly related to the main computation is called side effects. Functions with no side effects are called "pure functions". In this case, calculate_grade is a pure function, andcalculate_grade_impure is an impure function.
For functional programming, pure functions are recommended over non-pure functions.
As we saw in this example, it is necessary to pay attention to how data changes when calling an impure function, which increases the complexity of the program.
Also, pure functions have the advantage of being easier to reuse code.
However, in Python, it is not realistic to completely eliminate impure functions, and pure functions may be disadvantageous for performance.
However, when defining or calling a function it is still important to be aware of what side effects it has.
4. 第一級オブジェクトとしての関数 (Function as a first-class object)
lang:ja
Pythonにおいて、関数は変数に格納されたり、他の関数の引数や返り値になることができます。
このことを関数が 第一級オブジェクト (first-class object) として扱われるといいます。第一級オブジェクトとは、変数への代入や関数の引数や返り値になることなどができる値のことです。他には数値型やString型の値、リスト、辞書、Class なども第一級オブジェクトです。
この「関数が第一級オブジェクトである」性質は、我々は「数値」や「文字列」と同様に、それらに対する「操作」をもプログラムの中で持ち回すことを意味します。
この性質をうまく使いこなすことで、より簡潔でわかりやすいプログラムをかけることがあります。
それでは実際の例をみていきましょう。
まず、関数は数値などの値と同様に変数に代入することができ、それをいつも通り呼び出すことができます。
lang:en
A function is simply an object you can call in Python. Otherwise, a function behaves no differently from other objects. This property is incredibly powerful as it allows us to move operations around our code.
Let's take a look at how this works more concretely. First, we can assign functions to variables, and call them as usual.
End of explanation
def square(x):
  return x ** 2
def cube(x):
  return x ** 3
# Creating a list of functions.
power_functions = [ square, cube ]
for power_function in power_functions:
  print(power_function(3))
Explanation: lang:ja
関数をリストに格納することもできます。
これは例えば連続して呼ぶべき関数があったときなどに役立つでしょう。
lang:en
We can also add functions to a list. This can be useful if we have a series of functions that we need to call.
End of explanation
student_ages = [('Sam', 18), ('Yuko', 20), ('Devon', 19)]
# Sort by names in alphabetical order.
def get_name(student):
  return student[0]
sorted_by_name = sorted(student_ages, key=get_name)
print('Sorted by name: {}'.format(sorted_by_name))
# Sort by age. (ascending order)
## You can use lambda to avoid defining a new function
sorted_by_age = sorted(student_ages, key=lambda student:student[1])
print('Sorted by age (smallest to largest): {}'.format(sorted_by_age))
# You can use `reverse` to sort a list by descending order.
sorted_by_age_desc = sorted(student_ages, key=lambda student:student[1], reverse=True)
print('Sorted by age (largest to smallest): {}'.format(sorted_by_age_desc))
Explanation: lang:ja
また、関数を別の関数に引数として渡したり、関数の返り値にすることもできます。
引数や返り値が関数である関数のことを高階関数 (higher-order function) といいます。
高階関数を用いることでより進んだ抽象化を行うことができます。
リストをソートする操作を考えてみましょう。
「リスト内の値を並べ替える」という操作はとても一般的なものです。
しかし、あるリストにおいて「どんな値が先にくるべきか」というのは、用途によります。
そこでPythonは ソートを行う sorted(...) を高階関数として提供しています。
sorted を呼ぶ際に key としてどの値で並べ替えるべきかを指定する関数を与えることができます。
lang:en
We can also pass functions to functions as arguments. This is most helpful when we have a general pattern, and we need specific operations to make these patterns relevant to our programs.
A good example that we mentioned earlier is sorting, where "what should come first" is very dependent on our program. For example, for Python's built in sorted(...) function, we use the key argument to tell the function which of the students' attributes to sort by.
End of explanation
def create_adder(k):
  def adder(x):
    # k is captured from the outer function.
    return x + k
  return adder
adder_5 = create_adder(5)
print(adder_5(3))
Explanation: lang:ja
さらに、関数を関数の中で定義し、それを返すことも可能です。
次の例では関数create_adderの情報をcapture したadderという関数を定義し、それを返しています。
lang:en
Finally, just like objects, functions can be defined and returned in functions. This is an advanced technique that will not be covered in this notebook, but allows information in the outer function to be "captured" by the inner function.
End of explanation
%%solution
def apply_n_times(f, x, n):
   # BEGIN PROMPT
  pass
   # END PROMPT
  # BEGIN SOLUTION
  result = x
  for _ in range(n):
    result = f(result)
  return result
  # END SOLUTION
%%studenttest ApplyNTimesStudentTest
def add2(x):
  return x + 2
assert apply_n_times(add2, 0, 5) == 10
# Note: the "lambda" syntax is a shorthand for creating a function with no name.
# For more information, see:
# https://docs.python.org/3/tutorial/controlflow.html#lambda-expressions
assert apply_n_times(lambda x: x * 2, 1, 10) == 1024
def fibonacci_step(x):
  return (x[1], x[0] + x[1])
assert apply_n_times(fibonacci_step, (1, 1), 10) == (89, 144)
%%inlinetest ApplyNTimesInlineTest
assert apply_n_times(lambda x: True, None, 1) is not None, 'Did you forget to return a value?'
assert apply_n_times(lambda x: x + 1, 1, 2) == 3, 'Are you passing `x` and `y` to the function?'
assert apply_n_times(lambda x: x * x, 0, 100) == 0, '`x` must be returned as is when `n == 0`.'
Explanation: 5. Exercise: 高階関数 (Higher-order functions)
5.1. Calling Functions from Functions
lang:ja
それでは実際に関数を引数に取る関数を実装してみましょう。
1引数関数fと2つの値x, nを受け取り、f をxに対して n回適用する関数 apply_n_times(f, x, n) を実装してください。
lang:en
In this section, let's implement higher-order functions by ourselves.
Define a function named apply_n_times(f, x, n) that takes a function f and two arguments x, n, and returns the value when this function is applied to x n times.
Example
```python
def add2(x):
  return x + 2
Prints 10 (i.e. add2(add2(add2(add2(add2(0))))))
print(apply_n_times(add2, 0, 5)) 
```
```
EXERCISE METADATA
exercise_id: "ex51_ApplyNTimes"
```
End of explanation
%%solution
def find_first_match(predicate, items):
   # BEGIN PROMPT
  pass
   # END PROMPT
  # BEGIN SOLUTION
  for x in items:
    if predicate(x):
      return x
  # END SOLUTION
%%studenttest FindFirstMatchStudentTest
assert find_first_match(lambda x: x > 5, [1, 2, 3, 8, 9]) == 8
assert find_first_match(lambda x: x, [False, False, True]) is True
assert find_first_match(lambda x: x == 10, [11, 12, 8]) is None
%%inlinetest FindFirstMatchInlineTest
assert find_first_match(lambda x: True, []) is None, 'Do you have the correct return value when there are no items?'
assert find_first_match(lambda x: x > 1, [2]) == 2, 'Are you checking if calling the predicate returns True?'
assert find_first_match(lambda x: x > 1, [1, 2]) == 2, 'Are you checking all of the items?'
Explanation: 5.2. Returning the First Item that Matches a Predicate
lang:ja
引数を受け取り、True か False を返す純粋関数をpredicate (述語)と呼ぶことにします。
例えば、次の関数greater_than_5 はpredicateです。
python
def greater_than_5(x):
  return x &gt; 5
predicateとリストを受け取り、リストの要素のうちそのpredicateがTrueを返す最初の要素を返す関数find_first_match を実装してください。
ただし、そのような要素が存在しない場合、None を返してください。
lang:en
We call a function that takes arguments and returns a Boolean value as "predicate".
For example, following greater_than_5 is a predicate.
python
def greater_than_5(x):
  return x &gt; 5
Define a function find_first_match(...) that takes a predicate and a list, and returns the first matching item. If there is no such item, then return None.
Example
```python
Prints 8, which is the first item greater than 5.
print(find_first_match(greater_than_5, [1, 2, 3, 8, 9]))
Prints None
print(find_first_match(greater_than_5, [1, 2, 3, -8, -9]))
```
```
EXERCISE METADATA
exercise_id: "ex52_FindFirstByPredicate"
```
End of explanation
%%solution
def my_filter(predicate, items):
   # BEGIN PROMPT
  pass
   # END PROMPT
  # BEGIN SOLUTION
  filtered_items = []
  for item in items:
    if predicate(item):
      filtered_items.append(item)
  return filtered_items
  # END SOLUTION
%%studenttest MyFilterStudentTest
assert(my_filter(lambda x : x > 3, [4, 2, 8, -3, 10, 3]) == 
       [4, 8, 10])
assert (my_filter(lambda x: len(x) > 3, 
                  ['dog', 'elephant', 'cat', 'hippopotamus']) == 
        ['elephant', 'hippopotamus'])
assert my_filter(lambda x: x > 2, [2, 4, 5]) == [4, 5]
assert my_filter(lambda x: x, [True, True, False]) == [True, True]
assert (my_filter(lambda x: x[0] * x[1] < 1, [(1, 0.5), (0.8, 0.9),
                                                 (2, 1)]) == [(1, 0.5),
                                                              (0.8, 0.9)])
%%inlinetest MyFilterInlineTest
assert len(my_filter(lambda x: True, [1, 2])) == 2, 'Are you returning all matching items?'
assert my_filter(lambda x: x > 1, [1, 2]) == [2], 'Are you calling the predicate on each item?'
assert my_filter(lambda x: True, [1, 2]) != [2, 1], 'Are you following the order of the provided items?'
Explanation: 5.3. Filtering Items in a List
lang:ja
Predicateとリストを受け取り、リストの各要素のうち predicateがTrueを返すもののみからなるリストを返す関数 my_filter を実装してください。
ただし、my_filter が返すリスト内の要素の順序は元のリストの順序を保存するものとします。
lang:en
Define a function filter_items(...) that takes a predicate and a list of items, and returns only the items for which the predicate returns True.
my_filter has to preserve the order of items in the list passed as an argument.
Example
```python
def greater_than_3(x):
  return x > 3
# Prints [4, 8, 10]
print(my_filter(greater_than_3, [4, 2, 8, -3, 10, 3]))
def longer_than_3(x):
  return len(x) > 3
Prints ['elephant', 'hippopotamus'].
print(my_filter(longer_than_3, ['dog', 'elephant', 'cat', 'hippopotamus']))
```
```
EXERCISE METADATA
exercise_id: "ex53_FilterList"
```
End of explanation
%%solution
def my_map(function, items):
   # BEGIN PROMPT
  pass
   # END PROMPT
  # BEGIN SOLUTION
  transformed_items = []
  for item in items:
    transformed_items.append(function(item))
  return transformed_items
  # END SOLUTION
%%studenttest MyMapStudentTest
assert my_map(lambda x: x, [1, 2, 3]) == [1, 2, 3]
assert my_map(lambda x: x[0], [(1, 2), (2, 3), (3, 4)]) == [1, 2, 3]
assert my_map(lambda x: x > 3, [8, 2, 1]) == [True, False, False]
%%inlinetest MyMapStudentTest
assert len(my_map(lambda x: x, [1, 2])) == 2, 'Are you returning all of the mapped items?'
assert my_map(lambda x: x, [1, 2]) != [2, 1], 'Are you following the order of the provided items?'
assert my_map(lambda x: x + 1, [1, 2]) == [2, 3], 'Are you calling the function on each of the items?'
Explanation: 5.4. map: リストの各要素に関数適用をする関数 (map: Appying a Function to Each Item in a List)
lang:ja
関数とリストを受け取り、そのリストの各要素に受け取った関数を適用して得られるリストを返す関数 my_map を実装してください。
lang:en
Define a function my_map(...) that takes a function and a list of items, and returns the list of items after the function has been applied on each of the items.
Example
```python
def square(x):
  return x ** 2
print(my_map(square, [1, 2, 3])) # Prints [1, 4, 9].
def expand3(x):
  return [x] * 3
print(my_map(expand3, [1, 2, 3])) # Prints [[1, 1, 1], [2, 2, 2], [3, 3, 3]].
```
```
EXERCISE METADATA
exercise_id: "ex54_ApplyFuncToList"
```
End of explanation
filtered_list = list(filter(lambda x : x > 3, [4, 2, 8, -3, 10, 3])) 
assert(filtered_list == [4, 8, 10])
mapped_list = list(map(lambda x: x**2, [1, 2, 3]))
assert(mapped_list == [1, 4, 9])
Explanation: Aside: Python's Built-In Functional Primitives
lang:ja
さて、ここまで実装してきた my_filter と my_map はよくつかわれる処理なので、Pythonでbuilt-in関数として用意されています。
それぞれ、filter, map という関数です。
lang:en
As it turns out, the my_filter(...) and my_map(...) that you implemented are such common operations that they have been built into the Python language itself!
End of explanation
# Prints [1, 4, 9].
print([x ** 2 for x in [1, 2, 3]])
Explanation: lang:ja
また、これらの処理は リスト内包表記 (list comprehension) という機能をつかうことでも記述することができます。
例えば、mapに対応する処理はこのように実装できます。
lang:en
Also, you can use list comprehension to implement such list operations.
By default, we can transform items like so:
End of explanation
print([x for x in [4, 2, 8, -3, 10, 3] if x > 3])
Explanation: lang:ja
また、filter に対応する処理は、述語をリスト内包表記の末尾に if とともに書くことで記述できます。
lang:en
Then, to filter the items, we add the predicate at the end of the list comprehension:
End of explanation
# Prints [4, 9] since only x > 1 are transformed.
print([x ** 2 for x in [1, 2, 3] if x > 1])
# Creates a list of squares for each number in [1, 2, 3] that is larger than 1.
print([[x ** 2 for x in range(y)] for y in [1, 2, 3] if y > 1])
# Converts a list of number strings into numbers, then creates 3 x 3 matrices
# containing each number.
print([[[x] * 3] * 3 for x in [int(y) for y in ['1', '2', '3']]])
Explanation: lang:ja
もっと複雑なこともできます。
ただ、リスト内包表記で複雑なことをしすぎるとコードの可読性が落ちるため、このような例では単に for-loopやif文を使ったほうがいいかもしれません。
lang:en
We can write more complex operations in list comprehension!
This syntax can get quite complicated, with list comprehensions inside of list comprehensions! This is a very powerful tool, but we need to be careful that we are writing code that others can understand. For example, in the following case, we might be better off just using our normal for-loops and if-statements.
End of explanation
%%solution
# [(city name, population, area)]
test_data = [('Chiyoda',   64894, 11.66),
             ('Minato',   259042, 20.37),
             ('Shinjuku', 349844, 18.22),
             ('Bunkyo',   233926, 11.29),
             ('Taito',    207838, 10.11)]
    
 # BEGIN PROMPT    
class City:
  # Q 6.1.
  def __init__(self, data):
    pass
  # Q 6.2.
  def population_density(self):
    pass
    
# Q6.3.
def top_k_densest_city_names(city_list, k):
  pass
 # END PROMPT
# BEGIN SOLUTION
class City:
  # Q 6.1.
  def __init__(self, data):
    self.name = data[0]
    self.population = data[1]
    self.area = data[2]
  # Q 6.2.
  def population_density(self):
    return self.population / self.area
# Q6.3.
def top_k_densest_city_names(city_list, k):
  sorted_cities = list(sorted(city_list, key=lambda c: c.population_density(), reverse=True))
  return list(map(lambda c: c.name, sorted_cities[:k]))
# END SOLUTION
%%studenttest FPAndOOPStudentTest1
# Q 6.1.
## Create a `City` instance for ('Chiyoda', 64894, 11.66) 
chiyoda_ku = City(test_data[0])
## Each data must be accessed 
assert(chiyoda_ku.name == 'Chiyoda')
assert(chiyoda_ku.population == 64894)
assert(chiyoda_ku.area == 11.66)
%%studenttest FPAndOOPStudentTest2
# Q 6.2.
## Population density is (population / area)
assert(chiyoda_ku.population_density() == 64894 / 11.66)
%%studenttest FPAndOOPStudentTest3
# Q 6.3.
## Create a list of `City` instances by using `map` function.
city_list = list(map(City, test_data))
## Get Top 5 cities
top5_densest_cities = top_k_densest_city_names(city_list, 5)
# Expected: ['Bunkyo', 'Taito', 'Shinjuku', 'Minato', 'Chiyoda']
print('Top 5 cities: {}'.format(top5_densest_cities))
assert(len(top5_densest_cities) == 5)
expected = ['Bunkyo', 'Taito', 'Shinjuku', 'Minato', 'Chiyoda']
assert top5_densest_cities == expected, 'Expected: {}, Actual: {}'.format(expected, top5_densest_cities)
%%studenttest FPAndOOPStudentTest3_2
# More tests: Change the value of `k`
## Get Top 2 cities
top2_densest_cities = top_k_densest_city_names(city_list, 2)
print('Top 2 cities: {}'.format(top2_densest_cities))
assert len(top2_densest_cities) == 2
assert top2_densest_cities == [ 'Bunkyo', 'Taito' ]
## What if `k` is 0?
top0_densest_cities = top_k_densest_city_names(city_list, 0)
print('Top 0 cities: {}'.format(top0_densest_cities))
assert(top0_densest_cities == [])
%%inlinetest FPAndOOPStudentTest
# Q 6.1.
try:
  City(('A', 1, 1))
except NameError:
  assert False, 'class `City` is not implemented'
except Exception:
  assert False, 'City((\'A\', 1, 1)) raised an exception'
try:
  c = City(('A', 1, 1))
  name = c.__class__.__name__
except Exception:
  assert False, "City(('A', 1, 1)) raised an exception"
if name != 'City':
  assert False, 'The class name is not `City` but {}'.format(name)
test_data = [('Chiyoda',   64894, 11.66),
             ('Minato',   259042, 20.37),
             ('Shinjuku', 349844, 18.22),
             ('Bunkyo',   233926, 11.29),
             ('Taito',    207838, 10.11)]
city_a = City(test_data[0])
try:
  city_a.name
  city_a.population
  city_a.area
except AttributeError:
  assert False, 'The class `City` must have fields `name`, `population` and `area`.'
assert city_a.name == 'Chiyoda', '`name` field is not implemeted properly'
if city_a.population == test_data[1] and city_a.area == test_data[0]:
  assert False, 'You may swap `population` and `area`?'
assert city_a.population == test_data[0][1], '`population` field is not implemeted properly'
assert city_a.area == test_data[0][2], '`area` field is not implemeted properly'
# Q 6.2.
try:
  city_a.population_density()
except AttributeError:
  assert False, 'The class has no method like `city_a.population_density()`.'
assert city_a.population_density() == city_a.population / city_a.area, 'population_density() must return `population` / `area`'
# Q 6.3.
try:
  top_k_densest_city_names
except NameError:
  assert False, 'function \'top_k_densest_city_names\' is not defined'
city_list = list(map(lambda data: City(data), test_data))
try:
  assert top_k_densest_city_names(city_list, 3) is not None, "You have not implemented top_k_densest_city_names"
except Exception as e:
  assert False, 'Error when trying to run top_k_densest_city_names: %s' % e
ans3 = top_k_densest_city_names(city_list, 3)
assert len(ans3) == 3, 'top_k_densest_city_names(..., 3) must return list with 3 elements, but got %d' % len(ans3)
dense_cities = top_k_densest_city_names(city_list, 5)
assert dense_cities.__class__ == list, "top_k_densest_city_names() should return a list, but got %s" % dense_cities.__class__
assert len(dense_cities) == 5, "top_k_densest_city_names(city_list, 5) should return a list with 5 elements, but got %d" % len(dense_cities)
assert dense_cities[0].__class__ == str, "top_k_densest_city_names() should return a list of strings, but got %s" % dense_cities[0].__class__
ans = ['Bunkyo', 'Taito', 'Shinjuku', 'Minato', 'Chiyoda']
assert dense_cities == ans, ('the population density ranking should be '+"['Bunkyo', 'Taito', 'Shinjuku', 'Chuo', 'Minato'], but your code returned %s" % dense_cities)
result, logs = %autotest FPAndOOPStudentTest
assert result.results['passed']
report(FPAndOOPStudentTest, results=result.results)
Explanation: 6. Exercise: オブジェクト指向プログラミングと関数型プログラミング (OOP and FP
<!--
```
# ASSIGNMENT METADATA
assignment_id: "FP_OOP"
```
-->
lang:ja
この節では、ここまでで学んだ関数型プログラミング的考え方と、classを用いるオブジェクト指向的考え方をあわせて、データ処理を行うプログラムを書いてみましょう。
今回は"('市町村名', 人口, 面積)" というタプルのリストに対する処理をするプログラムを考えます。
6.1-6.3が問題の説明、6.4で実装という構成になっています。
lang:en
In this section, let's write a program that performs data processing, combining the functional programming and the object-oriented programming.
Here, let's consider a program that operates on a list of tuples " ('city name', population, area) ".
Problem statements are given in 6-1, 6-2, and 6-3, and you can implement the solution in 6-4.
```python
[(city name, population, area)]
test_data = [('Chiyoda',   64894, 11.66),
             ('Minato',   259042, 20.37),
             ('Shinjuku', 349844, 18.22),
             ('Bunkyo',   233926, 11.29),
             ('Taito',    207838, 10.11)]
```
6.1. Define a class
lang:ja
一つの市町村のデータを表すクラス City を実装してください。
このクラスは
* name
* population
* area
というメンバーをもち、これらの値をタプルとして受け取るコンストラクタを持つようにしてください。
lang:en
Define a class City, which has the following members:
* name
* population
* area
The City has to have a contstructor that work like followings:
Example
```python
name = 'Bunkyo'
population = 233926
area = 11.29
city = City((name, population, area))
assert(city.name == name)
assert(city.area == area)
assert(city.population == population)
You can create a list of City instances from test_data by using map.
city_list = list(map(City, test_data))
```
6.2. Define a method
lang:ja
6.1.で定義した class City に人口密度を計算して返すメソッド population_density() を実装してください。
lang:en
Implement a method population_density() in City
Example
```python
Population density is (population / area)
assert(city.population_density() == city.population / city.area)
```
6.3. Get top k cities
lang:ja
Cityのインスタンスのリスト city_list を受け取り、 人口密度が高い上位k個の都市の名前のリストを返す関数 top_k_densest_city_name(city_list, k) を実装してください。
注意： 返すリストの要素は都市の名前にして下さい。
実装のヒント: リストlに対し、l[n:m]と書くことで n番目からm-1番目の要素までを取り出すことが出来ます。
lang:en
Implement a function top_k_densest_city_name(city_list, k) that takes a list of City instances city_list and returns a list of the topk cities with high population density.
Note: The return value should be a list of names, not city objects.
Hint: You can write l[n:m] to take the range from n-th element to m-1-th element in a list l.
Example
```python
top5_cities = top_k_densest_city_names(city_list, 5)
Prints ['Bunkyo', 'Taito', 'Shinjuku', 'Minato', 'Chiyoda']
'Bunkyo' is the densest city.
print(top5_cities)
If you are only interested in the densest city, pass 1 as k.
Prints ['Bunkyo']
print(top_k_densest_city_names(city_list, 1))
```
6.4. 実装 (Implementation)
```
EXERCISE METADATA
exercise_id: "ex64_FP_OOP"
```
End of explanation
<END_TASK>