Functional Programming in hica

# Functional Programming in hica - hica Source: [https://www.hica.dev/docs/functional-programming/](https://www.hica.dev/docs/functional-programming/) Functional programming \(FP\) is a style where you build programs by composing functions rather than by writing sequences of instructions that change state\. hica is designed around this style: immutable data, expressions everywhere, and functions as first\-class values\. All examples are runnable\. You don’t need a background in FP; if you can write a function and read a match expression, you have enough\. ## Expressions, not statements In most languages, statements*do things*and expressions*produce values*\. In hica, almost everything is an expression, including`if`,`match`, and blocks\. That means you can use them anywhere a value is expected: ``` fun sign(x) => if x < 0 { "negative" } else { "non-negative" } ``` The body of a`\{\}`block is the value of its last expression\. No`return`keyword: ``` fun clamp(x, lo, hi) { if x < lo { lo } else if x > hi { hi } else { x } } ``` This single rule carries you through most of FP: when everything has a value, everything can be composed\. ## Immutability by default FP avoids shared mutable state\. When you can’t change a value after creating it, your functions are easier to reason about and test\. hica uses`let`for immutable bindings: ``` let name = "Alicia" let scores = [85, 92, 78] ``` You never mutate`scores`in place\. Instead, you create new lists: ``` let updated = scores + [95] // new list: [85, 92, 78, 95] let doubled = map(scores, (x) => x * 2) ``` When you need mutation \(a counter, a loop variable\), use`var`\. It’s locally scoped and can’t leak out of the function: ``` var total = 0 for x in scores { total = total + x } ``` `var`is opt\-in\. Everything else stays immutable\. ## Pure functions A*pure function*always returns the same output for the same input and has no side effects \(no printing, no file I/O, no mutable state\)\. Pure functions are easy to test and compose\. ``` fun add(a, b) => a + b fun square(x) => x * x fun to_celsius(f: float) => (f - 32.0) * 5.0 / 9.0 ``` In hica, functions are pure by default\. The type system \(inherited from Koka\) tracks effects like I/O, so when a function*does*have a side effect, that’s visible in its type\. Pure functions are what you build with\. Everything else is composition\. ## Functions as first\-class values In FP, functions are values like integers or strings\. You can store them in variables, pass them to other functions, and return them from functions\. ``` fun apply(f, x: int) => f(x) fun main() { let double = (x) => x * 2 let greet = (name) => "Hello, " + name println(apply(double, 5)) // 10 println(greet("Olle")) // Hello, Olle } ``` A function that takes or returns another function is called a*higher\-order function*\.`apply`above is one\. ## Closures A*closure*is a function that captures variables from its surrounding scope: ``` fun make_adder(n) => (x) => x + n fun main() { let add5 = make_adder(5) let add10 = make_adder(10) println(add5(3)) // 8 println(add10(3)) // 13 } ``` `make\_adder`returns a new function each time\. That function*closes over*`n`, meaning it remembers the value of`n`from when it was created, even after`make\_adder`has returned\. This pattern lets you stamp out specialised functions on demand: ``` fun make_multiplier(factor) => (x) => x * factor fun main() { let triple = make_multiplier(3) let nums = [1..5] println(map(nums, triple)) // [3, 6, 9, 12, 15] } ``` ## map, filter, fold These three functions cover most of what you need for working with lists\. ### map: transform every element ``` fun main() { let nums = [1..5] println(map(nums, (x) => x * x)) // [1, 4, 9, 16, 25] println(map(nums, show)) // ["1", "2", "3", "4", "5"] } ``` `map`takes a list and a function\. It applies the function to each element and returns a new list of the same length\. ### filter: keep matching elements ``` fun main() { let nums = [1..8] let evens = filter(nums, (x) => x % 2 == 0) println(evens) // [2, 4, 6, 8] } ``` `filter`keeps only the elements for which the predicate returns`true`\. ### fold: reduce to a single value ``` fun main() { let nums = [1..5] let total = fold(nums, 0, (acc, x) => acc + x) println(total) // 15 let product = fold(nums, 1, (acc, x) => acc * x) println(product) // 120 } ``` `fold`accumulates a result\. It starts with an initial value and applies the function to each element in turn:`acc`holds the running result,`x`is the current element\. You can implement many list operations with fold: ``` fun my_length(xs) => fold(xs, 0, (acc, _) => acc + 1) fun my_max(xs) => fold(xs, 0, (acc, x) => if x > acc { x } else { acc }) fun my_reverse(xs) => fold(xs, [], (acc, x) => [x] + acc) ``` ## flatten and flat\_map `map`transforms every element\. But sometimes the function you pass to`map`itself returns a list\. The result is a list of lists, which is usually not what you want: ``` fun main() { let sentences = ["hello world", "foo bar", "one two three"] let split_words = map(sentences, (s) => split(s, " ")) println(split_words) // [["hello", "world"], ["foo", "bar"], ["one", "two", "three"]] } ``` You wanted a flat list of all words\. Two functions solve this\. ### concat: collapse one level of nesting ``` fun main() { let nested = [[1, 2], [3, 4], [5, 6]] println(concat(nested)) // [1, 2, 3, 4, 5, 6] } ``` `concat`takes a list of lists and collapses one level\. \(Other languages call this`flatten`\.\) ### flat\_map: map and flatten in one step `flat\_map`applies a function to each element and joins all the resulting lists together\. It is`map`followed by`concat`, but written as one step: ``` fun main() { let sentences = ["hello world", "foo bar", "one two three"] let all_words = flat_map(sentences, (s) => split(s, " ")) println(all_words) // ["hello", "world", "foo", "bar", "one", "two", "three"] } ``` You reach for`flat\_map`whenever the function you are mapping returns a list\. ### Expanding elements in a pipe `flat\_map`fits naturally in a pipe\. Use it at the step where a single element becomes multiple elements: ``` fun expand(n) => [n, n * 10] // each element fans out to two fun main() { let result = [1, 2, 3] |> flat_map(expand) // [1, 10, 2, 20, 3, 30] |> filter((x) => x > 5) // [10, 20, 30] println(result) } ``` Without`flat\_map`you would get`\[\[1, 10\], \[2, 20\], \[3, 30\]\]`and`filter`would be operating on lists, not numbers\. ### The same idea applies to Maybe The pattern:*apply a function that produces a wrapped value, then flatten the wrapping*, appears with Maybe too\.`map\_maybe`transforms the value inside a`Maybe`\. But if the function itself returns`Maybe`, you’d end up with`Maybe<Maybe<x\>\>`\.`and\_then`prevents that by flattening the extra layer automatically: ``` fun parse_pos(s: string) : maybe<int> { let n = parse_int(s)? if n > 0 { Some(n) } else { None } } fun main() { // and_then chains steps that each return Maybe — no nesting, no nested match let result = Some("42") |> and_then((s) => parse_int(s)) // parse string → maybe<int> |> and_then((n) => parse_pos(show(n))) |> map_maybe((n) => n * 2) println(result) // Some(84) let bad = Some("-5") |> and_then((s) => parse_int(s)) |> and_then((n) => parse_pos(show(n))) |> map_maybe((n) => n * 2) println(bad) // None } ``` `flat\_map`for lists and`and\_then`for Maybe are the same idea with different names\. Functional programmers call this operation*bind*\. Knowing the pattern: “map over a wrapped value with a function that itself returns a wrapped value, and don’t double\-wrap”, is the thing to take away, whatever the type\. ## Composition with \|\> The pipe operator`\|\>`feeds the result of one expression into the next function\. It reads left to right, matching the order of operations: ``` fun main() { let result = [1..10] |> filter((x) => x % 2 == 0) // [2, 4, 6, 8, 10] |> map((x) => x * x) // [4, 16, 36, 64, 100] |> fold(0, (acc, x) => acc + x) // 220 println(result) } ``` Without`\|\>`you’d write: ``` let result = fold(map(filter([1..10], (x) => x % 2 == 0), (x) => x * x), 0, (acc, x) => acc + x) ``` With`\|\>`, each step is on its own line and you read the transformation in the order it happens\. That’s the point: each step is one function, and they chain\. ### Point\-free style When a lambda just passes its argument directly to a function, you can drop the lambda entirely: ``` fun is_even(x) => x % 2 == 0 fun square(x) => x * x fun main() { let result = [1..5] |> filter(is_even) // same as filter(nums, (x) => is_even(x)) |> map(square) println(result) // [4, 16] } ``` This style \(naming the function rather than wrapping it in a lambda\) is called*point\-free*\. Use it when the name says more than the lambda would\. ## Recursion FP uses recursion where imperative code uses loops\. A recursive function calls itself with a smaller input until it hits a base case: ``` fun sum(xs) => match xs { [] => 0, [x, ..rest] => x + sum(rest) } fun main() { println(sum([1..5])) // 15 } ``` The`\[x, \.\.rest\]`pattern splits a list into its first element and the rest\. This pairs naturally with recursion: ``` fun contains(xs, target) => match xs { [] => false, [x, ..rest] => x == target || contains(rest, target) } fun map_r(xs, f) => match xs { [] => [], [x, ..rest] => [f(x)] + map_r(rest, f) } ``` For mutual recursion \(two functions that call each other\), no forward declarations are needed: ``` fun is_even(n) => if n == 0 { true } else { is_odd(n - 1) } fun is_odd(n) => if n == 0 { false } else { is_even(n - 1) } ``` In practice you’ll use`map`/`filter`/`fold`far more than explicit recursion, but recursion is the right tool for tree\-shaped data, and knowing it helps you read other people’s code\. ## Algebraic data types Functional programming uses*algebraic data types*\(ADTs\) to model data that comes in different shapes\. hica has two kinds\. ### Structs: product types A struct bundles fields together: ``` struct Point { x: int, y: int } struct Person { name: string, age: int } fun greet(p: Person) => "Hi, {p.name}!" fun distance(a: Point, b: Point) : int { let dx = a.x - b.x let dy = a.y - b.y dx * dx + dy * dy } ``` Structs are immutable\. To “update” a field, create a new struct: ``` struct Player { name: string, score: int } fun add_score(p: Player, points: int) : Player => Player { name: p.name, score: p.score + points } ``` ### Enums: sum types An enum represents a choice between distinct variants, each of which can carry its own data: ``` type Shape { Circle(radius: float), Rect(width: float, height: float), Point } fun area(s: Shape) : float => match s { Circle(r) => 3.14159 * r * r, Rect(w, h) => w * h, Point => 0.0 } ``` The compiler checks exhaustiveness: if you forget a variant, you get a warning\. This makes adding new variants safe; the compiler tells you every place that needs updating\. Enums can be recursive, which is how you model tree\-shaped data: ``` type Tree { Leaf, Node(value: int, left: Tree, right: Tree) } fun tree_sum(t: Tree) : int => match t { Leaf => 0, Node(v, l, r) => v + tree_sum(l) + tree_sum(r) } ``` ## Maybe and Result Two built\-in types handle failure without exceptions\. ### Maybe: a value that might not exist ``` fun find_first(xs, pred) => match xs { [] => None, [x, ..rest] => if pred(x) { Some(x) } else { find_first(rest, pred) } } fun main() { let nums = [1, 3, 5, 4, 7] match find_first(nums, (x) => x % 2 == 0) { Some(n) => println("First even: {n}"), None => println("No evens found") } } ``` `Some\(x\)`wraps a value;`None`signals absence\. The compiler forces you to handle both cases\. ### Chaining with combinators Nested`match`for every step gets unwieldy fast\. Combinators keep the chain flat\. There is also a subtlety: when the function you want to apply itself returns`Maybe`, using`map\_maybe`would give you`Maybe<Maybe<x\>\>`\.`and\_then`prevents the double\-wrapping by flattening one level, the same job`flat\_map`does for lists: ``` fun main() { // map_maybe transforms the value inside, leaves None alone let x = Some(21) |> map_maybe((n) => n * 2) println(x) // Some(42) // and_then chains a function that itself returns Maybe let y = Some("42") |> and_then((s) => parse_int(s)) |> map_maybe((n) => n + 1) println(y) // Some(43) // Short-circuits at the first None let z = Some("nope") |> and_then((s) => parse_int(s)) |> map_maybe((n) => n + 1) println(z) // None } ``` ### Result: success or a specific error `Result`carries an error message on failure: ``` fun safe_divide(a, b) => if b == 0 { Err("division by zero") } else { Ok(a / b) } fun validate_positive(n) => if n > 0 { Ok(n) } else { Err("must be positive") } fun main() { let result = safe_divide(100, 4) |> and_then_result((n) => validate_positive(n)) |> map_result((n) => n * 2) println(result) // Ok(50) let bad = safe_divide(100, 0) |> and_then_result((n) => validate_positive(n)) println(bad) // Err("division by zero") } ``` ### The ? operator For functions that chain many fallible steps,`?`keeps the code flat\. It returns early with`None`or`Err`if a step fails: ``` fun add_strings(a: string, b: string) : maybe<int> { let x = parse_int(a)? let y = parse_int(b)? Some(x + y) } fun main() { println(add_strings("10", "32")) // Some(42) println(add_strings("10", "oops")) // None } ``` Three constraints to know: - The**return type annotation is required**on the enclosing function: the compiler needs it to emit the early return correctly\. - The wrapper type must match:`?`on`maybe`only works inside a`maybe`\-returning function, and`?`on`result`only inside a`result`\-returning function\. - `?`**cannot be used in`main\(\)`**:`main\(\)`returns`\(\)`\. Move fallible logic into a helper and call it from`main\(\)`with`match`\. ## Putting it together A program that pulls it all together: structs, pure functions, closures, pipe, pattern matching, and`maybe`\. ``` struct Student { name: string, grade: int } fun letter_grade(g: int) : string => match g { 90..=100 => "A", 80..=89 => "B", 70..=79 => "C", 60..=69 => "D", _ => "F" } fun passing(s: Student) : bool => s.grade >= 60 fun summarise(students: list<Student>) { let passing_students = filter(students, passing) let names = map(passing_students, (s) => s.name) let avg = fold(passing_students, 0, (acc, s) => acc + s.grade) / length(passing_students) println("Passing: {join(names, ", ")}") println("Average grade (passing): {avg}") println("Letter grade: {letter_grade(avg)}") } fun main() { let students = [ Student { name: "Alicia", grade: 92 }, Student { name: "Björn", grade: 55 }, Student { name: "Cecilia", grade: 78 }, Student { name: "David", grade: 61 } ] summarise(students) } ``` Output: ``` Passing: Alicia, Cecilia, David Average grade (passing): 77 Letter grade: C ``` ## Key ideas to take with you ConcepthicaImmutable data`let`by default,`var`when you need itFirst\-class functions`\(x\) =\> x \* 2`,`fun add\(a, b\) =\> a \+ b`Closures`fun make\_adder\(n\) =\> \(x\) =\> x \+ n`Composition`\\\|\>`pipe operatorTransforming lists`map`,`filter`,`fold`Flattening / expanding`concat`\(flatten\),`flat\_map`\(map \+ flatten\)Chaining wrapped values`and\_then`\(Maybe\),`and\_then\_result`\(Result\), same idea as`flat\_map`Recursive data`type Tree \{ Leaf, Node\(\.\.\.\) \}`Safe failures`Maybe`\(`Some`/`None`\) and`Result`\(`Ok`/`Err`\)Exhaustive matching`match`with compiler\-checked variantsThe point isn’t to avoid loops\. It’s that small functions composed together tend to be easier to test, name, and reuse\. hica’s design makes that the natural default\.