Functional Programming in hica

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 { "positive" } else { "negative" }

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<T>>. 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<T>>. 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

| Concept | hica |
|---|---|
| Immutable data | let by default, var when you need it |
| First-class functions | Functions are values - store, pass, return them |
| Pure by default | Functions are pure; effects are tracked in the type |
| Composition | |> chains transformations left to right |
| Pattern matching | Destructure and exhaustively check variants |
| No null | Maybe and Result handle absence and errors |
| Algebraic data types | struct for products, enum for sums |