Clearness - Learn Clarity - Iterate on lists

The Clarity language reference specifies a list of "limitations". The second one is:

"Looping may only be performed via map, filter, or fold"

This means that there's no such thing as for or while loops in Clarity. The only way to iterate is to use the built-in functions map, filter, and fold.
If you come from the JS/TS world for instance, these functions might feel familiar since they are the equal of [].map(), [].filter() and [].reduce().

An overview of `map`, `filter`, and `fold` (with food emojis 😋)

There's a great tweet by @stevluscher that explains the equivalent JS functions. Let's see how it would look like in Clarity. (This is just pseudo-code, we won't write the actual functions.)

(map cook (list "🌽" "🌾" "🥔"))
;; => (list "🍿" "🍞" "🍟")

(filter isCooked (list "🍿" "🌾" "🍟"))
;; => (list "🍿" "🍟")

(fold makeBurger (list "🥬" "🥩" "🧀" "🍅") "🍞")
;; => "🍔"

What do we learn with these examples?

👉 A list of 3 items is passed to map and it returns a new list of the same length with modified items.
👉 A similar list is given to filter, it returns a smaller list with some of the items of the original list.
👉 A list and an emoji are passed to fold, it returns an emoji (not a list) built with all the items.

Finally, they all take a function as their first argument (cook, isCooked & makeBurger). The second argument is a sequence (list, buffer, or string). fold takes a third argument, we'll talk more about it later.

We will focus on each of these functions.

map

The map function takes at least 2 arguments. The first one is a function that will be called for each element of the provided sequences. It also takes one or many sequences (1..N) of the same type. It always returns a list.

Take a look at two examples from the official doc:

;; 1st
(map not (list true false true false)) ;; returns (false true false true)
;; 2nd
(map + (list 1 2 3) (list 1 2 3) (list 1 2 3)) ;; returns (3 6 9)

The first example is very basic, map will apply the not function on each boolean of the provided list. So that in the result true becomes false and vice-versa.
The second example shows that many sequences can be given. It will apply the + function to each corresponding item ((+ 1 1 1) ;; => 3...). It works because (+) can take more than 2 arguments.

Time to put it to practice!

Exercise 1:

Write a square function so that (map square <list>) returns the squared value of each number (uint) of the list.

;; add your square function here

(print (map square (list u1 u2 u3 u4)))
;; => (list u1 u4 u9 u16)

💻 Open in ClarityTools

Hint

For this exercise, you'll have to define a private-function.
Note that we'll only manipulate unsigned integers (uints).

Solution exercise 1

(define-private (square (n uint))
  (* n n)
)
;; or using pow: (define-private (square (n uint)) (pow n u2))

(print (map square (list u1 u2 u3 u4)))
;; => (list u1 u4 u9 u16)

Exercise 2:

Define a data-map matching IDs (uint) to Pseudos (string-utf8). Write a public function get-10-pseudos that takes a list of up to 10 IDs and returns the matching 10 pseudos.

👉 Note that the map function is not the same thing as a data-map. The latter is a data structure used to store data within a Clarity smart contract.

(define-map pseudos uint (string-utf8 100))
(map-insert pseudos u0 u"muneeb")
(map-insert pseudos u1 u"satoshi")
(map-insert pseudos u2 u"aulnau")
(map-insert pseudos u4 u"akirtovskis")

;; insert your code here

(print (get-10-pseudos (list u0 u3 u4)))
;; (list (some u"muneeb") none (some u"akirtovskis"))

💻 Open in ClarityTools

Hint

The function get-10-pseudos will call the function map. Therefore, you'll have to declare a private function get-1-pseudo that will be called for each provided ID.

(define-map pseudos uint (string-utf8 100))
(map-insert pseudos u0 u"muneeb")
(map-insert pseudos u1 u"satoshi")
(map-insert pseudos u2 u"aulnau")
(map-insert pseudos u4 u"akirtovskis")

(define-private (get-1-pseudo (id uint))
  ;; this function might need some changes
)

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  ;; use map to call get-1-pseudo for each id
)

(print (get-10-pseudos (list u0 u3 u4)))
;; (list (some u"muneeb") none (some u"akirtovskis"))

Solution exercise 2

(define-map pseudos uint (string-utf8 100))
(map-insert pseudos u0 u"muneeb")
(map-insert pseudos u1 u"satoshi")
(map-insert pseudos u2 u"aulnau")
(map-insert pseudos u4 u"akirtovskis")

(define-private (get-1-pseudo (id uint))
  (map-get? pseudos id)
)

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  (map get-1-pseudo ids)
)

