Python higher-order functions and comprehensions

It may be better to ask a question, but I would like to add it as needed, and I feel like I will lose something if it is a question, so I will write it as an article (self-centered).

Originally using Scheme, for various reasons Description of higher-order functions often expressed in Scheme because Python is used as an alternative language. I'm looking for a way to replace Anyway, in Scheme, map + lambda etc. are used a lot, and it is possible to write as it is in Python, but there are still subtle differences, and list comprehension etc. is recommended from the viewpoint of readability and processing speed. Since it seems that there is, I would like to do something that can be expressed by comprehension.

In this article, I will expose the description expressed in the (?) Comprehension notation and use it as a memorandum and information exchange material. The Scheme processing system is Gauche, and the Python processing system is Python3. programming-online /) is assumed.

Description example (1) (map → inclusion notation)

Description example in Scheme:

(display (map + '(0 1 2 3 4) '(5 6 7 8 9)))
; => (5 7 9 11 13)

Description example using Python's map and lambda:

from operator import add
print(tuple(map(add, (0,1,2,3,4), (5,6,7,8,9))))
# => (5, 7, 9, 11, 13)

Or

print(tuple(map((lambda x, y: x + y), (0,1,2,3,4), (5,6,7,8,9))))
# => (5, 7, 9, 11, 13)

Description example using Python comprehension:

print(tuple(x + y for x, y in zip((0,1,2,3,4), (5,6,7,8,9))))
# => (5, 7, 9, 11, 13)

The processing speed is ... Oh, is map + ʻadd` the fastest? I wonder if I made a mistake (bearish).

python


from time import time
from operator import add

R1 = range(9999999,-1,-1)
R2 = range(0,10000000)

start = time()
a = tuple(map(add, R1, R2))
print("          map + add: ", time() - start)

start = time()
b = tuple(map((lambda x,y: x + y), R1, R2))
print("       map + lambda: ", time() - start)

start = time()
c = tuple(x + y for x,y in zip(R1, R2))
print("comprehension + zip: ", time() - start)

#           map + add:  2.8753578662872314
#        map + lambda:  4.222743034362793
# comprehension + zip:  3.9112401008605957

Description example (2) (fold / reduce)

Description example in Scheme:

(display (fold * 1 '(1 2 3 4 5 6 7 8 9 10)))
; => 3628800

Description example using Python's reduce and lambda:

from functools import reduce
from operator import mul
print(reduce(mul, (1,2,3,4,5,6,7,8,9,10)))
# => 3628800

Or

print(reduce(lambda x, y: x * y, (1,2,3,4,5,6,7,8,9,10)))
# => 3628800

Is there a description example using Python's comprehension? In the first place, the value to be sought is not a sequence type, so there is no set inclusion (it immediately deviates from the purpose of the article). It seems that sum is prepared as standard for addition. Is this something that you should create your own function if necessary (rather, a LISP-like idea)?

def product(l):
    r = 1
    for i in l: r *= i
    return r

print(product((1,2,3,4,5,6,7,8,9,10)))
# => 3628800

And time measurement. It doesn't change much, but it seems that ʻoperator.mul` is about to be a child who doesn't need it.

from functools import reduce
from time import time
from operator import mul

def product(l):
    r = 1
    for i in l: r *= i
    return r

R1 = range(1,100000)

start = time()
a = reduce(mul, R1)
print("   reduce + mul: ", time() - start)

start = time()
a = reduce(lambda x, y: x * y, R1)
print("reduce + lambda: ", time() - start)

start = time()
a = product(R1)
print("        product: ", time() - start)

#    reduce + mul:  23.096322059631348
# reduce + lambda:  18.508586406707764
#         product:  19.82227087020874

Description example (3) (Inclusive notation → Higher-order function)

Here, conversely, consider expressing the following description expressed in Python list comprehension with a higher-order function.

python


tuple((x, y) for x in (1,2,3) for y in (7,8,9) if x + y < 11)
# => ((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))

Regarding Scheme, there is a list comprehension notation list-ce in the extended proposal specification SRFI 42, and it can be written as follows.

(use srfi-42)
(display (list-ec (: x '(1 2 3)) (: y '(7 8 9)) (if (< (+ x y) 11)) (list x y)))
; => ((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))

If you try to do this with just a lambda expression or map, it will be rather complicated.

