Flix Series Part 1: Higher-order functions & infix combinators

A higher order function is a function that takes one or more functions as arguments, or returns a function as its result. Higher order functions are an important concept in functional programming, as they allow for the creation of more abstract and flexible code.

Here is an example of a higher order function in Scala:

def applyTwice(f: Int => Int, x: Int): Int = f(f(x))

This function takes a function f and an integer x as arguments, and applies f to x and then applies f to the result. The function f must take an integer as an argument and return an integer.

Higher order functions abstract over common patterns in code, such as looping and mapping over collections. They also construct more complex functions from simpler functions without uncomposeable and "glue" or brittle boilerplate code like you might see in a more procedural language like Go with its infamous inline error handling.

Higher order functions (HOFs) are useful because they allow for the creation of more abstract and flexible code via parametric polymorphism. They allow programmers to write code that is more general and reusable, as well as easier to understand and maintain.

For example, the above applyTwice higher-order function works for any function f that takes any type A and produces a value of the same type. Let us see how we would do this in Scala:

def applyTwicePoly[A](f: A => A, x: A): A = f(f(x))

The definition of the function remains the same (f(f(x))) but the type signature abstracts away the concrete types with an [A] parameter.

There are many commonly used higher order functions in functional programming that are useful for a variety of tasks. Here are a few examples:

map

The map function applies a given function to each element in a collection and returns a new collection with the results.

filter

The filter function selects elements from a collection that meet a certain criteria, and returns a new collection with only the selected elements. This is a useful function for selecting specific items from a collection. The caller passes in a function that takes each element from the list and returns a boolean answer for each one. Again this function gets included in most standard library collection types.

reduce

The reduce function combines all the elements in a collection into a single value by applying a given function to each element in turn. This is a useful function for performing operations such as summing the elements in a collection.

compose

The compose function takes two functions as arguments and returns a new function that is the composition of the two given. This is a useful function for combining smaller functions into larger, more complex ones.

curry

The curry function takes a function with multiple arguments and returns a new function that is called with the arguments one at a time. This is a useful function for creating more flexible functions that can be partially applied. Sometimes you just need to defer computing the end arguments until later.

flip

The flip function takes a function that takes two arguments and returns a new function that flips the order of the arguments. This is useful when used in conjunction with other higher-order functions like curry from above.

There are many more, and the specific functions that are most useful will depend on the needs of the particular software application being written.

Overall, higher-order functions are a powerful tool in functional programming that can help programmers write more concise, flexible, and reusable code.

In Flix, we would write both of these functions like so:

def applyTwice(f: Int32 -> Int32, x: Int32): Int32 = f(f(x))
def applyTwicePoly[a: Type](f: a -> a, x: a): a = f(f(x))

Only minor differences exist, namely:

• syntax: inline function definitions use -> instead of the "fat arrow" syntax as in Scala
• syntax: type parameter kind is provided via Type in Flix
• primitives: integer types are split into sized variants so we are using Int32 in Flix instead of Int

// The sum type from the prior blog post
// to refresh our memory
enum Expr:
  case Lit(value: Int)
  case Add(left: Expr, right: Expr)
  case Sub(left: Expr, right: Expr)
  case Mul(left: Expr, right: Expr)
  case Div(left: Expr, right: Expr)

// Also defined in prior blog post
def eval(expr: Expr): Int =
  expr match
    case Expr.Lit(value)       => value
    case Expr.Add(left, right) => eval(left) + eval(right)
    case Expr.Sub(left, right) => eval(left) - eval(right)
    case Expr.Mul(left, right) => eval(left) * eval(right)
    case Expr.Div(left, right) => eval(left) / eval(right)

// This is the extension mechanism to add
// symbolic infix custom operators for API
// (Scala 3 only)
extension (left: Expr)
  def +(right: Expr): Expr = Expr.Add(left, right)
  def -(right: Expr): Expr = Expr.Sub(left, right)
  def *(right: Expr): Expr = Expr.Mul(left, right)
  def /(right: Expr): Expr = Expr.Div(left, right)

object Expr:
  def lit(value: Int): Expr = Expr.Lit(value)

val expr1: Expr = Expr.Add(Expr.Mul(Expr.lit(3), Expr.lit(2)), Expr.lit(5))
val expr2: Expr = Expr.Mul(Expr.Sub(Expr.lit(4), Expr.lit(1)), Expr.lit(9))
val expr3: Expr = (Expr.lit(4) - Expr.lit(1)) * Expr.lit(9)
val expr4: Expr = (Expr.lit(4) + Expr.lit(1)) / Expr.lit(5)

