scrapbook
  • "Unorganized" Notes
  • The Best Public Datasets for Machine Learning and Data Science
  • Practice Coding
  • plaid-API project
  • Biotech
    • Machine Learning vs. Deep Learning
  • Machine Learning for Computer Graphics
  • Books (on GitHub)
  • Ideas/Thoughts
  • Ziva for feature animation: Stylized simulation and machine learning-ready workflows
  • Tools
  • 🪶math
    • Papers
    • Math for ML (coursera)
      • Linear Algebra
        • Wk1
        • Wk2
        • Wk3
        • Wk4
        • Wk5
      • Multivariate Calculus
    • Improving your Algorithms & Data Structure Skills
    • Algorithms
    • Algorithms (MIT)
      • Lecture 1: Algorithmic Thinking, Peak Finding
    • Algorithms (khan academy)
      • Binary Search
      • Asymptotic notation
      • Sorting
      • Insertion sort
      • Recursion
      • Solve Hanoi recursively
      • Merge Sort
      • Representing graphs
      • The breadth-first search algorithm
      • Breadth First Search in JavaScript
      • Breadth-first vs Depth-first Tree Traversal in Javascript
    • Algorithms (udacity)
      • Social Network
    • Udacity
      • Linear Algebra Refresher /w Python
    • math-notes
      • functions
      • differential calculus
      • derivative
      • extras
      • Exponentials & logarithms
      • Trigonometry
    • Probability (MIT)
      • Unit 1
        • Probability Models and Axioms
        • Mathematical background: Sets; sequences, limits, and series; (un)countable sets.
    • Statistics and probability (khan academy)
      • Analyzing categorical data
      • Describing and comparing distributions
      • Outliers Definition
      • Mean Absolute Deviation (MAD)
      • Modeling data distribution
      • Exploring bivariate numerical data
      • Study Design
      • Probability
      • Counting, permutations, and combinations
      • Binomial variables
        • Binomial Distribution
        • Binomial mean and standard deviation formulas
        • Geometric random variable
      • Central Limit Theorem
      • Significance Tests (hypothesis testing)
    • Statistics (hackerrank)
      • Mean, Medium, Mode
      • Weighted Mean
      • Quartiles
      • Standard Deviation
      • Basic Probability
      • Conditional Probability
      • Permutations & Combinations
      • Binomial Distribution
      • Negative Binomial
      • Poisson Distribution
      • Normal Distribution
      • Central Limit Theorem
      • Important Concepts in Bayesian Statistics
  • 📽️PRODUCT
    • Product Strategy
    • Product Design
    • Product Development
    • Product Launch
  • 👨‍💻coding
    • of any interest
    • Maya API
      • Python API
    • Python
      • Understanding Class Inheritance in Python 3
      • 100+ Python challenging programming exercises
      • coding
      • Iterables vs. Iterators vs. Generators
      • Generator Expression
      • Stacks (LIFO) / Queues (FIFO)
      • What does -1 mean in numpy reshape?
      • Fold Left and Right in Python
      • Flatten a nested list of lists
      • Flatten a nested dictionary
      • Traverse A Tree
      • How to Implement Breadth-First Search
      • Breadth First Search
        • Level Order Tree Traversal
        • Breadth First Search or BFS for a Graph
        • BFS for Disconnected Graph
      • Trees and Tree Algorithms
      • Graph and its representations
      • Graph Data Structure Interview Questions
      • Graphs in Python
      • GitHub Repo's
    • Python in CG Production
    • GLSL/HLSL Shading programming
    • Deep Learning Specialization
      • Neural Networks and Deep Learning
      • Untitled
      • Untitled
      • Untitled
    • TensorFlow for AI, ML, and DL
      • Google ML Crash Course
      • TensorFlow C++ API
      • TensorFlow - coursera
      • Notes
      • An Introduction to different Types of Convolutions in Deep Learning
      • One by One [ 1 x 1 ] Convolution - counter-intuitively useful
      • SqueezeNet
      • Deep Compression
      • An Overview of ResNet and its Variants
      • Introducing capsule networks
      • What is a CapsNet or Capsule Network?
      • Xception
      • TensorFlow Eager
    • GitHub
      • Project README
    • Agile - User Stories
    • The Open-Source Data Science Masters
    • Coding Challenge Websites
    • Coding Interview
      • leetcode python
      • Data Structures
        • Arrays
        • Linked List
        • Hash Tables
        • Trees: Basic
        • Heaps, Stacks, Queues
        • Graphs
          • Shortest Path
      • Sorting & Searching
        • Depth-First Search & Breadth-First Search
        • Backtracking
        • Sorting
      • Dynamic Programming
        • Dynamic Programming: Basic
        • Dynamic Programming: Advanced
    • spaCy
    • Pandas
    • Python Packages
    • Julia
      • jupyter
    • macos
    • CPP
      • Debugging
      • Overview of memory management problems
      • What are lvalues and rvalues?
      • The Rule of Five
      • Concurrency
      • Avoiding Data Races
      • Mutex
      • The Monitor Object Pattern
      • Lambdas
      • Maya C++ API Programming Tips
      • How can I read and parse CSV files in C++?
      • Cpp NumPy
    • Advanced Machine Learning
      • Wk 1
      • Untitled
      • Untitled
      • Untitled
      • Untitled
  • data science
    • Resources
    • Tensorflow C++
    • Computerphile
      • Big Data
    • Google ML Crash Course
    • Kaggle
      • Data Versioning
      • The Basics of Rest APIs
      • How to Make an API
      • How to deploying your API
    • Jupiter Notebook Tips & Tricks
      • Jupyter
    • Image Datasets Notes
    • DS Cheatsheets
      • Websites & Blogs
      • Q&A
      • Strata
      • Data Visualisation
      • Matplotlib etc
      • Keras
      • Spark
      • Probability
      • Machine Learning
        • Fast Computation of AUC-ROC score
    • Data Visualisation
    • fast.ai
      • deep learning
      • How to work with Jupyter Notebook on a remote machine (Linux)
      • Up and Running With Fast.ai and Docker
      • AWS
    • Data Scientist
    • ML for Beginners (Video)
    • ML Mastery
      • Machine Learning Algorithms
      • Deep Learning With Python
    • Linear algebra cheat sheet for deep learning
    • DL_ML_Resources
    • Awesome Machine Learning
    • web scraping
    • SQL Style Guide
    • SQL - Tips & Tricks
  • 💡Ideas & Thoughts
    • Outdoors
    • Blog
      • markdown
      • How to survive your first day as an On-set VFX Supervisor
    • Book Recommendations by Demi Lee
  • career
    • Skills
    • learn.co
      • SQL
      • Distribution
      • Hypothesis Testing Glossary
      • Hypothesis Tests
      • Hypothesis & AB Testing
      • Combinatorics Continued and Maximum Likelihood Estimation
      • Bayesian Classification
      • Resampling and Monte Carlo Simulation
      • Extensions To Linear Models
      • Time Series
      • Distance Metrics
      • Graph Theory
      • Logistic Regression
      • MLE (Maximum Likelihood Estimation)
      • Gradient Descent
      • Decision Trees
      • Ensemble Methods
      • Spark
      • Machine Learning
      • Deep Learning
        • Backpropagation - math notation
        • PRACTICE DATASETS
        • Big Data
      • Deep Learning Resources
      • DL Datasets
      • DL Tutorials
      • Keras
      • Word2Vec
        • Word2Vec Tutorial Part 1 - The Skip-Gram Model
        • Word2Vec Tutorial Part 2 - Negative Sampling
        • An Intuitive Explanation of Convolutional Neural Networks
      • Mod 4 Project
        • Presentation
      • Mod 5 Project
      • Capstone Project Notes
        • Streaming large training and test files into Tensorflow's DNNClassifier
    • Carrier Prep
      • The Job Search
        • Building a Strong Job Search Foundation
        • Key Traits of Successful Job Seekers
        • Your Job Search Mindset
        • Confidence
        • Job Search Action Plan
        • CSC Weekly Activity
        • Managing Your Job Search
      • Your Online Presence
        • GitHub
      • Building Your Resume
        • Writing Your Resume Summary
        • Technical Experience
      • Effective Networking
        • 30 Second Elevator Pitch
        • Leveraging Your Network
        • Building an Online Network
        • Linkedin For Research And Networking
        • Building An In-Person Network
        • Opening The Line Of Communication
      • Applying to Jobs
        • Applying To Jobs Online
        • Cover Letters
      • Interviewing
        • Networking Coffees vs Formal Interviews
        • The Coffee Meeting/ Informational Interview
        • Communicating With Recruiters And HR Professional
        • Research Before an Interview
        • Preparing Questions for Interviews
        • Phone And Video/Virtual Interviews
        • Cultural/HR Interview Questions
        • The Salary Question
        • Talking About Apps/Projects You Built
        • Sending Thank You's After an Interview
      • Technical Interviewing
        • Technical Interviewing Formats
        • Code Challenge Best Practices
        • Technical Interviewing Resources
      • Communication
        • Following Up
        • When You Haven't Heard From an Employer
      • Job Offers
        • Approaching Salary Negotiations
      • Staying Current in the Tech Industry
      • Module 6 Post Work
      • Interview Prep
  • projects
    • Text Classification
    • TERRA-REF
    • saildrone
  • Computer Graphics
  • AI/ML
  • 3deeplearning
    • Fast and Deep Deformation Approximations
    • Compress and Denoise MoCap with Autoencoders
    • ‘Fast and Deep Deformation Approximations’ Implementation
    • Running a NeuralNet live in Maya in a Python DG Node
    • Implement a Substance like Normal Map Generator with a Convolutional Network
    • Deploying Neural Nets to the Maya C++ API
  • Tools/Plugins
  • AR/VR
  • Game Engine
  • Rigging
    • Deformer Ideas
    • Research
    • brave rabbit
    • Useful Rigging Links
  • Maya
    • Optimizing Node Graph for Parallel Evaluation
  • Houdini
    • Stuff
    • Popular Built-in VEX Attributes (Global Variables)