(print (get-10-pseudos (list u0 u3 u4)))
;; (list (some u"muneeb") none (some u"akirtovskis"))

filter

The filter function takes exactly 2 arguments. The first one is the test function and the second one is a sequence. filter will return a sequence of the same type as the second argument.
Each item of the input sequence will be passed to the test function, if it returns true the item is added to the output sequence.

Here is a nice example from the official doc:

(define-private (is-a (char (string-utf8 1))) (is-eq char u"a"))
(filter is-a u"acabd") ;; Returns u"aa"

It's pretty much self-explaining, it's also a nice example to show that if the second argument is a string, the output is of the same type. Here is another example from the doc:

(filter not (list true false true false false)) 
;;                     -----      ----- -----
;; returns (list false false false)

The native not function returns the inverse of the input. So every time filter passes the false value to it, it will return true and thus, add the item (ie: false) to the output list.

It's exercise time again 😄

Exercise 3:

Write a function called is-even so that (filter is-even <list>) returns the list of even numbers from the <list>.

;; add is-even function here

(print (filter is-even (list u1 u2 u10 u51 u42)))
;; => (list u2 u10 u42)

💻 Open in ClarityTools

Hint

To know if a number is even, you can check if the integer remainder from dividing by 2 is equal to zero. Clarity has a built-in function (mod i1 i2) to compute this value.

Solution exercise 3

(define-private (is-even (n uint)) (is-eq (mod n u2) u0))

(print (filter is-even (list u1 u2 u10 u51 u42)))
;; => (list u2 u10 u42)

Exercise 4:

Looking back at Exercise 2, the output of the get-10-pseudos could be improved. When we left it, it returned an optional utf8 string ((some u"string") or none). What if we wanted it to return only the pseudos, along with the matching id.

👉 This exercise is a bit more complicated than the previous ones. if it seems too complicated, feel free to jump to the fold section and come back to it later.

(define-map pseudos uint (string-utf8 100))
(map-insert pseudos u0 u"muneeb")
(map-insert pseudos u1 u"satoshi")
(map-insert pseudos u2 u"aulnau")
(map-insert pseudos u4 u"akirtovskis")

(define-private (get-1-pseudo (id uint))
  ;; you probably want to modifiy this part
)

;; add other private functions here

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  ;; you will need a combination of map and filter to make it work
)

(print (get-10-pseudos (list u0 u3 u4)))
;; > (list {id: u0, pseudo: "muneeb"} {id: u4, pseudo: "akirtovskis"})

👉 It's not possible to pass some native function to map, filter and fold (such as is-some or unwrap-panic for instance). They must be wrapped into another function with less generic type signatures.

💻 Open in ClarityTools

Hint 1

The problem can be split in three steps:

map the ids to their equivalent value: (some { id: uint, pseudo: (string-utf8 100) }). The value is wrapped into (some) because sometime it will be none and the function has to return the same type (an optional tuple in this case),
filter the items to keep only the some ones,
map again on the list in order to unwrap the (some <tuple>) into simply <tuple>.

Hint 2

In the end, get-10-pseudos will be a chain of map and filter:

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  (map unwrap-pseudo (filter is-some-pseudo (map get-1-pseudo ids)))
)

It's now your job to write down the get-1-pseudo, is-some-pseudo and unwrap-pseudo function.

Solution exercise 4

(define-map pseudos uint (string-ascii 100))
(map-insert pseudos u0 "muneeb")
(map-insert pseudos u1 "satoshi")
(map-insert pseudos u2 "aulnau")
(map-insert pseudos u4 "akirtovskis")

(define-private (get-1-pseudo (id uint))
  (some { id: id, pseudo: (unwrap! (map-get? pseudos id) none) })
)

(define-private (unwrap-pseudo
  (item (optional { id: uint, pseudo: (string-ascii 100) }))
)
  (unwrap-panic item)
)

(define-private (is-some-pseudo
  (item (optional { id: uint, pseudo: (string-ascii 100) }))
)
  (is-some item)
)

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  (map unwrap-pseudo (filter is-some-pseudo (map get-1-pseudo ids)))
)

👉 It's usually recommended to use unwrap! in order to throw better errors. We can consider that unwrap-panic is ok here because we call it after is-some 👉 In the real world, we would probably let the client take

fold

Fold is a bit different than map and filter. It takes exactly 3 arguments, a function, a sequence, and the initial value. The 1st argument, the function will be called recursively with each item and the previous result. A classic example is to compute the sum of the numbers in a list. (fold + (list 4 5 6) 0). It will call the + function 3 times (or each item in the list):

