Lab 5 is due Thursday, November 2 at 11:59pm.

This week, you will practice higher-order list programming. More specifically, you will practice using common list programming tools like map, filter and fold on a selection of list processing operations.

First, copy the following data definitions from this page. 

(define-type Bank
  (U 'Lake 'Left 'Right))

(define-struct Account
  ([bank   : Bank]
   [number : Integer]))

(define-struct Trx
  ([from   : Account]
   [to     : Account]
   [amount : Integer]))

(define-type Ledger
  (Listof Trx))
These definitions are similar to the definitions from lab4, except the name of the Transaction structure has been changed to Trx for brevity and Ledger is now built upon the built-in Listof constructor instead of being a custom unary tree.

This table gives the types of the most common higher-order list operators. The andmap and ormap functions, not previously discussed, check whether a test holds for all of or at least one of the items in a list, respectively. 

(: map    : All (A B) (A -> B) (Listof A)     -> (Listof B))

(: filter : All (A) (A -> Boolean) (Listof A) -> (Listof A))

(: foldl  : All (A B) (A B -> B) B (Listof A) -> B)

(: foldr  : All (A B) (A B -> B) B (Listof A) -> B)

(: andmap : All (A) (A -> Boolean) (Listof A) -> Boolean)

(: ormap  : All (A) (A -> Boolean) (Listof A) -> Boolean)

A rule of thumb about the choice between foldl and foldr. When the accumulating operator is commutative, such as + or *, the result is the same in either case, so use foldl because it is a bit faster than foldr. In the case of non-commutative operators such as string-append, beside or overlay, the result may differ, so proceed with caution and think carefully about which order you want. The result of foldr is often the more natural or expected order (your mileage may vary on this last point).

Here are a few examples of higher-order list functions in action for your reference. 

;; map examples

(map add1 (list 1 2 3 4)) 
=> (list 2 3 4 5)

(map sqr (list 100 49 25)) 
=> (list 10 7 5)

(map even? (list 2 4 7 8)) 
=> (list #t #t #f #t)

(map number->string (list 2 3 4)) 
=> (list "2" "3" "4")

(map (lambda ([s : String]) (add1 (string-length s))) (list "a" "bb" "c"))
=> (list 2 3 2)

;; filter examples

(filter even? (list 1 2 3 4)) 
=> (list 2 4)

(filter negative? (list 1 2 3 4)) 
=> '()

(filter (lambda ([s : String]) (even? (string-length s))) (list "a" "bb" "c"))
=> (list "bb")

;; foldl examples

(foldl string-append "" (list "a" "b" "cd"))
=>
"cdba"

(foldl + 0 (list 2 4 6))
=> 12

(foldl * 0 (list 2 4 6)) 
=> 0

(foldl * 1 (list 2 4 6)) 
=> 48

;; foldr examples

(foldr string-append "" (list "a" "b" "cd"))
=> "abcd"

(foldr + 0 (list 2 4 6)) 
=> 12

(foldr * 0 (list 2 4 6)) 
=> 0

(foldr * 1 (list 2 4 6)) 
=> 48

(foldr (lambda ([n : Integer] [tot : Integer]) (if (even? n) (+ n tot) tot))
       0
       (list 2 3 10)) 
=> 12

(foldr (lambda ([s : String] [tot : Integer]) (+ (string-length s) tot)) 
       0
       (list "a" "bb" "c")) 
=> 4

(foldr (lambda ([n : Integer] [s : String]) 
               (string-append (number->string n) s))
       ""
       (list 1 2 3))
=> "123"

;; andmap examples

(andmap even? (list 2 4 6)) 
=> #t

(andmap even? (list 2 4 5))
=> #f

(andmap even? (list 3 5 7))
=> #f

;; ormap examples

(ormap even? (list 2 4 6))
=> #t

(ormap even? (list 2 4 5))
=> #t

(ormap even? (list 3 5 7))
=> #f

For this week's exercise, complete the following operations (see below). In each case, avoid explicit recursion. Any recursion that takes place should be tucked away inside one of the built-in operators. As a result, even though you are writing a collection of functions that all depend on recursion to do their work, none of the functions you write today needs to call itself directly.

You may still write helper functions as you see fit, but none of those should contain explicit recursion either.

For example, if we asked you to write a function

(: rationalize : Ledger -> (Listof Exact-Rational))
to present all the transaction amounts in a ledger as a rational number of dollars as opposed to an integer number of pennies, you could write it as a call to map like so: 
(define (rationalize ledger)
  (local 
    {(: r : Trx -> Exact-Rational)
     (define (r t) 
       (/ (Trx-amount t) 100))}
   (map r ledger)))
The definition of the function r need not be local, but it keeps the code tidy to define it only where you need it. Alternatively, you could make the code tidier still by avoiding the local definition and using an anonymous function as follows: 
(define (rationalize ledger)
  (map (lambda ([t : Trx]) (/ (Trx-amount t) 100)) ledger))

Here are the functions you need to write. We have hinted under each type ascription which higher-order tool is appropriate. 

(: trx-total : Ledger -> Integer)
;; hint: fold
;; compute the total amount of money in all transactions
                   
(: trx-from-account : Account Ledger -> Ledger)
;; hint: filter
;; gather all transactions from the given account

(: trx-from-bank : Bank Ledger -> Ledger)
;; hint: filter
;; gather all transactions from the given bank

(: count-from-account : Account Ledger -> Integer)
;; hint: fold
;; count all transactions that originate from account

(: count-to-bank : Bank Ledger -> Integer)
;; hint: fold
;; count all transactions that flow into given bank

(: verify : Ledger -> Boolean)
;; hint: andmap (see above for examples)
;; verify no trx has nonpositive amount and no trx goes to/from same account

(: ledger-net : Bank Ledger -> Integer)
;; hint: fold
;; determine the net amount flowing into (positive) or 
;; out of (negative) bank given the ledger

(: at-or-above : Integer Ledger -> Ledger)
;; hint: filter
;; return all transactions whose amount is >= the given threshold

(: largest : Ledger -> Ledger)
;; match and return empty list for empty argument, fold nonempty
;; compute the ledger of zero or more of trxs whose amount 
;; is equal to the largest amount on the ledger

;; ==== ==== ==== ====

;; a report consists of a bank,
;; all transactions that flow into the bank from an external source,
;; all transactions internal to the bank,
;; all transactions that flow out of the bank to an external bank,
;; all transactions that involve the bank and are not verifiable
;; (per verify above)
(define-struct Report
  ([bank     : Bank]
   [inflow   : Ledger]
   [internal : Ledger]
   [outflow  : Ledger]
   [errors   : Ledger]))

(: build-report : Bank Ledger -> Report)
;; you can write this as four calls to filter,
;; or, for a challenge, as one fold with a rather involved custom operator

Some of the latter problems involving fold are especially challenging. Before you attempt to fold over a list in a complicated way, make sure you settle the types in your mind first. That is an essential first step.

Please submit one file, lab5.rkt, in a lab5 directory in your repository.