Abstraction

Concepts of Efficiency and Abstraction

  • Importance of Order of Growth

    • Focus on whether the order of growth is linear or logarithmic.

    • Continuous examination of Big O notation concepts throughout course.

Course Objectives

  • Emphasis on Abstraction

    • Aim to hide complexities in simpler representations.

    • Abstraction enables higher-level thinking without getting lost in details.

  • Analogy for Learning

    • "30,000 foot overview" analogy for understanding abstraction.

Examples for Practical Understanding

Example 1: First Letters

  • Task: Create a function that retrieves the first letters of each word in a sentence.

    • Input: Sentence provided (e.g., "this is spam").

    • If the sentence is empty: Return empty sentence.

    • Function Mechanism:

    • first item: Retrieves the first word; first item of first word: Retrieves the first letter of the first word.

    • Recursively calls for first letters of the remaining words in the sentence.

    • Output: Sentence of first letters (e.g., "tis").

Example 2: Square Sense (SquareWord)

  • Task: Create a function to square numbers in a sentence.

    • Input: Sentence with words (e.g., "one two three").

    • If the sentence is empty: Return empty sentence.

    • SquareWord Function Details:

    • Converts words to numbers, squares them, and returns them as words.

    • If input word is numerical, squares it, else leaves it unchanged.

    • Mechanism:

    • First word processed with square word, then recursively processes the rest of the words.

    • Possible Input: Word "two"; Output: Word "four" (from squaring).

Conceptual Similarities

  • Both examples show a structural abstraction:

    • Both functions process the first word, apply a transformation, and recurse on the remainder.

    • General principle: Create functions that can be applied broadly to similar problems.

Introduction of Higher-Level Abstraction: Every Function

Parameters in Haskell

  • Haskell allows passing functions as parameters.

  • every: This function applies a given function (e.g., transformation) to every word in a sentence.

    • Signature: First parameter is a function from language to language; second is the sentence.

    • Mechanism:

    • every f s processes the first word with function f and applies f recursively to the rest of the sentence.

Introduced Function Examples: Keep and Accumulate

Keep Function

  • Keeps words that meet certain criteria.

  • Signature: Accepts a function (word -> boolean) and sentence.

  • Example of Filtering:

    • Using a function to keep only words that match a particular property (e.g., equal to "spam").

    • Returns filtered words, discarding others.

Accumulate Function

  • Combines results of words in a sentence using a combiner function.

  • Signature: Combiner takes two words and returns a single word.

  • Example: Concatenating all words together into a single output.

  • Mechanism explained:

    • If only one word exists, return it; else combine first word with recursive process on the remainder.

Practical Exercises and Assignments

  • Specific functions require using every, keep, or accumulate:

    • Count Letters: Uses every to apply a counting function on sentence words.

    • Remove all Fewer: Decides on keep to filter letters or words.

    • Summing Numbers: Utilizes accumulate to return combined sums of numbers represented as words.

Recap and Differences Between Functions

  • Every: Applies a transformation to every word.

  • Keep: Filters words based on a condition.

  • Implications of using these functions to streamline code and create reusable abstractions.

Example Use Cases for Assignment Problems

  1. Exaggerate: Doubles numbers in a sentence and modifies specific words.

  2. Keep: Filters words based on criteria (e.g., first & last letters matching).

  3. Hyphenate: Combine words in a sentence with hyphens.

  4. Acronym: Generate acronyms from sentences while filtering out connecting words (e.g., "of", "the").

Conclusion

  • Integration of discussing efficiency, abstraction techniques, and practical application in programming.

  • Challenge to take new concepts and implement them through assignments that reinforce knowledge of functions in Haskell.