Powered by GitBook
On this page
  • Fold
  • Laws of fold
  • Fold in Python
  • Now what?
  • Conclusion
  • Resources
  1. coding
  2. Python

Fold Left and Right in Python

PreviousWhat does -1 mean in numpy reshape?NextFlatten a nested list of lists

Last updated 6 years ago

exposes a number of enriched with a plethora of modules composing . It is a pragmatic language that does not confine the developer in a specific programming paradigm. A Python developer can write imperative, procedural, object oriented or functional code. In Python, common functional constructs are available as (e.g. map, filter, all, any, sum...). Additional higher-order functions are regrouped in the module (e.g. reduce, partial...). Prior to crafting some Python code, let's take a detour in some potentially more arcane areas of functional programming, in particular surrounding the fold concepts.

Despite being primary a Python article, some of the initial code examples are in . Haskell is the perfect cradle for concepts like Folding. In addition, Haskell code, like Python code, reads like pseudo-code.

Fold

regroups a family of pertaining to the functional programming domain. At a high level, folding allows to deconstruct or reduce data. A typical signature for a generic fold function is the following: fold f z xsfold f z xs

Where:

  • f is a higher-order function taking two arguments, an accumulator and an element of the list xs. It is applied recursively to each element of xs.

  • z is the initial value of the accumulator and an argument of the function f.

  • xs is a collection.

