Variadic map function

[njordhov]

The map function in Clarity currently is limited to functions that takes a single argument, mapping them over a single sequence.

The map function should be variadic and allow functions that takes more than one argument, mapping them over a number of sequences matching their arity.

For example:

(map + (list 1 2 3) (list 4 5 6))     ;; evaluates to (5 7 9) 

Variadic map functions are found in similar other languages including Racket, Scheme, Common Lisp and Clojure.

Originally posted at: https://github.com/blockstack/stacks-blockchain/issues/1482

[njordhov]

In functional programming, it is commonplace to use map with partial function applications and anonymous functions, typically closing over local bindings. Variadic map could compensate for Clarity lacking closures by providing an alternative means to pass arguments from the local context to the mapping function.

With multiple sequences as arguments, it's an open question how to handle lists of different length. Racket takes a strict approach, requiring all input lists to have the same length. In contrast, Common Lisp and Clojure only iterate to the end of the shortest input sequence.

Clarity can benefit from variadic map implicitly extending shorter input sequences to the length of the longest by repeating their last item. This can be used to pass on arguments to the applied function, without requiring an explicit expression such as repeat to fill the shorter sequences.

Use case from the Blockstack codebase: https://github.com/blockstack/stacks-blockchain/blob/27381d64b1e6c8f308537a2c397958a97fdea337/src/chainstate/stacks/boot/pox.clar#L338-L352

Discussion: https://github.com/blockstack/stacks-blockchain/pull/1790#discussion_r478651298

Assuming that map fills list arguments to have the same length, this could be an alternative implementation:

(fold + 
  (map add-pox-addr-to-ith-reward-cycle 
    (list {pox-addr: pox-addr, first-reward-cycle: first-reward-cycle, num-cycles: num-cycles, amount-ustx: amount-ustx})
    (list u0 u1 u2 u3 u4 u5 u6 u7 u8 u9})))

It is of course possible to rather use fold to accumulate the integers, or even combining into a single reducer. A benefit of using map for such mapping is that the applied function will be simpler and more straight-forward, returning a single integer result for each iteration with the accumulated sequence immediately available, while fold has to pass on arguments in the accumulator and requires extracting the accumulated result on completion.

[njordhov]

Variadic map can substantially simplify the implementation of various sequence processing. For example, just testing whether a list contains an item takes a good chunk of Clarity code. With variadic map it can be covered by a one-liner:

(fold or (map is-eq (list item) items) false)    ;; true if the items list contains the item

Compare to the implementation of contains and contains-check in the rockets-base.clar example:

;; implementing a contains function via fold
(define-private (contains-check
                   (y principal)
                   (to-check {p: principal, result: bool}))
   (if (get result to-check)
        to-check
        {p: (get p to-check),
         result: (is-eq (get p to-check) y)}))

(define-private (contains (item principal) (items (list 10 principal)))
   (get result (fold contains-check items
                    {p: item, result: false)))

[kantai]

Variadic map was implemented in Clarity in Stacks 2.0