[Feature-length poem] I don't understand functional languages You can understand it with Python: Part 1 Functions that receive functions are convenient.

This is a ** feature-length poem ** that describes the features of functional programming in Python. IQ145 beautiful girls will not appear, so don't expect too much.

[Target readers]

[Series article]

Introduction

There is a sentence "Why functional programming is important". As the title suggests, it is a sentence that introduces how functional languages are useful. It's long, but it looks like this in 3 lines:

However, although this sentence and content are highly evaluated, ** the goodness of functional languages is explained by the code of functional languages, so it is not transmitted to users who do not know functional languages at all **. I have a problem.

When explaining to someone who doesn't know functional languages, why would you try to explain using only functional languages (I wish I had written the code for other popular languages as well)? It's exactly like "** If you don't understand the jargon and ask the programmer, it's explained in a more difficult jargon **". Even if you read that sentence because you want to know about functional languages, you will only get the impression that functional languages are difficult.

Therefore, in this poem, "higher-order functions" and "lazy evaluation", which are considered to be particularly important in "Why functional programming is important", are explained in Python. I will explain it without using the code of the functional language, so it will be easy for people who are not functional language users to understand.

(Hey, there! Don't say, "Isn't there fewer Python users in Japan than functional language users?")

Preparation to explain higher-order functions

It is a high hurdle to explain higher-order functions suddenly, so let's prepare before that.

Function object

In Python, ** functions are objects **.

For example, the actual state of ** function definition as follows is the operation ** of "creating a function object and assigning it to a variable".

##A function object is created and assigned to the variable hello
def hello(name):
  print("Hello %s!" % name)

##If you look at the contents of the variable hello, you can see that it is a function object.
print(hello)    #Execution result:<function hello at 0x1007a3ed8>

Therefore, you can call the function by assigning the contents of the variable hello to another variable.

##You can assign the contents of the variable hello to another variable and call it.
say = hello     #Assign a function object to another variable
say("world")    #Call it(The result is hello("world")Same as)

In addition to def, you can also create function objects with lambda. The difference between the two is like this:

##The function defined by def is
def add(x, y):
  return x + y
print(add(3, 5))      #=> 8

##You can also write with lambda(However, only in the case of a single formula)
add = lambda x, y: x + y    #You don't have to write return
print(add(3, 5))      #=> 8

##def contains multiple statements, but must be independent and single statements
def sum(numbers):
  t = 0                 #This function contains multiple statements, so
  for n in numbers:     #I can't write with lambda
    t += n
  return t

##lambda can only be a single expression, but it can be embedded in other statements and expressions
sorted(strings, lambda s: len(s))  #Example of embedding lambda in function argument

The important thing is that in Python, functions are objects, so you can treat them as data ** just like integers and strings. Since you can treat the function as data, you can do something like this:

##Functions can be treated as data (as if they were integers or strings)
n = 123       #Assign an integer to a variable
s = "ABC"     #Assign a string to a variable
f = hello     #Assign a function to a variable

##Pass a function as an argument to another function
otherfunc(hello)

##Create and return a new function within a function
def create_func():
  def add(x, y):
    return x + y
  return add
  ##Or this is fine
  #return lambda x, y: x + y

Summary here:

What the function represents

Even if you say "function" in a nutshell, there are various contents that it represents. Here, I tried to classify them into the following three categories.

** (A) Calculation formula / conversion formula **… Calculates one value to another. Or convert one value to another.

##Calculate double value(Convert to double value)
def double(x):
  return x * 2

##Calculate the sum of the arguments(Convert to sum of arguments)
def add(x, y):
  return x + y

##Calculate HTML class name based on line number(Convert line numbers to HTML class names)
def classname(index):
  if index % 2 == 0:
    return "row-even"
  else:
    return "row-odd"

** (B) Conditional expression / Judgment expression **… Judges whether the value satisfies the condition. Returns true if satisfied, false if not satisfied. (Note: Python uses True / False instead of true / false.)

##Determine if it is even
def is_even(n):
  return n % 2 == 0    #True for even numbers, False for odd numbers

##Determine if it is blank
def is_blank(line):
  if not line:         #Returns True if None or an empty string
    return True
  if not line.strip(): #Returns True if only whitespace or newline characters
    return True
  return False         #Otherwise returns False

##Whether or not they are lovers(To Teketou)judge
couples = [
  ("Kirito", "Asuna"),
  ("Brave",   "Devil"),
  ("Naruto", "Hinata"),
  ("Ellen", "Mikasa"),   #Objection is not recognized
  ("Brother", "Deep snow"),
  ("Kyon", "Sasaki"),   #I admit the objection
]
def is_couple(boy, girl):
  return (boy, girl) in couples

** (C) Processing / Procedure **… Output a character string, read a file, etc.

##Process to display the name
def hello(name):
  print("Hello %s!" % name)

##The process of reading a file and counting the number of lines
## (Note: The with statement closes open files automatically.)
def count_lines(filename):
  n = 0
  with open(filename) as f:
    for line in f:
      n += 1
  print("%s lines" % n)

However, this classification is not strict. Please note that this is just a rough classification for use in the explanations that follow.

Also, I really want to explain the side effects here, but if I say "what are the side effects?", It is beyond the scope of this poem and the ability of the author, so I will omit the explanation here (I love technical terms like that). Smart people will do it).

