Basic Syntax for iterating through List Element and processing each of them

Question

I am creating two lists in liquidity and trying to process on them as follow:

type two_element = {
 name: string;
 value : nat;
}

type list1 = two_element list;
type list2 = two_element list;

Suppose I need to find out whether some "name" in list1 is present with smaller "value" in list2 or not, if the "value" in list 2 is smaller, get a two_element list of all those "name" with the value difference.

A simple example of what I want to get is as follow: input lists:

  let list1 = [{"A"; 5}; {"B"; 10}; {"C"; 20};] in  
  let list2 = [{"A"; 15}; {"B"; 8}; {"C"; 15}; {"D";25};{"E"; 25}] in  

output list:  
  list3 = [{"B"; 2}; {"C"; 5}]  

I think I can iterate the list1 and compare each element's name by iterating it in list2, but how to write the syntax of this iteration? Maybe using Loop? It's not very clear from the syntax and examples given in documentation to use the loop.

Also, I was thinking, maybe, I can map each element of both lists to another function using List.map and it will return a two_element list containing the names and value difference but I am not sure how that can be done for the two lists simultaneously.

I couldn't find any example of List processing in this manner and spent some time in understanding the exact working of Loops and List.map but couldn't get any significant conclusion.

Answer 1

You can use Loop.left (with and accumulator) but it is easier to use List.fold and tail recursive functions (those are encoded with loops).

Here is a way to do it (you can call the entry point test with parameter [{name="A"; value=5}; {name="B"; value=10}; {name="C"; value=20}] and storage [{name="A"; value=15}; {name="B"; value=8}; {name="C"; value=15}; {name="D";value=25};{name="E"; value=25}] to try it on your example):

type two_element = {
  name: string;
  value : nat;
}

type storage = two_element list 

(* Tail recursive function. Returns the value field if an element in l2 has
   field name = x, or None otherwise. *)
let[@inline] rec assoc (x, l) =
  match l with
  | [] -> None
  | y :: l ->
      if y.name = x then Some y.value
      else assoc (x, l)

let diff (l1, l2) =
  let r =
    (* Fold over l1. acc contains new two_element values with the difference *)
    List.fold (fun (x1, acc) ->
        match assoc (x1.name, l2) with
        | None -> acc (* x1.name is not in l2 *)
        | Some v2 ->
            match is_nat (x1.value - v2) with
            | None -> acc (* the value associated to x1.name in l2 is greater 
                             than x1.value *)
            | Some value ->
                (* value = x1.value - v2 is positive *)
                { name = x1.name; value } :: acc
      ) l1 [] in
  (* Finally reverse the resulting list, as we always put elements in front *)
  List.rev r

let%entry test l1 l2 =
  [], diff (l1, l2)