Fold functions come in different kinds, the two main linear ones are foldl and foldr.

foldl

foldl, for "fold left", is left associative. Think of foldl as "fold from the left" (image courtesy of Wikipedia):

Left fold transformation

Let ⊗ be a variable bound to the function of two arguments f in the diagram above. The foldl function can be defined as follows:

foldl (⊗) z [1,2,3,4,5]=((((z ⊗ 1) ⊗ 2) ⊗ 3) ⊗ 4) ⊗ 5foldl (⊗) z [1,2,3,4,5]=((((z ⊗ 1) ⊗ 2) ⊗ 3) ⊗ 4) ⊗ 5

To cement the concept, here is an example in Haskell with the subtraction operator:

> foldl (-) 0 [1,2,3]
-6
> (((0 - 1) - 2) - 3)
-6

foldr

foldr, for "fold right", is right associative. Think of foldr as "fold from the right" (image courtesy of Wikipedia):

As for foldl in the previous section, let ⊗ be a variable bound to the function of two arguments f. The foldr operator can be defined as:

foldr (⊗) z [1,2,3,4,5]=1 ⊗ (2 ⊗ (3 ⊗ (4 ⊗ (5 ⊗ z))))foldr (⊗) z [1,2,3,4,5]=1 ⊗ (2 ⊗ (3 ⊗ (4 ⊗ (5 ⊗ z))))