extension (left: Expr)
  def plus(right: Expr): Expr  = Expr.Add(left, right)
  def minus(right: Expr): Expr = Expr.Sub(left, right)
  def times(right: Expr): Expr = Expr.Mul(left, right)
  def over(right: Expr): Expr  = Expr.Div(left, right)

val expr5: Expr = Expr.lit(1) plus (Expr.lit(2) times Expr.lit(5))

  pub def +(left: Expr, right: Expr): Expr = Expr.Add(left, right)

>> Re-definition of reserved name '+'.

18 |   pub def +(left: Expr, right: Expr): Expr = Expr.Add(left, right)
               ^
               re-definition of a reserved name

instance Add[Expr] {
  pub def add(left: Expr, right: Expr): Expr =
    Expr.Add(left, right)
}
instance Sub[Expr] {
  pub def sub(left: Expr, right: Expr): Expr =
    Expr.Sub(left, right)
}
instance Mul[Expr] {
  pub def mul(left: Expr, right: Expr): Expr =
    Expr.Mul(left, right)
}
instance Div[Expr] {
  pub def div(left: Expr, right: Expr): Expr =
    Expr.Div(left, right)
}

def expr3(): Expr =
  (Expr.Val(4) - Expr.Val(1)) * Expr.Val(9)
def expr4(): Expr =
  (Expr.Val(4) + Expr.Val(1)) / Expr.Val(5)

@Test
def checkExpr3(): Bool = eval(expr3()) == 27

@Test
def checkExpr4(): Bool = eval(expr4()) == 1

