Lists and Higher Order Functions

A function that takes another function as input or output.

A function that takes a function as input and applies it twice to an input value. It's a versatile tool for applying transformations repeatedly.

A function that maps an input value to another value of the same type. It's a building block for various transformations.

A function that takes a Boolean value and inverts it.

An elegant way to define simple functions in Scala, using a shorter syntax.

A function that takes a function as a predicate and keeps elements from a list until the predicate fails.

A function that takes a function as a predicate and drops elements from a list until the predicate fails.

A function that takes a value and returns its negation.

Scala lists are collections of elements of the same type, where each element has a reference to the next one, forming a chain. Accessing the i-th element requires iterating through i elements, making it a linear time operation (O(i)).

In Scala, lists are immutable, meaning once created, you cannot directly modify their content. To change a list, you must create a new one with the desired modifications.

The 'Nil' keyword represents the empty list in Scala. It is a special case where the list contains no elements. It is the base case for the recursive definition of lists.

The ':' (cons) operator is used to create a new list by adding an element (head) to an existing list (tail). It's like adding a bead to a necklace: the existing necklace (tail) remains intact, and a new bead (head) is appended to the front.

In a list built with the cons operator, the first element (leftmost) is called the 'head' and the remaining elements are called the 'tail.'

The head function takes a list and returns its first element. If the list in empty, it throws an exception.

The tail function takes a list and returns a new list containing all elements except the first one.

Pattern matching is a powerful feature of Scala that allows you to write concise and expressive code for working with different list cases. It's crucial for creating functions that handle variations in list structures.

A higher-order function that applies a given function to each element of a list to create a new list.

A higher-order function that reduces a list to a single value by applying a given function cumulatively to each element.

A higher-order function that removes elements from a list based on a condition.

A function that checks if a condition is true for a given input.

A function that takes a list and a predicate (a function that checks a condition) as inputs and returns a new list containing only elements from the original list that fulfill the predicate.

A function that takes a list and a function (that transforms elements) as inputs and returns a new list containing the transformed elements from the original list.

A type parameter allows a function to work with different types of data. This means you can write a single function that can handle lists of integers, strings, or any other type.

The function concat takes two lists as input and returns a new list that contains all the elements of both lists.

The function take takes a number n and a list as input and returns a new list containing the first n elements of the input list. If the list has fewer than n elements, it returns the entire list.

The function drop takes a number n and a list as input and returns a new list that is the same as the input list but with the first n elements removed. If the list has fewer than n elements, it returns an empty list.

The function reverse takes a list as input and returns a new list that contains the same elements but in reverse order.

The function reverse is inefficient because it creates many new lists during the recursion process, which is computationally expensive, especially for long lists.

The efficiency of the reverse function can be measured by counting the number of :: operations used, not the number of ::: operations.

The running time of the reverse function can be analyzed using a recursive function. The base case is T(0) = 0, meaning no :: operations are performed for an empty list. The recursive case involves T(n) being the number of :: operations for a list of length n.

A function that combines elements of a list with a given operation (e.g., addition, multiplication) and an initial value (e.g., 0, 1). It iterates over the list from right to left.

A function that combines elements of a list with a given operation and an initial value, iterating from left to right. It's tail recursive.

A value that doesn't influence the result of the operation when combined with the initial element in fold functions. Examples: 0 for sum, 1 for product, true for all quantifier.

A function that applies a predicate to each element of a list and returns true only if all elements satisfy the predicate. Uses recursion.

A function that sums all elements of a list. Uses recursion.

A function that multiplies all elements of a list. Uses recursion.

The process of breaking down a problem into smaller, self-similar subproblems and combining their solutions to solve the original problem.

A recursive function that is optimized to avoid creating new stack frames for each recursive call. Makes it more efficient.

A sorting algorithm that inserts each element into its correct position in a sorted sublist. It starts from the second element and compares it with the element to its left, swapping them until the element is in the correct position. It repeats this process for each element.

An algorithm that recursively sorts a list by first recursively sorting the tail of the list and then inserting the head element into its correct position in the sorted tail.

A function used in insertionsort to insert a new element into its correct position in a sorted list. It iterates through the list, comparing the new element with each element in the list, swapping them until the new element is in the correct position.

The starting value used in the fold operation, representing the initial state of the computation. It determines the type of the accumulated result.

The function applied to each element during the fold operation. It takes two arguments: the current accumulated result and the next element from the list.