# Looping

Sometimes you'll want to run a body of code multiple times. You might be familiar with some kind of looping convention from other programming languages but for folks who come fromimperative languageswe'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,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
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 ->
use Nat +
head + 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.

Unison supports tail call elimination. This is an optimization that the Unison compiler will do for functions (including recursive and mutually recursive functions) which are in tail call position. Functions in tail call position are evaluated without growing the function call stack.

tailRecursive.myTotal : [Nat] -> Nat
tailRecursive.myTotal : [Nat] -> Nat
tailRecursive.myTotal list =
loop : [Nat] -> Nat -> Nat
loop innerList currentTotal =
match innerList with
[]           -> currentTotal
head +: tail ->
use Nat +
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.

loop : Nat ->{Stream Nat} ()
loop = cases
n
| n Nat.== 0 -> ()
| otherwise  ->
use Nat -
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.