Functional Programming and Data Structures Review

Vocabulary flashcards covering Haskell functional programming, algebraic data types, tail recursion, runtime complexities, fold functions, and tree operations in C and Haskell.

Worst-case runtime for Access (Arrays vs. Lists)

$o(1)$ for arrays and $o(n)$ for lists.

Worst-case runtime for Insert/Delete (Arrays vs. Lists)

$o(n)$ for arrays and $o(1)$ for lists.

Accumulating parameter

A programming technique used to transform a standard recursive function definition into an equivalent tail recursive definition.

Pattern matching

A Haskell mechanism demonstrated in function definitions over lists, such as Product [] = 1 and Product (x:xs) = x * product xs.

Haskell Fold evaluations

Results of fold expressions: Foldr (+) 0 (1, 2, 3) = 6, Foldr (-) 0 (1, 2, 3) = 2, Foldl (-) 0 (1, 2, 3) = -6, Foldr (+) 5 [1, 2, 3] = 11, and Foldl (-) 5 [1, 2, 3] = -1.

List concatenation operator (++)

A Haskell function with type (++) :: [a] -> [a] -> [a], defined by (++) [] ys = ys and (++) (x:xs) ys = x : (xs ++ ys).

Foldr (++) []

A Haskell expression that flattens a list of lists into a single list.

Syntactic sugar for lists in Haskell

The notation [1, 2, 3], which desugars to 1:2:3:[] and is equivalent to 1:(2:(3:[])).

Foldl vs. Foldr (Tail Recursiveness)

Foldl is tail recursive, whereas foldr is not tail recursive.

Type of foldr

Foldr :: (a -> b -> b) -> b -> [a] -> b

Type of foldl

Foldl :: (b -> a -> b) -> b -> [a] -> b

Product algebraic data type

A category of algebraic data types that pairs components, exemplified by pairs (a, b), tuples, and records.

Projections

Functions that extract elements from a product type, specifically fst (x, ) = x and snd (, y) = y.

Sum / Co-product algebraic data type

An algebraic data type representing disjoint alternatives, exemplified by enumerated types, tagged unions, and definitions like data Shape = circle float | rectangle float float.

Recursive data type

A data type that refers to itself in its definition, such as data Tree a = Node a (Tree a) (Tree a) | Tip.

Maybe data type evaluations

Evaluations over the type data maybe = nothing | just a: sum Nothing = 0, product (Just 2) = 2, length (Just "abc") = 1, and length Nothing = 0.

Functional programming paradigm snippets

Snippets characterized by immutable values and pure returns, such as Const int x = 5; and Int f(int x) { return 2*x+1; }.

Imperative programming paradigm snippets

Snippets characterized by mutable state and explicit mutation, such as x += 5; and Void swap (int *a, int *b) { Int h = *a; *a = *b; *b = h; }.

Quicksort element comparison counts

A call to standard filter-based qsort compares each element twice, whereas qsort implemented with sortp compares each element once.

Tail recursiveness of qsort vs. sortp

sortp is tail recursive, but qsort is not tail recursive.

Merge function

A Haskell list function defined as Merge [] ys = ys, Merge xs [] = xs, and Merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys.

Linked list printList function (C)

A C traversal that iterates through nodes via current = current->next until NULL, producing the output 1, 2, 3 for chained nodes n3 -> n2 -> n1.

leaves (Haskell tree function)

A function on data Tree a = Tip | Branch (Tree a) a (Tree a) defined by leaves Tip = [], leaves (Branch Tip x Tip) = [x], and leaves (Branch l _ r) = leaves l ++ leaves r.

count_leaves (C tree function)

A C recursive function that returns 0 if p == NULL, 1 if both p->left == NULL and p->right == NULL, and count_leaves(p->left) + count_leaves(p->right) otherwise.