(display
  (filter (lambda (p) (< (+ (car p) (cadr p)) 11))
          (fold append '()
                (reverse
                  (map (lambda (x)
                         (map (lambda (y) (list x y))
                              '(7 8 9)))
                       '(1 2 3))))))
; => ((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))

The main reason is that the selection by the conditional expression is performed by filter separately after generating the unconditional list once. In addition, nesting map also nests the returning list, so ʻappend needs to be flattened by fold ( reduce) (and ʻappend is added to the top of the list in sequence. Therefore, it is necessary to reverse the list elements with reverse before ʻappend). The latter is a little easier if you can use SRFI 1's ʻappend-map.

(display
  (filter (lambda (p) (< (+ (car p) (cadr p)) 11))
          (append-map (lambda (x)
                        (map (lambda (y) (list x y))
                             '(7 8 9)))
                      '(1 2 3))))
; => ((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))

In that sense, if list comprehension notation cannot be used, map fold ( reduce) + filter will be required as a set (ʻappendandreverse` are both list operations. When functional programming was introduced in languages where procedural programming was the main language, these may have been regarded as typical higher-order functions. And, in such a description, the set inclusion is easier to understand and is omitted below.

In Python3, reduce is one of the external libraries functools, but since the basic function sum also supports lists, you can write as follows even without reduce. Possible.

print(
  tuple(filter(lambda p: p[0] + p[1] < 11,
               sum(tuple(map(lambda x:
                             tuple(map(lambda y: (x, y),
                                       (7,8,9))),
                             (1,2,3))),
                   ()))))
# => ((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))

When using reduce of functools, it is as follows.

from functools import reduce
print(
  tuple(filter(lambda p: p[0] + p[1] < 11,
               reduce(lambda x, y: x + y,
                      tuple(map(lambda x:
                                tuple(map(lambda y: (x, y),
                                          (7,8,9))),
                                (1,2,3))),
                      ()))))
# => ((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))

Needless to compare the processing speed. The map is generating tuple many times on the way.

from time import time
from functools import reduce

N = 2000
R1 = range(1,N)

start = time()
a = tuple((x, y) for x in R1 for y in R1 if x + y < N)
print("        comprehension: ", time() - start)

start = time()
a = tuple(filter(lambda p: p[0] + p[1] < N,
               sum(tuple(map(lambda x:
                             tuple(map(lambda y: (x, y),
                                       R1)),
                             R1)),
                   ())))
print("   map + sum + filter: ", time() - start)

start = time()
a = tuple(filter(lambda p: p[0] + p[1] < N,
                 reduce(lambda x, y: x + y,
                        tuple(map(lambda x:
                                  tuple(map(lambda y: (x, y),
                                            R1)),
                                  R1)),
                        ())))
print("map + reduce + filter: ", time() - start)

#         comprehension:  0.5814449787139893
#    map + sum + filter:  27.217236757278442
# map + reduce + filter:  28.032208919525146

Description example (4) (quick sort)

From the conclusion, it seems that there is not much difference between list comprehension notation and filter + lambda descriptively. List comprehension is much better in the sense that it is faster because it is built-in and implemented.

from time import time

D = range(996, -1, -1)

start = time()
def qsort1(L):
    if not L: return []
    else:
        LL = qsort1([x for x in L[1:] if x <  L[0]])
        LR = qsort1([x for x in L[1:] if x >= L[0]])
        return LL + [L[0]] + LR
a = list(qsort1(D))
print("  comprehension: ", time() - start)

start = time()
def qsort2(L):
    if not L: return []
    else:
        LL = qsort2(list(filter(lambda x: x <  L[0], L[1:])))
        LR = qsort2(list(filter(lambda x: x >= L[0], L[1:])))
        return LL + [L[0]] + LR
a = list(qsort2(D))
print("filter + lambda: ", time() - start)

#   comprehension:  0.1841585636138916
# filter + lambda:  0.3261446952819824

Remarks

Change log

Recommended Posts

Python higher-order functions and comprehensions
Higher-order functions and decorators
Python list comprehensions and generators
Python 3 sorted and comparison functions
Python functions
Python tuple comprehensions and generator expressions
About python dict and sorted functions
Comparison of how to use higher-order functions in Python 2 and 3
#Python basics (functions)
Python Easy-to-use functions
Python basics: functions
Use Python and MeCab with Azure Functions
Correspondence between Python built-in functions and Rust
Julia Quick Note [22] Calling Python functions and Python modules
Practice applying functions and global variables in Python
[python] Compress and decompress
Python Beginner's Guide (Functions)
Python basic course (12 functions)
Python and numpy tips
[Python] pip and wheel
Batch design and python
Python iterators and generators
Python packages and modules
Vue-Cli and Python integration
[Python] Memo about functions
Ruby, Python and map
python input and output
Python and Ruby split
Indent comprehensions in Python
# 4 [python] Basics of functions
Python built-in functions ~ Zip ~
Wrap Python built-in functions
Python3, venv and Ansible
Python asyncio and ContextVar
Anonymous and map functions
[Python for Hikari-] Chapter 06-04 Functions (arguments and return value 3)
Writing using lambda expressions and filter functions and writing using list comprehensions
[Python for Hikari-] Chapter 06-01 Functions (Intrinsic Functions and Function Definitions)
[Python for Hikari-] Chapter 06-03 Functions (arguments and return value 2)
Curry arbitrary functions with Python ....
Programming with Python and Tkinter
Python> lambda> tiny functions / callback functions
Encryption and decryption with Python
Getting Started with Python Functions
Python: Class and instance variables
Python3 programming functions personal summary
3-3, Python strings and character codes
Python 2 series and 3 series (Anaconda edition)
Python and hardware-Using RS232C with Python-
Python on Ruby and angry Ruby on Python
Python indentation and string format
Python real division (/) and integer division (//)
Install Python and Flask (Windows 10)
About python objects and classes
About Python variables and objects
Apache mod_auth_tkt and Python AuthTkt
Understand Python packages and modules
# 2 [python3] Separation and comment out
Python shallow copy and deep copy
Python and ruby slice memo
Python installation and basic grammar