Lecture

Combinatorial Search: For-Expressions

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

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 fundamental software construction concepts (reusability, abstr ...

Description

This lecture covers the use of for-expressions in Scala to simplify complex computations involving nested loops and higher-order functions. It demonstrates how for-expressions can be translated into map, flatMap, and withFilter functions, providing a more intuitive way to manipulate lists. The lecture also explores the application of for-expressions in solving problems like combinatorial search and N-Queens. Additionally, it discusses the implementation of maps and sets in Scala collections, along with practical examples and exercises to reinforce the concepts.

Instructors (2)

Martin Odersky

Martin Odersky heads the programming research group at EPFL. His research interests cover fundamental as well as applied aspects of programming languages. They include semantics, type systems, programming language design, and compiler construction. The main focus if his work lies in the integration of object-oriented and functional programming. His research thesis is that the two paradigms are just two sides of the same coin and should be unified as much as possible. To prove this he has experimented a number of language designs, from Pizza to GJ to Functional Nets. He has also influenced the development of Java as a co-designer of Java generics and as the original author of the current javac reference compiler. His current work concentrates on the Scala programming language, which unifies FP and OOP, while staying completely interoperable with Java and .NET. Martin Odersky got his doctorate from ETHZ, in 1989. He held research positions at the IBM T.J. Watson Research Center from 1989 and at Yale University from 1991. He was then a professor at the University of Karlsruhe from 1993 and at the University of South Australia from 1997. He joined EPFL as full professor in 1999. He is associate editor of the Journal of Functional Programming and member of IFIP WG 2.8. He was conference chair for ICFP 2000, and program chair for ECOOP 2004 as well as ETAPS/CC 2007.

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Official source

Ontological neighbourhood

Theoretical computer science

Programming language theory: High-level programming languages

Information engineering

Natural language processing: Topics in natural language processing

Related concepts (30)

Translation

Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between translating (a written text) and interpreting (oral or signed communication between users of different languages); under this distinction, translation can begin only after the appearance of writing within a language community.

Translation studies

Translation studies is an academic interdiscipline dealing with the systematic study of the theory, description and application of translation, interpreting, and localization. As an interdiscipline, translation studies borrows much from the various fields of study that support translation. These include comparative literature, computer science, history, linguistics, philology, philosophy, semiotics, and terminology. The term "translation studies" was coined by the Amsterdam-based American scholar James S.

Functional programming

In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program. In functional programming, functions are treated as first-class citizens, meaning that they can be bound to names (including local identifiers), passed as arguments, and returned from other functions, just as any other data type can.

Higher-order programming

Higher-order programming is a style of computer programming that uses software components, like functions, modules or objects, as values. It is usually instantiated with, or borrowed from, models of computation such as lambda calculus which make heavy use of higher-order functions. A programming language can be considered higher-order if components, such as procedures or labels, can be used just like data. For example, these elements could be used in the same way as arguments or values.

Literal translation

Literal translation, direct translation, or word-for-word translation is a translation of a text done by translating each word separately without looking at how the words are used together in a phrase or sentence. In translation theory, another term for literal translation is metaphrase (as opposed to paraphrase for an analogous translation). It is to be distinguished from an interpretation (done, for example, by an interpreter). Literal translation leads to mistranslation of idioms, which was once a serious problem for machine translation.

Related lectures (32)

Translation of for

Explains the translation of for-expressions in Scala using map, flatmap, and filter functions, with examples and a discussion on its generalization to different types.

Group Actions: Theory and Examples

Explores concrete examples of group actions on sets, focusing on actions that do not change the set.

The Label of Edges: Set

Explores edge labels, skills like aggregation and deduction, and the structure of contents.

Loops: Control Statements and Functions

Covers modeling control statements with functions in Scala, including while loops, repeat loops, and for-loops translation.

Sets and Operations: Introduction to Mathematics