Summary here:

The role of arguments in functions / procedures / subroutines

For example, let's create a "function that sums 1 to 10". (Note: range (1, 11) produces an integer from 1 to 10, not 11)

def total():
  t = 0
  for i in range(1, 10+1):
    t += i
  return t

It's too easy.

That said, you wouldn't normally write this, but instead use an argument to make it a "function that sums 1 through n".

def total(n):
  t = 0
  for i in range(1, n+1):
    t += i
  return t

It could also be a "function that sums m through n".

def total(m, n):    #Argument check omitted
  t = 0
  for i in range(m, n+1):
    t += i
  return t

Looking at this:

In this way, in functions / procedures / subroutines, you can make a variable part ** (or increase) by using ** arguments (roughly, but if you know the template engine, I think it's similar to that. Isn't it?). Also, the more variable parts there are, the wider the range of applications.

And if you pass not only data such as numerical values, character strings, boolean values and arrays, but also ** calculation formulas / conversion formulas, conditional formulas / judgment formulas, and processing / procedures to the variable part of the function, the range of application will be further expanded. Spread **. You can do that with function objects.

About functions that receive functions (higher-order functions)

Higher-order functions are functions that treat the function as data. Specifically, it looks like this:

(Of course, "a function that receives a function and returns a function" is also a higher-order function.)

Of these, this poem describes the first "function that receives a function".

Higher-order functions that receive functions can be roughly classified as follows.

Let's look at these with concrete examples.

Higher-order function that receives a calculation / conversion formula

Take a look at the following code. The two functions are doing different things.

##A function that takes an array of integers and doubles each element
def doubles(arr):
  newarr = []
  for x in arr:
    newarr.append(x * 2)      #Double each element
  return newarr

##A function that takes an array of strings, converts each element to uppercase and returns it
def uppers(arr):
  newarr = []
  for x in arr:
    newarr.append(x.upper())  #Capitalize each element
  return newarr

