# 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 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, 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.

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 to sum up is empty, it returns the value 0, 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 to recursive.myTotal. Note that this implementation of the sum function requires that the head element of the list be stored on the call stack.

Better yet, we can write this recursive function so that each successive call to myTotal doesn'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 =
use Nat +
loop : [Nat] -> Nat -> Nat
loop innerList currentTotal = match innerList with
[]           -> 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 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 +
distributed.lib.base.data.List.foldLeft
(currentTotal element -> currentTotal + element) 0 list

The core parts of the operation we're performing are the same in both the distributed.lib.base.data.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 distributed.lib.base.data.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 distributed.lib.base.data.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 distributed.lib.base.data.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

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)
lib.base.data.Stream.toList do loop 10โงจ[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Many of the higher-order functions on data types in the base library are already ability polymorphic. In the signature for distributed.lib.base.data.List.map, distributed.lib.base.data.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.