diff options
Diffstat (limited to 'js/scripting-lang/tutorials/Combinators_Deep_Dive.md')
| -rw-r--r-- | js/scripting-lang/tutorials/Combinators_Deep_Dive.md | 812 |
1 files changed, 0 insertions, 812 deletions
diff --git a/js/scripting-lang/tutorials/Combinators_Deep_Dive.md b/js/scripting-lang/tutorials/Combinators_Deep_Dive.md deleted file mode 100644 index e73382b..0000000 --- a/js/scripting-lang/tutorials/Combinators_Deep_Dive.md +++ /dev/null @@ -1,812 +0,0 @@ -# Problem Solving with Functional Programming - -This tutorial takes you deep into the world of combinators and functional programming patterns. We'll explore how to think about problems functionally and solve them using the language's combinator-based architecture. - -## Prerequisites - -This tutorial assumes you've completed the Introduction tutorial and are comfortable with: - -- Basic function definitions and application -- Pattern matching with `when` expressions -- Working with tables -- Function references using `@` - -## The Combinator Mindset - -### What Are Combinators? - -Combinators are functions that combine other functions to create new behaviors. In our language, **everything is a function call** - even operators like `+` and `*` are translated to combinator functions like `add` and `multiply`. - -```plaintext -/* Understanding the translation */ -x + y * z - -/* Becomes internally: */ -add(x, multiply(y, z)) -``` - -This approach gives us: -- **Zero ambiguity**: Every expression has exactly one interpretation -- **Functional foundation**: Everything is a function call -- **Composability**: Functions can be combined in powerful ways -- **Extensibility**: New operations are just new functions - -## Core Combinators: Building Blocks - -### Map: Transform Everything - -`map` applies a function to every element in a collection: - -```plaintext -/* Basic map usage */ -double : x -> x * 2; -numbers : {1, 2, 3, 4, 5}; -doubled : map @double numbers; -/* Result: {2, 4, 6, 8, 10} */ - -/* Map with tables */ -person : {name: "Alice", age: 30, city: "NYC"}; -get_age : x -> x.age; -ages : map @get_age person; -/* Result: {name: 30, age: 30, city: 30} */ - -/* Map with complex transformations */ -format_person : person -> { - name: person.name, - age: person.age + " years old", - city: "📍 " + person.city -}; -formatted : map @format_person {alice: person}; -/* Result: {alice: {name: "Alice", age: "30 years old", city: "📍 NYC"}} */ -``` - -### Filter: Select What You Want - -`filter` keeps only elements that satisfy a predicate: - -```plaintext -/* Basic filtering */ -is_even : x -> x % 2 = 0; -numbers : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; -evens : filter @is_even numbers; -/* Result: {2, 4, 6, 8, 10} */ - -/* Filter with complex predicates */ -is_adult : person -> person.age >= 18; -people : { - alice: {name: "Alice", age: 25}, - bob: {name: "Bob", age: 16}, - charlie: {name: "Charlie", age: 30} -}; -adults : filter @is_adult people; -/* Result: {alice: {name: "Alice", age: 25}, charlie: {name: "Charlie", age: 30}} */ - -/* Chaining filter conditions */ -is_high_value : x -> x > 5; -is_low_value : x -> x < 15; -numbers : {1, 3, 7, 12, 18, 22}; -medium : filter @is_high_value (filter @is_low_value numbers); -/* Result: {7, 12} */ -``` - -### Reduce: Accumulate Results - -`reduce` combines all elements into a single value: - -```plaintext -/* Basic reduction */ -numbers : {1, 2, 3, 4, 5}; -sum : reduce @add 0 numbers; -/* Result: 15 */ - -/* Complex reduction */ -people : { - alice: {name: "Alice", salary: 50000}, - bob: {name: "Bob", salary: 60000}, - charlie: {name: "Charlie", salary: 45000} -}; -get_salary : person -> person.salary; -total_salary : reduce @add 0 (map @get_salary people); -/* Result: 155000 */ - -/* Building complex objects with reduce */ -entries : {name: "Alice", age: 30, city: "NYC"}; -to_list : key value -> {key: key, value: value}; -pairs : reduce @to_list {} entries; -/* This would create a list-like structure from key-value pairs */ -``` - -## Function Composition: The Power of Combination - -### Compose: Right-to-Left Composition - -`compose` combines functions so the output of one becomes the input of another: - -```plaintext -/* Basic composition */ -double : x -> x * 2; -increment : x -> x + 1; -square : x -> x * x; - -/* Mathematical style: g then f */ -double_then_increment : compose @increment @double; -result : double_then_increment 5; -/* Result: 11 (5*2=10, then 10+1=11) */ - -/* Complex composition chain */ -double_then_increment : compose @increment @double; -process_number : compose @double_then_increment @square; -result : process_number 3; -/* Result: 19 (3^2=9, 9*2=18, 18+1=19) */ - -/* Composition with different types */ -add_exclamation : x -> x + "!"; -format_number : compose @add_exclamation @double; -result : format_number 5; -/* Result: "10!" */ -``` - -### Pipe: Left-to-Right Composition - -`pipe` is the opposite of `compose` - it flows left to right: - -```plaintext -/* Pipeline style: f then g */ -increment_then_double : pipe @increment @double; -result : increment_then_double 5; -/* Result: 12 (5+1=6, then 6*2=12) */ - -/* Data processing pipeline */ -data : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; -is_even : x -> x % 2 = 0; -double : x -> x * 2; -sum : x -> reduce @add 0 x; - -/* Pipeline: filter -> map -> reduce */ -filter_evens : filter @is_even; -double_evens : map @double; -sum_all : reduce @add 0; -process_pipeline : pipe @sum_all @double_evens @filter_evens; -result : process_pipeline data; -/* Result: 60 (filter evens: {2,4,6,8,10}, double: {4,8,12,16,20}, sum: 60) */ -``` - -### Via: Natural Composition Syntax - -The `via` operator provides a more natural composition syntax: - -```plaintext -/* Using via for composition */ -double : x -> x * 2; -increment : x -> x + 1; -square : x -> x * x; - -/* Natural reading: double via increment via square */ -complex_transform : double via increment via square; -result : complex_transform 3; -/* Result: 19 (3^2=9, 9+1=10, 10*2=20) */ - -/* Via with multiple functions */ -format_pipeline : double via increment via square; -result : format_pipeline 2; -/* Result: 10 (2^2=4, 4+1=5, 5*2=10) */ -``` - -#### Understanding the `via` Operator - -The `via` operator is a **right-associative function composition operator** that translates to `compose` calls: - -```plaintext -/* Translation examples */ -f via g → compose(f, g) -f via g via h → compose(f, compose(g, h)) -f via g via h via i → compose(f, compose(g, compose(h, i))) -``` - -#### Right-Associative Behavior - -The `via` operator is **right-associative**, meaning it groups from right to left: - -```plaintext -/* Right-associative grouping */ -double via increment via square - -/* Groups as: */ -double via (increment via square) - -/* Which translates to: */ -compose(double, compose(increment, square)) - -/* Execution order: square → increment → double */ -``` - -This matches mathematical function composition notation where `(f ∘ g ∘ h)(x) = f(g(h(x)))`. - -#### Precedence Rules - -The `via` operator has **higher precedence** than function application: - -```plaintext -/* via binds tighter than function application */ -double via increment 5 - -/* This is parsed as: */ -(double via increment) 5 - -/* NOT as: */ -double via (increment 5) -``` - -#### Comparison with Other Composition Methods - -```plaintext -/* Three ways to compose functions */ - -/* 1. via operator (natural syntax) */ -result1 : double via increment via square 3; -/* Result: 20 (3^2=9, 9+1=10, 10*2=20) */ - -/* 2. compose function (mathematical style) */ -double_then_increment : compose @increment @double; -complex_transform : compose @double_then_increment @square; -result2 : complex_transform 3; -/* Result: 19 (3^2=9, 9*2=18, 18+1=19) */ - -/* 3. pipe function (pipeline style) */ -square_then_double : pipe @square @double; -pipeline_transform : pipe @square_then_double @increment; -result3 : pipeline_transform 3; -/* Result: 19 (3^2=9, 9*2=18, 18+1=19) */ -``` - -#### When to Use `via` - -Use the `via` operator when you want: - -1. **Natural reading**: `f via g via h` reads as "f then g then h" -2. **Mathematical notation**: Matches `(f ∘ g ∘ h)` notation -3. **Concise syntax**: Shorter than nested `compose` calls -4. **Right-to-left flow**: When you think of data flowing right to left - -```plaintext -/* Good use cases for via */ - -/* Data transformation pipeline */ -process_data : filter @is_even via map @double via reduce @add 0; -result : process_data {1, 2, 3, 4, 5, 6}; -/* Reads: filter evens, then double each, then sum all */ - -/* String processing pipeline */ -format_text : to_upper via trim via replace_spaces; -result : format_text " hello world "; -/* Reads: replace spaces, then trim, then uppercase */ - -/* Mathematical composition */ -complex_math : square via double via increment; -result : complex_math 3; -/* Reads: increment, then double, then square */ -``` - -#### Common Patterns - -```plaintext -/* Pattern 1: Data processing pipeline */ -data : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; -is_even : x -> x % 2 = 0; -double : x -> x * 2; -sum : x -> reduce @add 0 x; - -/* Pipeline: filter → map → reduce */ -process_pipeline : sum via map @double via filter @is_even; -result : process_pipeline data; -/* Result: 60 (filter evens: {2,4,6,8,10}, double: {4,8,12,16,20}, sum: 60) */ - -/* Pattern 2: Validation chain */ -validate_name : user -> user.name != ""; -validate_age : user -> user.age > 0; -validate_email : user -> user.email.contains "@"; - -/* Chain validations */ -all_validations : validate_email via validate_age via validate_name; -result : all_validations {name: "Alice", age: 25, email: "alice@test.com"}; -/* Result: true (all validations pass) */ - -/* Pattern 3: Formatting pipeline */ -to_upper : x -> x.toUpperCase(); -add_prefix : prefix -> x -> prefix + ": " + x; -format_label : add_prefix "Name" via to_upper; -result : format_label "alice"; -/* Result: "Name: ALICE" */ -``` - -#### Debugging `via` Chains - -```plaintext -/* Add tracing to understand execution order */ -trace : name value -> { - ..out "[" + name + "]: " + value; - value -}; - -/* Trace each step in the pipeline */ -traced_pipeline : trace "final" via trace "double" via trace "filter" via trace "input"; -result : traced_pipeline {1, 2, 3, 4, 5}; -/* Output: [input]: {1,2,3,4,5}, [filter]: {2,4}, [double]: {4,8}, [final]: 12 */ -``` - -#### Best Practices - -1. **Use `via` for natural reading**: When you want `f via g via h` to read as "f then g then h" -2. **Use `compose` for mathematical style**: When you want explicit mathematical notation -3. **Use `pipe` for pipeline style**: When you want left-to-right data flow -4. **Keep chains readable**: Break long chains into named intermediate functions -5. **Consider precedence**: Remember that `via` binds tighter than function application - -```plaintext -/* Good: Clear and readable */ -process_data : sum via map @double via filter @is_even; - -/* Better: Named intermediate steps */ -filter_evens : filter @is_even; -double_values : map @double; -sum_all : reduce @add 0; -process_data : sum_all via double_values via filter_evens; -``` - -### Advanced Composition Patterns - -Complex composition chains can also be built using nested `compose` and `pipe`: - -```plaintext -/* Mathematical style: g then f then h */ -double_then_increment : compose @increment @double; -complex_transform : compose @double_then_increment @square; -result : complex_transform 3; -/* Result: 19 (3^2=9, 9*2=18, 18+1=19) */ - -/* Pipeline style: f then g then h */ -square_then_double : pipe @square @double; -pipeline_transform : pipe @square_then_double @increment; -result : pipeline_transform 3; -/* Result: 19 (3^2=9, 9*2=18, 18+1=19) */ -``` - -## Each: Multi-Argument Element-Wise Operations - -`each` is designed for combining multiple collections element-wise: - -```plaintext -/* Element-wise addition */ -table1 : {a: 1, b: 2, c: 3}; -table2 : {a: 10, b: 20, c: 30}; -sum : each @add table1 table2; -/* Result: {a: 11, b: 22, c: 33} */ - -/* Adding scalar to each element */ -numbers : {1, 2, 3, 4, 5}; -incremented : each @add numbers 10; -/* Result: {11, 12, 13, 14, 15} */ - -/* Complex element-wise operations */ -people : { - alice: {name: "Alice", age: 25}, - bob: {name: "Bob", age: 30} -}; -bonuses : { - alice: 1000, - bob: 1500 -}; -add_bonus : person bonus -> { - name: person.name, - age: person.age, - salary: person.age * 1000 + bonus -}; -with_bonuses : each @add_bonus people bonuses; -/* Result: {alice: {name: "Alice", age: 25, salary: 26000}, ...} */ -``` - -## Problem-Solving Patterns - -### Pattern 1: Data Transformation Pipeline - -Transform data through multiple stages: - -```plaintext -/* Problem: Process a list of numbers */ -/* 1. Filter out negative numbers */ -/* 2. Double each remaining number */ -/* 3. Sum all results */ - -data : {-3, -1, 0, 2, 4, 6, -2, 8}; - -/* Step-by-step approach */ -is_positive : x -> x > 0; -double : x -> x * 2; -sum : x -> reduce @add 0 x; - -positive : filter @is_positive data; -doubled : map @double positive; -total : sum doubled; - -/* Or as a composition */ -process_data : compose @sum @map @double @filter @is_positive; -total : process_data data; -/* Result: 40 (positive: {2,4,6,8}, doubled: {4,8,12,16}, sum: 40) */ -``` - -### Pattern 2: Table Aggregation - -Extract and aggregate data from complex structures: - -```plaintext -/* Problem: Calculate average salary by department */ -employees : { - alice: {name: "Alice", dept: "Engineering", salary: 80000}, - bob: {name: "Bob", dept: "Sales", salary: 60000}, - charlie: {name: "Charlie", dept: "Engineering", salary: 90000}, - diana: {name: "Diana", dept: "Sales", salary: 65000}, - eve: {name: "Eve", dept: "Engineering", salary: 85000} -}; - -/* Extract department and salary */ -get_dept_salary : emp -> {dept: emp.dept, salary: emp.salary}; -dept_salaries : map @get_dept_salary employees; - -/* Group by department (simplified) */ -engineering : filter @is_engineering dept_salaries; -sales : filter @is_sales dept_salaries; - -is_engineering : entry -> entry.dept = "Engineering"; -is_sales : entry -> entry.sales = "Sales"; - -/* Calculate averages */ -get_salary : entry -> entry.salary; -eng_salaries : map @get_salary engineering; -sales_salaries : map @get_salary sales; -eng_total : reduce @add 0 eng_salaries; -sales_total : reduce @add 0 sales_salaries; -/* Note: Division would require additional arithmetic functions */ -``` - -### Pattern 3: Conditional Transformation - -Apply different transformations based on conditions: - -```plaintext -/* Problem: Format different types of data */ -data : { - user1: {type: "admin", name: "Alice", level: 5}, - user2: {type: "user", name: "Bob", level: 2}, - user3: {type: "guest", name: "Charlie", level: 1} -}; - -/* Define transformation based on type */ -format_user : user -> - when user.type is - "admin" then { - display: "👑 " + user.name, - access: "full", - level: user.level * 10 - } - "user" then { - display: "👤 " + user.name, - access: "limited", - level: user.level * 5 - } - _ then { - display: "👻 " + user.name, - access: "readonly", - level: 1 - }; - -/* Apply transformation to all users */ -formatted : map @format_user data; -``` - -### Pattern 4: Recursive Combinators - -Build recursive patterns using combinators: - -```plaintext -/* Problem: Flatten nested tables */ -nested : { - level1: { - a: {value: 1}, - b: {value: 2} - }, - level2: { - c: {value: 3} - } -}; - -/* Recursive flattening function */ -flatten : table -> - when (t.has table "value") is - true then table - _ then reduce @t.merge {} (map @flatten_entry table); - -flatten_entry : entry -> - when (t.has entry "value") is - true then entry - _ then flatten entry; - -/* Apply flattening */ -flat : flatten nested; -/* Result: {a: {value: 1}, b: {value: 2}, c: {value: 3}} */ -``` - -## Advanced Combinator Patterns - -### Partial Application and Currying - -Create specialized functions from general ones: - -```plaintext -/* Basic partial application */ -add : x y -> x + y; -add_ten : add 10; -result : add_ten 5; -/* Result: 15 */ - -/* Complex partial application */ -format_with_prefix : prefix value -> prefix + ": " + value; -format_name : format_with_prefix "Name"; -format_age : format_with_prefix "Age"; - -person : {name: "Alice", age: 30}; -formatted_name : format_name person.name; -formatted_age : format_age person.age; -/* Results: "Name: Alice", "Age: 30" */ - -/* Currying with combinators */ -multiply_by : x y -> x * y; -double : multiply_by 2; -triple : multiply_by 3; - -numbers : {1, 2, 3, 4, 5}; -doubled : map @double numbers; -tripled : map @triple numbers; -``` - -### Higher-Order Combinators - -Combinators that work with other combinators: - -```plaintext -/* Apply a combinator to multiple collections */ -apply_to_all : combinator collections -> - reduce @t.merge {} (map @combinator collections); - -/* Example usage */ -add_one : x -> x + 1; -collections : {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; -all_incremented : apply_to_all @map @add_one collections; - -/* Compose multiple functions */ -compose_many : functions -> - reduce @compose @identity functions; - -/* Example usage */ -double_then_increment : compose @increment @double; -complex_transform : compose @double_then_increment @square; -result : complex_transform 3; -/* Result: 19 (3^2=9, 9*2=18, 18+1=19) */ -``` - -### Memoization Pattern - -Cache function results for performance: - -```plaintext -/* Simple memoization */ -memoize : f -> { - cache: {}, - compute: x -> - when (t.has cache x) is - true then t.get cache x "not_found" - _ then { - result: f x, - new_cache: t.set cache x (f x) - } -}; - -/* Using memoized function */ -expensive_calc : x -> { - /* Simulate expensive computation */ - x * x * x -}; - -memoized_calc : memoize @expensive_calc; -result1 : memoized_calc.compute 5; -result2 : memoized_calc.compute 5; /* Uses cached result */ -``` - -## Real-World Problem Solving - -### Example 1: E-commerce Order Processing - -```plaintext -/* Process customer orders */ -orders : { - order1: {customer: "Alice", items: {book: 2, pen: 5}, status: "pending"}, - order2: {customer: "Bob", items: {laptop: 1}, status: "shipped"}, - order3: {customer: "Charlie", items: {book: 1, pen: 3}, status: "pending"} -}; - -prices : {book: 15, pen: 2, laptop: 800}; - -/* Calculate order totals */ -calculate_total : order -> { - customer: order.customer, - total: reduce @add 0 (map @calculate_item_total order.items), - status: order.status -}; - -calculate_item_total : item quantity -> - when item is - "book" then 15 * quantity - "pen" then 2 * quantity - "laptop" then 800 * quantity - _ then 0; - -/* Process all orders */ -processed_orders : map @calculate_total orders; - -/* Filter pending orders */ -is_pending : order -> order.status = "pending"; -pending_orders : filter @is_pending processed_orders; - -/* Get total revenue from pending orders */ -get_total : order -> order.total; -total_revenue : reduce @add 0 (map @get_total pending_orders); -``` - -### Example 2: Data Validation Pipeline - -```plaintext -/* Validate user input data */ -users : { - user1: {name: "Alice", email: "alice@example.com", age: 25}, - user2: {name: "", email: "invalid-email", age: -5}, - user3: {name: "Charlie", email: "charlie@test.com", age: 30} -}; - -/* Simple validation example */ -is_valid_name : user -> - when user.name = "" is - true then false - _ then true; - -is_valid_age : user -> - when user.age > 0 is - true then true - _ then false; - -/* Apply validation to all users */ -valid_names : map @is_valid_name users; -valid_ages : map @is_valid_age users; -``` - -## Performance Considerations - -### Lazy Evaluation Patterns - -```plaintext -/* Process large datasets efficiently */ -large_dataset : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; - -/* Process in chunks */ -chunk_size : 3; -process_chunk : chunk -> map @double chunk; - -/* Process data in smaller batches */ -batch1 : {1, 2, 3}; -batch2 : {4, 5, 6}; -batch3 : {7, 8, 9, 10}; - -processed_batch1 : process_chunk batch1; -processed_batch2 : process_chunk batch2; -processed_batch3 : process_chunk batch3; -/* Combine results manually since we don't have array operations */ -``` - -### Memory-Efficient Patterns - -```plaintext -/* Stream processing pattern */ -stream_process : data -> - compose @reduce @add 0 @map @double @filter @is_even data; - -/* This processes each element once through the pipeline */ -/* No intermediate results are stored */ -``` - -## Debugging Combinator Chains - -### Tracing Function Applications - -```plaintext -/* Add tracing to functions */ -trace : name value -> { - ..out "[" + name + "]: " + value; - value -}; - -/* Use in composition */ -traced_double : compose @trace "double" @double; -traced_increment : compose @trace "increment" @increment; -traced_square : compose @trace "square" @square; - -/* Trace the entire pipeline */ -traced_pipeline : compose @traced_increment @traced_double @traced_square; -result : traced_pipeline 3; -/* Output: [square]: 9, [double]: 18, [increment]: 19 */ -``` - -### Visualizing Data Flow - -```plaintext -/* Create visualization of data transformations */ -visualize_step : step_name data -> { - ..out "=== " + step_name + " ==="; - ..out "Input: " + data; - result: data -}; - -/* Use in pipeline */ -visualized_pipeline : compose - @visualize_step "Final Result" - @map @double - @visualize_step "After Filter" - @filter @is_even - @visualize_step "Initial Data"; - -result : visualized_pipeline {1, 2, 3, 4, 5, 6}; -``` - -## Best Practices Summary - -### 1. Think in Transformations -```plaintext -/* Instead of: "Loop through and modify" */ -/* Think: "Transform this into that" */ -``` - -### 2. Compose, Don't Nest -```plaintext -/* Good: Clear composition */ -pipeline : compose @step3 @step2 @step1; - -/* Avoid: Deep nesting */ -result : step3(step2(step1(data))); -``` - -### 3. Use Partial Application -```plaintext -/* Create specialized functions */ -specialized : general_function specific_value; -``` - -### 4. Leverage Immutability -```plaintext -/* Always return new data, never modify existing */ -new_data : transform_function old_data; -``` - -### 5. Build Reusable Patterns -```plaintext -/* Create patterns you can reuse */ -validation_pipeline : compose @validate3 @validate2 @validate1; -``` - -## Next Steps - -You now have a deep understanding of combinators and functional problem-solving! To continue your journey: - -1. **Practice**: Try implementing the examples above -2. **Experiment**: Create your own combinator patterns -3. **Optimize**: Look for opportunities to compose functions -4. **Extend**: Build your own specialized combinators -5. **Share**: Document patterns you discover - -The power of combinators comes from their composability. Start simple, build up complexity through composition, and always think in terms of data transformations rather than step-by-step instructions. \ No newline at end of file |