(Note: In Python, it's called a "list" instead of an "array". It's called a "list", but it's not a linked list, but a variable-length array in other languages (Java's java.util.ArrayList and Ruby's). Array). Please note that this poem is not intended to explain Python, so we dare to call it "array" in consideration of other language users.)

Now, the two functions do different things, but they do very similar things. ** The only difference is the formula / conversion formula passed to newarr.append () **.

Therefore, we will make the common part into a function called map () and pass the different part as a function:

##Calculation formula for each element of the array/Function to apply the conversion formula
def map(func, arr):
  newarr = []
  for x in arr:
    newarr.append(func(x))      #Calculation formula for each element/Apply the conversion formula
  return newarr

##A function that takes an array of integers and doubles each element
def doubles(arr):
  def func(x): return x * 2     #a formula/Using the conversion formula,
  return map(func, arr)         #Call a common function
  ##Or
  #return map(lambda x: x * 2, arr)

##A function that takes an array of strings, converts each element to uppercase and returns it
def uppers(arr):
  def func(x): return x.upper() #a formula/Using the conversion formula,
  return map(func, arr)         #Call a common function
  ##Or
  #return map(lambda x: x.upper(), arr)

Thus, map () is a "higher-order function that receives a calculation / conversion formula as a function". Also, by using higher-order functions such as map (), common processing can be created and the code is simplified.

Summary here:

Note that in Python, map () is built in by default, so you don't have to define it yourself. Also, Python's map () can be used not only for arrays but also for strings and files, but that is not the purpose of this poem, so I will omit it.

Higher-order function that receives conditional / judgment expressions

Take a look at the following code. The two functions are doing different things.

##A function that takes an array of integers and selects and returns only even numbers
def evens(arr):
  newarr = []
  for x in arr:
    if x % 2 == 0:           #Choose only even numbers
      newarr.append(x)
  return newarr

##Receives an array of strings and ends".html"A function that selects only those that are
def shorts(arr):
  newarr = []
  for x in arr:
    if x.endswith(".html"):  #The end is".html"Choose what is
      newarr.append(x)
  return newarr

(Note: In Python, it is called "list" instead of "array", but please note that this poem is called "array" in consideration of other language users.)

These two functions also do different things, but they do very similar things. ** The only difference is the conditional expression / judgment expression specified in the if statement **.

Therefore, the common part is a function called filter (), and the different part is passed as a function:

##Conditional expression from each element of the array/A function that selects and returns only those that satisfy the judgment formula
def filter(func, arr):
  newarr = []
  for x in arr:
    if func(x):             #Conditional expression/Select only the elements that satisfy the judgment formula
      newarr.append(x)
  return newarr

##A function that takes an array of integers and selects and returns only even numbers
def evens(arr):
  def func(x): return x % 2 == 0    #Conditional expression/Make the judgment formula a function
  return filter(func, arr)          #Call a common function
  ##Or
  #return filter(lambda x: x % 2 == 0, arr)

##Receives an array of strings and ends".html"A function that selects only those that are
def htmls(arr):
  def func(x): return x.endswith(".html")  #Conditional expression/Make the judgment formula a function
  return filter(func, arr)                 #Call a common function
  ##Or
  #return filter(lambda x: x.endswith(".html"), arr)

Thus, filter () is a "higher-order function that receives a conditional / judgment expression as a function". And I was able to simplify the code by using higher-order functions like filter ().

Summary here:

Note that Python also provides filter () as standard, so you don't have to define it yourself. Also, the Python standard filter () can be used not only for arrays but also for strings and files, but it is out of the scope of this poem, so explanations are omitted.

Higher-order function that receives processing / procedures

Take a look at the following code. We are doing separate benchmarks with the two functions.

## (For python 3)
try:
  xrange
except NameError:
  xrange = range

N = 1000000

import time

## str.join()Benchmark of string concatenation using
def bench_strjoin():
  start = time.time()
  for _ in xrange(N):
    s = str.join("", ("Haruhi", "Kyon", "Mikuru", "Itsuki", "Yuki"))
  end = time.time()
  print("%.3f sec" % (end - start))

## '%'Benchmark of string concatenation using operators
def bench_percentop():
  start = time.time()
  for _ in xrange(N):
    s = "%s%s%s%s%s" % ("Haruhi", "Kyon", "Mikuru", "Itsuki", "Yuki")
  end = time.time()
  print("%.3f sec" % (end - start))

(Note: In Python, when using str.join (), it is common to write " ". Join ((...)). But this looks so strange to non-Python users, so I'm using str.join ("", (...)) , which is easy for non-Python users to understand. )

Looking at these two functions, we can see that:

Therefore, define a function called benchmark () that measures the benchmark, and pass the content (processing) of the benchmark as a function. Then the code looks like this:

## (For python 3)
try:
  xrange
except NameError:
  xrange = range

N = 1000000

import time

##A function that measures and displays the execution time
def benchmark(func):
  start = time.time()
  func()               #Call benchmark processing
  end = time.time()
  print("%.3f sec" % (end - start))

## str.join()Benchmark of string concatenation using
def bench_strjoin():
  def func():
    for _ in xrange(N):
      s = str.join("", ("Haruhi", "Kyon", "Mikuru", "Itsuki", "Yuki"))
  benchmark(func)

## '%'Benchmark of string concatenation using operators
def bench_percentop():
  def func():
    for _ in xrange(N):
      s = "%s%s%s%s%s" % ("Haruhi", "Kyon", "Mikuru", "Itsuki", "Yuki")
  benchmark(func)

##Note: For statement benchmark()Including in func()Call cost
##I don't do that here because it can't be ignored.

Thus, benchmark () is a "higher-order function that receives a process / procedure as a function". Thanks to higher-order functions, we've been able to pull out common processes and simplify the code.

To generalize this a bit more, we can say "** You can add pre-processing and post-processing by using higher-order functions **". For example:

Such will be considered.

Summary here:

If you want to add pre-processing and post-processing, it is common to use the with statement instead of higher-order functions in Python (see below).

Higher-order functions received in both formulas and processes

Take a look at the following code. The two functions are doing different things.

##A function that takes an array of integers and returns a sum
def sum(arr):
  t = 0            #Initial value: 0
  for x in arr:
    t = t + x      #Calculate the total(For later explanation, t+=Not x)
  return t

##A function that takes an array of strings, converts it to a dictionary and returns it
def to_dict(arr):
  t = {}           #Initial value: Empty dictionary
  for x in arr:
    t[x] = x       #Convert to dictionary
    t = t          #This is essentially unnecessary, but added for explanation
  return t

(Note: A "dictionary" in Python is equivalent to Hash in Ruby or java.util.HashMap in Java.)

These two functions also do different things, but they do very similar things. ** The only difference is the initial value and the formulas and processes in the loop **.

Therefore, the calculation formulas and processes in the loop are made into functions. Then you can get the intersection out of the function reduce () as follows:

##Perform some calculation or processing on each element of the array and return the stacked result
def reduce(func, arr, initial):
  t = initial         #initial value
  for x in arr:
    t = func(t, x)    #Perform calculations and processing
  return t

##A function that takes an array of integers and returns a sum
def sum(arr):
  def func(t, x): return t + x      #Make the calculation formula a function
  return reduce(func, arr, 0)       #Call a common function
  ##Or
  #return reduce(lambda t, x: t + x, arr, 0)

##A function that takes an array of strings, converts it to a dictionary and returns it
def to_dict(arr):
  def func(t, x):                   #Make processing a function
    t[x] = x
    return t
  return reduce(func, arr, {})      #Call a common function

As you can see, reduce () is a "higher-order function that receives formulas and processes as functions". At first glance, "calculating the sum" and "converting to a dictionary" should be completely different processes, but in fact, I don't think it's very interesting that you can use reduce () to create common parts. Is it?

By the way, the initial value was required for reduce () in the above definition. However, in general, reduce () can omit the initial value, in which case the first element is used as the initial value. The code looks like this:

class Undefined(object):
  pass           #Python pass means "do nothing"
undefined = Undefined()

def reduce(func, arr, initial=undefined):
  ##If no initial value is specified, use the first element instead
  if initial is undefined:   # 'is'Is'=='I think it's a more rigorous version of!
    t = undefined
    for x in arr:
      if t is undefined:
        t = x
      else:
        t = func(t, x)
    ##However, if the array is empty, an error will occur.(Because the return value will be undefined)
    if t is undefined:
      raise TypeError("reduce() of empty sequence with no initial value")
    return t
  ##If the initial value is specified, it will continue as before
  else:
    t = initial
    for x in arr:
      t = func(t, x)
    return t

##note:`t = initial`When`return t`Can be easily removed from the if statement,
##I want to give priority to ease of understanding for beginners, so leave it as it is.

In this case, sum () can be written as follows (with different argument names), omitting the initial value.

def sum(arr):
  return reduce(lambda a, b: a + b, arr)

By writing this, ** the "+" operator that takes two arguments can be regarded as if it takes n arguments **.

reduce()を使うと二項演算子があたかもn項演算子のように見える

Of course, the content of reduce () is just repeating the "+" operator that takes two arguments many times, but depending on the point of view, it uses the operator that takes n arguments only once. It's interesting that it looks like this.

Summary here:

Note that Python also provides reduce () as standard, so you don't have to define it yourself (although Python 3 requires from functools import reduce).

Combine higher-order functions

Higher-order functions are convenient enough on their own, but they are even more convenient when combined.

##Output from 1 to 10(1 <= x < 10+1)
nums = range(1, 10+1)
for x in nums:
  print(x)

##Select and output only odd numbers from 1 to 10
nums = range(1, 10+1)
for x in filter(lambda x: x%2 == 1, nums):
  print(x)

##Select only odd numbers from 1 to 10 and square to output
nums = range(1, 10+1)
for x in map(lambda x: x*x, filter(lambda x: x%2 == 1, nums)):
  print(x)

##Select only odd numbers from 1 to 10, square and sum
from functools import reduce    # python3
nums = range(1, 10+1)
total = reduce(lambda t, x: t+x,
               map(lambda x: x*x, filter(lambda x: x%2 == 1, nums)))
print(total)

##Or
from functools import reduce    # python3
nums = range(1, 10+1)                      #Of 1 to 10
nums = filter(lambda x: x%2 == 1, nums)    #Select only odd numbers,
nums = map(lambda x: x*x, nums)            #Square
total = reduce(lambda t, x: t+x, nums)     #Sum
print(total)

But to be honest, Python's lambda isn't very easy to write. This is much more natural to write in Ruby, Groovy or Scala.

##Ruby can write so naturally
print (1..10).select {|x| x%2 == 1 }.map {|x| x*x }.reduce {|t,x| t+x }

If you look at this Ruby code, you can visually see the process going through in sequence.

If you're using UNIX, you'll notice that this is a lot like pipe processing. Actually, if you want to compare with pipe processing, you should explain lazy evaluation, but let me do that at a later date.

Loop vs higher order function

I will repost the code that combines the higher-order functions.

##Code that combines higher-order functions
from functools import reduce    # python3
total = reduce(lambda t, x: t+x,
               map(lambda x: x*x, filter(lambda x: x%2 == 1, nums, 0)))
##Or
nums = filter(lambda x: x%2 == 1, nums)    #Select only odd numbers,
nums = map(lambda x: x*x, nums)            #Square
total = reduce(lambda t, x: t+x, nums, 0)  #Sum

I wrote the same thing procedurally using a for statement.

##Code written procedurally using a for statement
total = 0
for x in nums:
  if x%2 == 1:
    total += x*x

Well, no matter how you look at it, the for statement is simpler and easier to understand ...

Comparing both of these codes, we can see that:

Procedurally written code Code using higher-order functions
Loops, conditional branches, and formulas are in one block The processing is subdivided into functions and they are combined.
Handle the elements of the array one by one Handle the entire array together("Select from the entire array" "Square the entire array" "Sumulate the entire array" etc.)
Fast (because it only loops once and doesn't use function calls) Operation is slow(Because loops are needed effectively three times for flter, map and reduce, and there are many function calls)

Of particular importance are the first and second. Functional programming takes this perspective and perspective.

To supplement the third point, the combination of functions is certainly slower than I wrote in a loop, but whether that slowness matters is another matter. It's much more likely that the benchmark will be slower but the experience will not change, or that the speed bottleneck is in another part, such as I / O.

Bad news

Unfortunately, higher-order functions that receive functions are not used very often in Python. This is because what you can write with higher-order functions can often be written more naturally in other ways.

For example, it is more natural to write map () and filter () in comprehension.

## map()Is
newarr = map(lambda x: x * x, arr)

##You can write this in list comprehension
newarr = [ x * x for x in arr ]

## filter()Is
newarr = filter(lambda x: x % 2 == 0, arr)

##You can write this in list comprehension
newarr = [ x for x in arr if x % 2 == 0 ]

The readability of comprehensions stands out, especially when combining map () and filter ().

## map()And filter()The combination of
newarr = map(lambda x: x * x, filter(lambda x: x % 2 == 0, arr))

##You can write this in list comprehension
newarr = [ x * x for x in arr if x % 2 == 0 ]

For reduce (), you can use the function sum () to calculate the sum value, and you can use the dictionary comprehension to convert an array of strings to a dictionary.

##For example this is
total = reduce(lambda t, x: t + x, arr, 0)

##This is better no matter what you think
total = sum(arr)


##For example this is
def func(t, x):
  t[x] = x
  return t
dictionary = reduce(func, strings)

##Better to use dictionary comprehension
dictionary = { x:x for x in strings }

If you want to add pre-processing and post-processing, you should use the with statement.

try:
  xrange                #For Python2
except NameError:
  xrange = range        #For Python3

N = 1000000

import time
from contextlib import contextmanager

@contextmanager         # '@'Is a function decorator(Commentary at a later date)
def benchmark():
  start = time.time()
  yield                 # 'yield'Is for generators(Commentary at a later date)
  end = time.time()
  print("%.3f sec" % (end - start))

with benchmark():
  for _ in xrange(N):
    s = str.join("", ("Haruhi", "Kyon", "Mikuru", "Itsuki", "Yuki"))

with benchmark():
  for _ in xrange(N):
    s = "%s%s%s%s%s" % ("Haruhi", "Kyon", "Mikuru", "Itsuki", "Yuki")

As you can see, Python provides a lot of useful features, so the higher-order functions that receive the functions are less used (not at all, sorted (arr, key = fn). ) Andre.sub (pattern, fn, string), etc.).

In particular, reduce () was a built-in function in Python2, but in Python3 it can only be used by importing from the library. This is a de facto downgrade, and we can see the intent that "in Python you can use other means thanreduce ()".

However, the higher-order functions that generate the function are still commonly used. This will be explained in the next Poem.

Python-specific story

import operator

## '=='Equivalent to an operator
operator.eq(1+1, 2)   #=> True

## '+'Equivalent to an operator
operator.add(1, 2)    #=> 3

Exercises

Write an example answer in the comment section.

** [Problem 1] ** Let's define map (), filter () and reduce () by ourselves.

** [Problem 2] ** The function parse_version (), which converts a version number such as "3.4.10 " to an array of integers such as[3, 4, 10], ismap. Let's define it using (). How to use:

print(parse_version("3.4.10"))   #=> [3, 4, 10]

(Hint: use " 3.4.2 ".split (". ") To split a string, and ʻint ("123") `to convert a string to an integer.)

** [Problem 3] ** Let's define a function grep () that selects only those that match the regular expression from the array of character strings using filter (). How to use:

arr = grep(r'\d+', ["ABC", "F102", "X10Y", "ZZZ"])
print(arr)   #=> ["F102", "X10Y"]

(Hint: Use ʻimport re; m = re.search (r'.. pattern ..', string) `for regular expressions.)

** [Problem 4] ** Let's define a function max_by () that returns the maximum value by the specified comparison method from the elements of the array using reduce (). How to use:

members = [
  ("Haruhi", "C"),   #Haruhi is C
  ("Mikuru", "E"),   #Mikuru is E
  ("Yuki",   "A"),   #Yuki is A
]

def getvalue(x):     #Return boobs
  return x[1]

##Who has the biggest boobs?
ret = max_by(getvalue, members)
print(ret)   #=> ("Mikuru", "E")

(Addition 2015-02-08: The problem was wrong! I'm sorry!)

Summary

I explained using Python the higher-order function that receives the function.

in conclusion

Functional languages The popularity of poems has led to more attention than ever to functional languages. This is a unique opportunity, so I would like to take this opportunity to promote the functional language features of Python and Ruby and aim for ** fishermen's interests **.

Recommended Posts

[Feature-length poem] I don't understand functional languages You can understand it with Python: Part 1 Functions that receive functions are convenient.
[Feature-length poem] I don't understand functional languages Even if you understand Python: Part 2 The functions that generate functions are amazing.
python Creating functions that you can remember later
[Python] I don't understand what I'm doing with table [key] [0] + = 1
An introduction to Python that even monkeys can understand (Part 3)
An introduction to Python that even monkeys can understand (Part 1)
An introduction to Python that even monkeys can understand (Part 2)
It seems that you can now write gate books with blueqat
Don't write Python if you want to speed it up with Python
I made a package that can compare morphological analyzers with Python
I made a shuffle that can be reset (reverted) with Python