> flix test
Found `flix.toml'. Checking dependencies...
Resolving Flix dependencies...
Downloading Flix dependencies...
Resolving Maven dependencies...
  Running Maven dependency resolver.
Downloading external jar dependencies...
Dependency resolution completed.
Running 9 tests...

   PASS  checkExpr1 2.6ms
   PASS  checkExpr2 183.8us
   PASS  checkExpr3 65.3us
   PASS  checkExpr4 57.6us
   PASS  testApplyNPoly 147.7us
   PASS  testApplyTwice01 57.4us
   PASS  testApplyTwice02 142.9us
   PASS  testApplyTwice03 64.0us
   PASS  testApplyTwicePoly01 94.9us

Passed: 9, Failed: 0. Skipped: 0. Elapsed: 8.1ms.

def lit(value: Int32): Expr =
  Expr.Lit(value)

def plus(left: Expr, right: Expr): Expr =
  Expr.Add(left, right)

def minus(left: Expr, right: Expr): Expr =
  Expr.Sub(left, right)

def times(left: Expr, right: Expr): Expr =
  Expr.Mul(left, right)

def over(left: Expr, right: Expr): Expr =
  Expr.Div(left, right)

def expr5() = lit(1) `plus` (lit(2) `times` lit(5)) // 11

>> Parse Error: Invalid input ") =", expected FormalParam or ':' (line 50, column 17):
  pub def expr5() = lit(1) `plus` (lit(2) `times` lit(5))

def expr5(): Expr = lit(1) `plus` (lit(2) `times` lit(5)) // 11

In this post, we explored two key aspects common to functional programming - higher-order functions and user-defined operators - in the Flix language comparing and contrasting it to Scala, the best known FP/OO hybrid language on the JVM.

We saw that Flix provides support for defining both monomorphic or polymorphic higher-order functions. The syntax is similar to Scala, while retaining familiarity for Java developers too. Flix does require type annotations which is different to Scala where types can often be inferred (especially return types of functions).

We also looked at how to create custom infix operators in Flix. Infix operators allow us to create embedded DSLs to model specific problem domains. Together both features enable writing compositional and expressive functional code.

While symbolic operators in Flix like + are reserved, we can leverage typeclasses like Add to get operator-style syntax. Non-symbolic operators can be used infix with backticks in Flix just like Scala's default behavior.

We've only scratched the surface of what's possible with Flix above. Stay tuned for future installments that will explore more of Flix.

Full source code for the Scala3 example is below:

enum Expr:
  case Lit(value: Int)
  case Add(left: Expr, right: Expr)
  case Sub(left: Expr, right: Expr)
  case Mul(left: Expr, right: Expr)
  case Div(left: Expr, right: Expr)

extension (left: Expr)
  def +(right: Expr): Expr = Expr.Add(left, right)
  def -(right: Expr): Expr = Expr.Sub(left, right)
  def *(right: Expr): Expr = Expr.Mul(left, right)
  def /(right: Expr): Expr = Expr.Div(left, right)


extension (left: Expr)
  def plus(right: Expr): Expr = Expr.Add(left, right)
  def minus(right: Expr): Expr = Expr.Sub(left, right)
  def times(right: Expr): Expr = Expr.Mul(left, right)
  def over(right: Expr): Expr = Expr.Div(left, right)

object Expr:
  def lit(value: Int): Expr = Expr.Lit(value)

def eval(expr: Expr): Int =
  expr match
    case Expr.Lit(value)       => value
    case Expr.Add(left, right) => eval(left) + eval(right)
    case Expr.Sub(left, right) => eval(left) - eval(right)
    case Expr.Mul(left, right) => eval(left) * eval(right)
    case Expr.Div(left, right) => eval(left) / eval(right)

val expr1: Expr = Expr.Add(Expr.Mul(Expr.lit(3), Expr.lit(2)), Expr.lit(5))
val expr2: Expr = Expr.Mul(Expr.Sub(Expr.lit(4), Expr.lit(1)), Expr.lit(9))
val expr3: Expr = (Expr.lit(4) - Expr.lit(1)) * Expr.lit(9)
val expr4: Expr = (Expr.lit(4) + Expr.lit(1)) / Expr.lit(5)
val expr5: Expr = Expr.lit(1) plus (Expr.lit(2) times Expr.lit(5))

@main def calc(): Unit =
  println(eval(expr1))
  println(eval(expr2))
  println(eval(expr3))
  println(eval(expr4))
  println(eval(expr5))

Full source for the Flix example is below:

mod Calculator {
  pub enum Expr {
    case Lit(Int32),
    case Add(Expr, Expr),
    case Mul(Expr, Expr),
    case Div(Expr, Expr),
    case Sub(Expr, Expr)
  }

  pub def eval(expr: Expr): Int32 = match expr {
    case Expr.Lit(i)      => i
    case Expr.Add(e1, e2) => eval(e1) + eval(e2)
    case Expr.Mul(e1, e2) => eval(e1) * eval(e2)
    case Expr.Div(e1, e2) => eval(e1) / eval(e2)
    case Expr.Sub(e1, e2) => eval(e1) - eval(e2)
  }

  pub def lit(value: Int32): Expr =
    Expr.Lit(value)

  pub def plus(left: Expr, right: Expr): Expr =
    Expr.Add(left, right)

  pub def minus(left: Expr, right: Expr): Expr =
    Expr.Sub(left, right)

  pub def times(left: Expr, right: Expr): Expr =
    Expr.Mul(left, right)

  pub def over(left: Expr, right: Expr): Expr =
    Expr.Div(left, right)

  instance Add[Expr] {
    pub def add(left: Expr, right: Expr): Expr = plus(left, right)
  }
  instance Sub[Expr] {
    pub def sub(left: Expr, right: Expr): Expr = minus(left, right)
  }
  instance Mul[Expr] {
    pub def mul(left: Expr, right: Expr): Expr = times(left, right)
  }
  instance Div[Expr] {
    pub def div(left: Expr, right: Expr): Expr = over(left, right)
  }

  pub def expr1(): Expr = Expr.Add(Expr.Mul(Expr.Lit(3), Expr.Lit(2)), Expr.Lit(5))
  pub def expr2(): Expr = Expr.Mul(Expr.Sub(Expr.Lit(4), Expr.Lit(1)), Expr.Lit(9))
  pub def expr3(): Expr = (Expr.Lit(4) - Expr.Lit(1))*Expr.Lit(9)
  pub def expr4(): Expr = (Expr.Lit(4) + Expr.Lit(1))/Expr.Lit(5)
  pub def expr5(): Expr = Expr.lit(1) `plus` (Expr.lit(2) `times` Expr.lit(5))

  @Test
  def checkExpr1(): Bool = eval(expr1()) == 11

  @Test
  def checkExpr2(): Bool = eval(expr2()) == 27

  @Test
  def checkExpr3(): Bool = eval(expr3()) == 27

  @Test
  def checkExpr4(): Bool = eval(expr4()) == 1
}

use Calculator.{Expr, eval, expr1, expr2, expr3, expr4, expr5}

// The main entry point.
def main(): Unit \ IO =
  eval(expr1()) |> println;
  eval(expr2()) |> println;
  eval(expr3()) |> println;
  eval(expr4()) |> println;
  eval(expr5()) |> println