Looping

You might be familiar with some kind of looping convention from other programming languages but for folks who come from imperative languages we'll talk briefly about Unison's strategies for handling iterative actions. 👋 Heads up: this document will likely be review for folks who are familiar with functional programming conventions for looping—if that's you, skip to the end of the doc, where we briefly describe some Unison conventions around recursion.

Functional looping

We'll dive right in with an example. Let's imagine you're tasked with writing a function to add up elements in a list.

If we were to express this in a made up programming language—let's call it nosinU 🙃—with Unison-like syntax but a different paradigm we might do something like:

myTotal : [Nat] -> Nat
myTotal list =
  var currentTotal = 0
  var currentIndex = 0
  -- remember, this is a made up language! 🙃
  while currentIndex < (length list)
    currentTotal += (unsafeAt currentIndex list)
    currentIndex += 1
  currentTotal

Here we're keeping track of a few details—we care about the length of the list so we don't run off the end; we're continually updating the value of the current index to access the data in the list; and we are adding to the current total, which we change when we encounter each element. The core of what we're doing is building a running total, but our program is also concerned with how we're updating each of these pieces of information.

Unison doesn't support looping or iteration with things like while loops, for loops, or break statements. One way to accomplish this in Unison is to rely on recursion.

As very brief refresher, recursive functions work by dividing a problem into two broad categories: 1.) scenarios where the recursion can be considered "done" and will not make further recursive calls, and 2.) cases where the function is reducing the problem space and then calling itself again.

An analogous recursive function which sums up the elements in a list might look like:

recursive.myTotal : [Nat] -> Nat
recursive.myTotal : [Nat] -> Nat
recursive.myTotal = cases
  []           -> 0
  head +: tail -> head Nat.+ recursive.myTotal tail

This recursive function is using pattern matching on a Unison list to establish a base case and a recursive case. When the list is empty, it returns the value 0, otherwise, it decomposes the list into the current element and its remainder, adding the current value to a recursive call. Note that this implementation of the sum function requires that the head element of the list be stored on the call stack.

Tail call elimination

Better yet, we can write this recursive function so that each successive call to myTotal doesn't grow the call stack. When the result of evaluating a function can be immediately returned to its enclosing caller, the function is in "tail call position". The Unison compiler will perform an optimization called tail call elimination for functions like this.

tailRecursive.myTotal : [Nat] -> Nat
tailRecursive.myTotal : [Nat] -> Nat
tailRecursive.myTotal list =
  use Nat +
  loop : [Nat] -> Nat -> Nat
  loop innerList currentTotal = match innerList with
    []           -> currentTotal
    head +: tail -> loop tail (head + currentTotal)
  loop list 0

Because these kinds of operations are so commonly performed on data structures, it's more common to delegate control over the looping logic to other functions which are based on the principles of recursion.

In Unison we might use one of the class of higher-order functions which handle "folding" to express the kind of operation where each element in the data structure needs to be combined in a programmatic way.

fold.myTotal : [Nat] -> Nat
fold.myTotal : [Nat] -> Nat
fold.myTotal list =
  use Nat +
  List.foldLeft
    (currentTotal element -> currentTotal + element) 0 list

The core parts of the operation we're performing are the same in both the List.foldLeft and original versions of the myTotal function: we initialize our currentTotal value with 0, and each successive element of the list is added to that total in the body of the higher-order function which we provide to List.foldLeft. You can think of that function (currentTotal element -> currentTotal + element) as declaring the logic or intent of "add up a running total" - for this reason, you'll often hear this style called declarative programming.

What if we wanted to write a function that breaks out of the loop in the event that a particular condition is hit?

In our made up alternative language, you might make use of a break statement.

bottlesOfPop : [Nat] -> [Text]
bottlesOfPop bottleRange =
  var bottleLocations = []
  var currentIndex = 0

  while currentIndex < (length list)
    bottle = unsafeAt currentIndex bottleRange
    if bottle > 10 then break else let
      bottleLocations += bottleLocations :+ ((toText bottle) ++ " bottles of pop on the wall")
    currentIndex += 1
  bottleLocations

We have a few strategies for this in Unison. In this case we might use List.takeWhile, which starts from the leftmost element of the list and will continue taking elements from the list until the condition provided is no longer true. Then we might transform that list into the desired text value in a second call to List.map.

bottlesOfPop : [Nat] -> [Text]
bottlesOfPop bottleRange =
  use Text ++
  ninetyNine =
    use Nat <=
    List.takeWhile (bottle -> bottle <= 10) bottleRange
  map (elem -> Nat.toText elem ++ " bottles of pop on the wall") ninetyNine
bottlesOfPop (List.range 1 100)

If we just wanted to gather all the elements which met a condition from the list, we might use a List.filter function to ensure that we are only operating over the desired subset of data. In each of these cases, the higher-order function is handling iteration. These and other functions can be found in the List namespace.

Recursion conventions in Unison

You do not need to annotate recursive functions with their return type for a program to typecheck.

sum listOfNats = match listOfNats with
   [] -> 0
   head +: tail -> head + (sum tail)

sum [9,8,7,6]

Unison supports tail call elimination. Functions in tail call position (including mutually recursive functions) are evaluated without growing the stack.

Effectful recursion

Recursive code can perform effects too. When your code performs an ability for some kind of computational effect, your function signature should include an ability requirement in curly braces in the return type of the function. See below for an example.

use Nat - ==
loop : Nat ->{Stream Nat} ()
loop = cases
  n 
    | n == 0    -> ()
    | otherwise ->
      emit n
      loop (n - 1)
Stream.toList do loop 10
⧨

Many of the higher-order functions on data types in the base library are already ability polymorphic. In the signature for List.map, List.map : (a ->{𝕖} b) -> [a] ->{𝕖} [b], the {𝕖} symbol in the lambda argument means that the transformation function a -> b can perform an effect in the process of mapping over each element.

Where to next?

🌟 Learn about error handling with data types