Following is an example with the division operator:

> foldr (/) 10 [1,2,3]
0.15
>  1 / (2 / (3 / 10))
0.15

Laws of fold

First duality theorem

> foldl (+) 0 [1,2,3]
6
> foldr (+) 0 [1,2,3]
6
> foldl (+) 0 [1,2,3] == foldr (+) 0 [1,2,3]
True

Third duality theorem

For all finite lists xs, foldr f e xs = foldl (flip f) e (reverse xs)foldr f e xs = foldl (flip f) e (reverse xs)

where, flip f x y=f y xflip f x y=f y x

> foldl (-) 0 [1,2,3]
-6
> foldr (-) 0 [1,2,3]
2
> foldl (flip(-)) 0 (reverse [1,2,3])
2
> foldr (-) 0 [1,2,3] == foldl (flip(-)) 0 (reverse [1,2,3])
True

Fold in Python

Note: The snippets of code used as examples in this article target Python 3.

foldl in Python

>>> import functools
>>> import operator
>>> foldl = lambda func, acc, xs: functools.reduce(func, xs, acc)
>>> foldl(operator.sub, 0, [1,2,3])
-6
>>> foldl(operator.add, 'L', ['1','2','3'])
'L123'

Or more formally as a function:


import functools
import operator

def foldl(func, acc, xs):
  return functools.reduce(func, xs, acc)

# tests
print(foldl(operator.sub, 0, [1,2,3])) # -6
print(foldl(operator.add, 'L', ['1','2','3'])) # 'L123'

foldr in Python

Relying on the third duality theorem evoked in the Laws of fold section above, foldr can be crafted as a lambda:


>>> import functools
>>> import operator
>>> foldr = lambda func, acc, xs: functools.reduce(lambda x, y: func(y, x), xs[::-1], acc)
>>> foldr(operator.sub, 0, [1,2,3])
2
>>> foldr(operator.add, 'R', ['1', '2', '3'])
'123R'

Lambdas implemented as above are not generally conducive of good code readibilty. The following code, although longer, may be arguably more maintainable:


import functools
import operator

def flip(func):
    @functools.wraps(func)
    def newfunc(x, y):
        return func(y, x)
    return newfunc

def foldr(func, acc, xs):
    return functools.reduce(flip(func), reversed(xs), acc)

# test
print(foldr(operator.sub, 0, [1,2,3])) # 2
print(foldr(operator.add, 'R', ['1','2','3'])) # '123R'

Now what?

We now have new toy functions in Python, foldl and foldr, what can we do with those?

Reimplementing existing functions with reduce (foldl)

The folding concept opens the doors to build many other functions. It allows to be done without having recourse to writing explicit recursive code or managing loops. For example, max, min, sum, prod, any, all, map, filter among others, can all be defined with folding/reduce functions.

Here are some simplistic examples, using lambdas for conciseness:


>>> import functools
>>> import operator
>>> lmax = lambda xs: functools.reduce(lambda x, y: x if x > y else y, xs)
>>> lmax([1,2,3,4,5])
5
>>> lmin = lambda xs: functools.reduce(lambda x, y: x if x < y else y, xs)
>>> lmin([1,2,3,4,5])
1
>>> lsum = lambda xs: functools.reduce(operator.add, xs)
>>> lsum([1,2,3,4,5])
15
>>> product = lambda xs: functools.reduce(operator.mul, xs)
>>> product([1,2,3,4,5])
120
>>> lany = lambda pred, xs: functools.reduce(lambda x, y: x or pred(y), xs, False)
>>> lany(lambda x: x > 3, [1,2])
False
>>> lany(lambda x: x > 3, [1,2,3,4,5,6])
True
>>> lall = lambda pred, xs: functools.reduce(lambda x, y: x and pred(y), xs, True)
>>> lall(lambda x: x > 3, [4,5,6,7])
True
>>> lall(lambda x: x > 3, [1,2])
False
>>> lmap = lambda func, xs: functools.reduce(lambda x, y: x + [func(y)], xs, [])
>>> lmap(lambda x: x + 2, [1,2,3,4,5])
[3, 4, 5, 6, 7]
>>> lfilter = lambda func, xs: functools.reduce(lambda x, y: x + [y] if func(y) else x, xs, [])
>>> lfilter(lambda x: x % 2 == 0, [1,2,3,4,5,6,7,8,9])
[2, 4, 6, 8]

