Susan Potter
software: Created / Updated

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

In the first installment of the Flix series we looked at how to get started with Flix using a sum type and pattern matching.

Today we will be looking at how to define higher order-functions and infix combinator syntax in the Flix programming language.

Our objectives are to:

• introduce higher-order functionsl (HOFs) to readers unfamiliar with the concept or unsure the utility
• show how to define higher-order functions in Flix
• explain what infix operators are and why they are useful
• demonstrate how we can define infix operations in Flix
• review how simple it was to define HOFs and infix operators using Flix and compare to Scala

### Getting started …

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.

### Higher-Order Functions in Flix (monomorphic and polymorphic)

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`

### Infix Combinator Operators in Flix

Scala developers are used to using custom infix operators and maybe defining their own. Flix also allows you to define your own infix operators to build embedded domain-specific languages that fit your problem space.

If we return to the simple calculator example from part 0, we can create user-defined infix operators for each of the calculation types in the `Expr` enum.

Let's see how we might do this in Scala3 first:

``````// The sum type from the prior blog post
// to refresh our memory
enum Expr:
case Lit(value: Int)
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)``````

Some notes about Scala3's custom symbolic infix operators:

• `extension` is used to extend the syntax of the first argument given
• extension methods can be used infix
``````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)``````

This allows us to write expressions like the following in Scala3 (tested on v3.3.0):

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

Now bringing it back to Flix, we can do similar user-defined symbolic operators. So let's see what happens when we try using the same approach as Scala:

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

When we run `flix build` we get the following syntax error:

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

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

So what does re-definition of a reserved name mean?

In Flix, + is reserved so we can't redefine it. Instead, we can define instances for built-in typeclasses:

• `Add`
• `Sub`
• `Mul`
• `Div`

Let's see what this would look like:

``````instance Add[Expr] {
pub def add(left: Expr, right: Expr): Expr =
}
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)
}``````

Now we can then use infix syntax with those symbolic operators thanks to those typeclass instances, like so:

``````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``````

Let's see that these new tests pass using our trusted friend `flix test`:

``````> flix test
Found `flix.toml'. Checking dependencies...
Resolving Flix dependencies...
Resolving Maven dependencies...
Running Maven dependency resolver.
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.``````

However, non-symbolic infix operations like plus need backticks:

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

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

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``````

If you try to build this, you will get the following parse error like the following:

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

This was because I forgot to add the return type annotation, so we would fix by adding `: Expr` after the arguments like so:

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

#+end_src

This is different to Scala where we aren't required to add return types most of the time since it can be inferred.

### Recap

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.

### Appendix

Full source code for the Scala3 example is below:

``````enum Expr:
case Lit(value: Int)
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 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 =

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)

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``````

If you enjoyed this content, please consider sharing via social media, following my accounts, or subscribing to the RSS feed.