Looping

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.

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 usingpattern matching on a Unison listto establish a base case and a recursive case. When the list to sum up is empty, it returns the value0,otherwise, if the list can be decomposed into a head element and tail containing the remainder of the list, it adds the current element's value to a recursive call torecursive.myTotal.Note that this implementation of the sum function requires that the head element of the list be stored on thecall stack.

Better yet, we can write this recursive function so that each successive call tomyTotaldoesn't grow the call stack.

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

However, because these kinds of operations are so commonly performed on data structures, you'll find that it's more common to delegate control over the looping logic to other functions which are based on the principles of recursion. Because we've entrusted the finer grained details of "how repeat the desired code" to other functions, we are able to focus on describing the desired effect of our program.

In Unison we might use one of the class ofhigher-order functionswhich 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 theList.foldLeftand original versions of themyTotalfunction: we initialize ourcurrentTotalvalue with0,and each successive element of the list is added to that total in the body of the higher-order function which we provide toList.foldLeft.You can think of that function(currentTotal element -> currentTotal + element)asdeclaringthe logic or intent of "add up a running total" - for this reason, you'll often hear this style calleddeclarative 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 abreakstatement.

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 useList.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 toList.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 aList.filterfunction 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 theListnamespace.

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 anability requirementin 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 ->
      Stream.emit n
      loop (n - 1)
toList! '(loop 10)
⧨
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Many of thehigher-order functionson data types in thebaselibrary are already ability polymorphic. In the signature forList.map,List.map : (a ->{𝕖} b) -> [a] ->{𝕖} [b],the{𝕖}symbol in thelambdaargument means that the transformation functiona -> bcan perform an effect in the process of mapping over each element.