Final Example


import functools

def foldl(func, acc, xs):
  return functools.reduce(func, xs, acc)

def flip(func):
    @functools.wraps(func)
    def newfunc(x, y):
        return func(y, x)
    return newfunc

def foldr(func, acc, xs):
    return functools.reduce(flip(func), reversed(xs), acc)

def first(func, acc, xs):
    return foldr(lambda x, y: x if func(x) else y, acc, xs)

def last(func, acc, xs):
    return foldl(lambda x, y: y if func(y) else x, acc, xs)

print(last(lambda x: x<8, 99, [1,2,3,4,5,6,7,8,9]))   # => 7
print(first(lambda x: x>3, 99, [1,2,3,4,5,6,7,8,9]))  # => 4
print(first(lambda x: x>20, 99, [1,2,3,4,5,6,7,8,9])) # => 99

first and last don't require any loop or explicit recursion. first uses foldr taking advantage of the right folding whereas last relies on foldl.

Conclusion

In this era of rediscovery of functional programming, there is much more to explore and to apply to languages that are not inherently functional. Arguably, from a pragmatic perspective, there may be little we need that is not already provided in the current versions of Python and that would require some sophisticated folding mechanisms. Further more, other higher-order functions flagships along with fold, like map and filter, can be expressed in Python with elegant list comprehensions and generator expressions, but this should be the subject of a different article.

Resources

Right fold transformation

In the book , the authors and wrote a section on the Laws of fold. The first three laws are called duality theorems and concern the relationship between foldl and foldr. For simplification and in the context of this article, let's focus on the first and third duality theorems.

For all finite lists xs, if f is and has identity element e, then foldr f e xs = foldl f e xsfoldr f e xs = foldl f e xs

To concretely illustrate this principle in the , see the following example using the addition as operation and 0 as the for addition:

To illustrate this principle, let's take another simple example in , this time with subtraction that is not associative:

Despite some resistance from Guido Van Rossum (see ), Python has a Fold function. It is named and is a built-in function in Python 2. In Python 3, it can be found in the module: .

Python already has foldl because is a foldl construct. As an exercise and to mimic Haskell, a foldl function can be written as follows with a lambda:

Note: xs[::-1] is the Python idiomatic way to return the reverse of a list (see this ). The other option, more readable, is to use the built-in function.

Note: the flip function above is courtesy of

All the examples above, except product (in that regard see ), have an existing implementation in Python. Also, all of the functions above are relying on reduce (foldl) and none are taking advantage of foldr.

To avoid ending on a dried note and to justify the functional workout executed in the sections above, here is a simple scenario that may demonstrate a decent usage of foldl and foldr in Python. Peter Drake presents this construct in his . Imagine that, given a list, we need to identify the last and/or the first element that satisfies a certain predicate. This could be written as follows:

👨‍💻
Introduction to Functional Programming using Haskell
Richard Bird
Philip Wadler
associative
Haskell REPL
identity element
Haskell
The fate of reduce() in Python 3000
reduce
functools
functools.reduce
functools.reduce
answer from Alex Martelli on stackoverlow
reversed
Raymond Hettinger in a stackoverflow answer
another stackoverflow response from Raymond Hettinger
Lambdas and folds Youtube video
Python
Haskell
Haskell REPL
Introduction to Functional Programming using Haskell
Thinking Functionally with Haskell
Fold
Richard Bird
Philip Wadler
Alex Martelli
Raymond Hettinger
Python
built-in functions
The Python Standard Library
built-in functions
functools
Haskell
Fold
higher-order functions