(+ 4 0) ;; = 4 (0 is the initial value)
(+ 5 4) ;; = 9 (4 is the precedent result)
(+ 6 9) ;; = 15 (9 is the precedent result)

As a quick warm-up, try achieving the same thing but with your own function for sum. So that (fold sum (list 4 5 6) 0) returns 15.
Also, write a sub function so that (fold sub (list 4 5 6) 0) returns 5. With the sub function, the order of the arguments matters.

Here are the solutions. Really give it a try before looking at it.

(define-private (sum (a int) (b int)) (+ a b))
(define-private (sub (a int) (b int)) (- a b))

Exercise 5

In this exercise, we'll try and write a read-only function to find the biggest number in a list of 10 uint.

(define-private (find-biggest (numbers (list 10 uint)))
  ;; find the biggest number in numbers
)

(find-biggest (list u2 u12 u3 u4 u5 u9 u2 u10 u0 u2)) ;; u12

💻 Open in ClarityTools

Hint

A hint is probably not needed here, it's quite similar to the previous exercises. You will have to write a private function, call it return-biggest, that will return the biggest of two numbers. Pass it to fold that will compare all of the items of the list versus the previous biggest.

Solution exercise 5

(define-private (return-biggest (number uint) (result uint))
  (if (> number result) number result)
)

(define-private (find-biggest (numbers (list 10 uint)))
  (fold return-biggest numbers u0)
)

Exercise 6

Remember exercise 4? We defined 3 private functions that were called with map, filter, and map again. It was pretty heavy to write but mostly, it was heavy to run! Indeed, resources are very important (in programming in general but even more when working on-chain). With the previous solutions, our code iterated three times on the list. For a list of 10 items, it would mean 30 calls to the private functions. What if we could use fold to replace the 3 iterations with only one?

(define-map pseudos uint (string-ascii 100))
(map-insert pseudos u0 "muneeb")
(map-insert pseudos u1 "satoshi")
(map-insert pseudos u2 "aulnau")
(map-insert pseudos u4 "akirtovskis")

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  ;; (fold ...)
)

💻 Open in ClarityTools

Hint 1

The first difficulty here could be to know what should be the initial value of the result? it's just an empty list. So the function would look like that

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  (fold fold-pseudos ids (list))
)

It's your job to write fold-pseudos now.

Hint 2

We previously used unwrap-panic but mentioned that it wasn't ideal. Here, you'll be able to easily replace it with unwrap! and return the result in case of error.

Solution exercise 6

(define-map pseudos uint (string-ascii 100))
(map-insert pseudos u0 "muneeb")
(map-insert pseudos u1 "satoshi")
(map-insert pseudos u2 "aulnau")
(map-insert pseudos u4 "akirtovskis")

(define-private (fold-pseudos
  (id uint)
  (acc (list 10 { id: uint, pseudo: (string-ascii 100) }))
)
  (let ((pseudo (unwrap! (map-get? pseudos id) acc)))
    (unwrap! (as-max-len? (append acc { id: id, pseudo: pseudo }) u10) acc)
  )
)

(define-read-only (get-10-pseudos (ids (list 10 uint)))
  (fold fold-pseudos ids (list))
)

👉 The second argument of the folding is often called acc, as in "accumulator" since it accumulates the result of each iteration. It can also be called "result" or something more meaningful in a given context.

Conclusion

Congrats for making it to the end of the article. I hope you learned a thing or two and that you are ready to master map, filter and, fold.
Remember the emojis at the beginning? It's important to recognize when to use which function. Need to transform all items of a list? Use map. Need to remove items from a list? Use filter. Need to condense a list into something else? fold to the rescue!

One more exercise?

Complete the is-sorted function to check if the numbers in the input list are ordered from lowest to greatest. No clues, no solution for this one. Keep it simple and efficient 😄

(define-read-only (is-sorted (numbers (list 10 uint)))
  ;; ...
)

(print (is-sorted (list u1 u2 u3 u4))) ;; true
(print (is-sorted (list u1 u2 u2 u3))) ;; true
(print (is-sorted (list u1 u5 u3 u4))) ;; false

Useful links

Official references: map, filter, and fold.

Clarity language

Iterate on lists

An overview of map, filter, and fold (with food emojis 😋)

map

Exercise 1:

Exercise 2:

filter

Exercise 3:

Exercise 4:

fold

Exercise 5

Exercise 6

Conclusion

Useful links

An overview of `map`, `filter`, and `fold` (with food emojis 😋)