**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Fold (higher-order function)

Summary

In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.
Folds are in a sense dual to unfolds, which take a seed value and apply a function corecursively to decide how to progressively construct a corecursive data structure, whereas a fold recursively breaks that structure down, replacing it with the results of applying a combining function at each node on its terminal values and the recursive results (catamorphism, versus anamorphism of unfolds).
Folds can be regarded as consistently replacing the structural components of a data structure with functions and values. Lists, for example, are built up in many functional languages from two primitives: any list is either an empty list, commonly called nil ([]), or is constructed by prefixing an element in front of another list, creating what is called a cons node ( Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) ), resulting from application of a cons function (written down as a colon (:) in Haskell). One can view a fold on lists as replacing the nil at the end of the list with a specific value, and replacing each cons with a specific function. These replacements can be viewed as a diagram:
There's another way to perform the structural transformation in a consistent manner, with the order of the two links of each node flipped when fed into the combining function:
These pictures illustrate right and left fold of a list visually. They also highlight the fact that foldr (:) [] is the identity function on lists (a shallow copy in Lisp parlance), as replacing cons with cons and nil with nil will not change the result.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Related concepts (48)

Related courses (8)

Related lectures (96)

Fold (higher-order function)

In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions.

Map (higher-order function)

In many programming languages, map is the name of a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form. The concept of a map is not limited to lists: it works for sequential containers, tree-like containers, or even abstract containers such as futures and promises. Suppose we have a list of integers [1, 2, 3, 4, 5] and would like to calculate the square of each integer.

Corecursion

In computer science, corecursion is a type of operation that is to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data.

CS-214: Software construction

Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and
fundam

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

Higher-Order Functions Using Naive SubstitutionsCS-210: Functional programming

Explores higher-order functions, environments, evaluation using substitution, and examples like twice factorial.

Avoiding Variable CaptureCS-210: Functional programming

Explores variable capture in higher-order functions and the importance of variable renaming.

Functional Programming in PythonCS-119(h): Information, Computation, Communication

Covers functional programming concepts in Python, showcasing filtering lists based on specific criteria.

Macro annotations are an important feature in Scala 2 macro system. Many projects use macro annotations to implement their systems or libraries. Due to the unportability of Scala 2 macro system, Scala 3 redesigns the macro system to make it more reliable and portable. But macro annotations have not been implemented in Scala 3 yet, resulting in some inconvenience in migrating projects that use macro annotations to Scala 3. Following the core design of Scala 2 macro annotations, we introduce the macro annotations as transformations from definitions to definitions. In this thesis, we also list rules to keep our simplicity but not hurt its functionality at the same time. The main difference between macro annotations of Scala 2 and Scala 3 is that in Scala 2 macro annotations expand before typechecking, while they expand after typechecking in Scala 3. Our implementation is based on a breadth-first approach, which helps us implement a tail-recursive transformation. We write test cases covering common and even uncommon cases to test the correctness of our macro annotation system.

2022