Higher Order Functions and Tail Recursion

Higher Order Functions in Python

Pardon the hand-written notes. Will try and type out the whole thing in some future point.

Hisaab -- A Program to Simplify Transactions among Friends

It's always fun when your technical knowledge comes in handy while to trying to solve some day-to-day problem. you get a kick in being able to describe a problem in its core mathematical essence, and in creating an algorithm to solve the problem. The size of the kick is independent of the size and complexity of the problem.

Follows a cute example of the above.

Problem Description

Often, a group of people may transact money between each other. A situation may arise when each person may have taken some money from someone else, thus owing the other person that much amount. To settle the accounts, there might be needed a very large number of transactions needed, requiring everyone to meet everyone else.

Solution Approach

A good way to simplify the settlement process would be to make one of the people involved as the bank, or the star. Everyone makes a transaction with this person only, only the net amount she owes to anyone.

Mathematical Model

The original situation can be represented as a directed graph as shown above in the left side graph. Each node represents a person, and each directed edge indicates a transaction. For example, the edge with weight 15 between A and F means that A owes Rs. 15 to F.

The solution is shown in the right side graph above. Note that all edges now involve node D. Thus every node needs to make at most one transaction with node D, which is huge simplification of the process. The accounts will now be settled with only 5 transactions as opposed to 9 in the original graph. As an added benefit, nodes which need not transact at all also get identified. For example, node B gets isolated in the right side graph, meaning that it doesn't need to transact anything with node D.

Transforms

The solution is achieving through the following two simple graph transformations.

Rerouting

Suppose we wish to make node 1 the star node. This means that we want all transactions between any pair not involving node 1 should be routed through node 1, as shown above.

Multigraph to Graph

Implementation

Follows an implementation of the above idea in OCaml. We use a purely functional style (i.e. by using a completely side-effect free style of programming). If you remove the profuse amount in-line documentation, you will notice that the code is remarkably concise (just about 25 lines of code)!

Find an OCaml and Python implementation here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160

(* The following program is useful to simplify the transactions amongst a group of people. Problem Description: Often, a group of people may transact money between each other. A situation may arise when each person may have taken some money from someone else, thus owing the other person that much amount. A good way to simplify the settlement process would be to make one of the people involved as the bank, or the star. Everyone makes a transaction with this person only, only the net amount she owes to anyone. User Instruction: 1. Open the file in a editor. 2. Edit the variable g to reflect what each person owes any other. 3. Save the file 4. Open the OCaml REPL 5. enter the command: #use "hisaab.ml";; The answer will appear on the standard output. *) (* Description: Takes an edge e = (n1, w, n2) and a node n, and returns a list of edges, to apply starification transform on e. Signature: 'a * int * 'a -> 'a -> ('a * int * 'a) list Example: 1) # reroute (1, 10, 2) 1;; - : (int * int * int) list = [(2, -10, 1)] # reroute (2, 10, 1) 1;; - : (int * int * int) list = [(2, 10, 1)] # reroute (2, 10, 3) 1;; - : (int * int * int) list = [(2, 10, 1); (3, -10, 1)] *) let reroute (n1, w, n2) n = if n1 = n then [(n2, -w, n1)] else if n2 = n then [(n1, w, n2)] else [(n1, w, n); (n2, -w, n)] (* Description: Takes a list of lists and returns the corresponding list Signature: 'a list list -> 'a list Example: # flatten_list [[1;2]; [3;4;5];[6]];; - : int list = [1; 2; 3; 4; 5; 6] *) let rec flatten_list = function [] -> [] | h :: t -> List.append h (flatten_list t) (* Description: Takes a graph (could be multigraph) g and and a node n and returns and equivalent graph g' which is starred at n, and preserves the net input/output at each node of g. Signature: ('a * int * 'a) list -> 'a -> ('a * int * 'a) list Example: # starify_graph [(1, 160, 2); (2, 440, 1); (1, 300, 3); (3, 160, 2)] 1;; - : (int * int * int) list = [(3, 160, 1); (2, -160, 1); (3, -300, 1); (2, 440, 1); (2, -160, 1)] *) let starify_graph g n = let list_of_lists = List.map (fun g -> reroute g n) g in flatten_list list_of_lists (* Description: Takes an edge e = (n1, w, n2) and a graph g, and returns a new graph g' such that g' is same as g except that if g contains an edge e' with same source and target nodes as e, then e and e' are merged by adding their weights. Signature: 'a * int * 'b -> ('a * int * 'b) list -> ('a * int * 'b) list Assumption: g is not a multi-graph. Example: # let g2 = [(3, -140, 1); (2, 120, 1)];; val g2 : (int * int * int) list = [(3, -140, 1); (2, 120, 1)] # merge (3, 140, 1) g2;; - : (int * int * int) list = [(3, 0, 1); (2, 120, 1)] # merge (3, 140, 2) g2;; - : (int * int * int) list = [(3, -140, 1); (2, 120, 1); (3, 140, 2)] # merge (3, 140, 2) [];; - : (int * int * int) list = [(3, 140, 2)] *) let rec merge (n1, w, n2) = function [] -> [(n1, w, n2)] | (n1', w', n2') :: t -> if n1 = n1' && n2 = n2' then ((n1, w + w', n2) :: t) else (n1', w', n2') :: (merge (n1, w, n2) t) (* Description: Takes a multigraph mg and returns its corresponding graph g by merging all edges between common pairs of nodes. Signature: ('a * int * 'b) list -> ('a * int * 'b) list Example: # graph_of_mgraph [(1, 160, 2); (2, 300, 1); (2, 140, 1); (1, 300, 3); (3, 160, 2)];; - : (int * int * int) list = [(1, 160, 2); (2, 440, 1); (1, 300, 3); (3, 160, 2)] *) let graph_of_mgraph mg = let rec iter g = function [] -> g | e :: t -> iter (merge e g) t in iter [] mg (* Description: Turns the weight of every edge of a given graph to positive value by inverting the direction of the edge if its weight is negative. Signature: ('a * int * 'a) list -> ('a * int * 'a) list Example: # abs_weight [("Taru", -140, "Shraddha"); ("Shilpi", 20, "Shraddha")];; - : (string * int * string) list = [("Shraddha", 140, "Taru"); ("Shilpi", 20, "Shraddha")] *) let abs_weight g = List.map ( fun (n1, w, n2) -> if w >= 0 then (n1, w, n2) else (n2, -w, n1) ) g let remove_empty_edges g = List.filter (fun (_, w, _) -> w <> 0) g (* Example graph (Provided by Shilpi) node 1 -> Shilpi node 2 -> Shraddha node 3 -> Taru (1, 160, 2) -> Shilpi owes Rs. 160 to Shraddha *) let g = [("Shilpi", 160, "Shraddha"); ("Shraddha", 300, "Shilpi"); ("Shraddha", 140, "Shilpi"); ("Shilpi", 300, "Taru"); ("Taru", 160, "Shraddha")] let star_node = "Shraddha" let _ = remove_empty_edges ( abs_weight ( graph_of_mgraph ( starify_graph g star_node))) let e1 = [ ("r2", 10, "r3"); ("r1", 20, "r2"); ("r2", 10, "r4"); ("r4", 30, "r3"); ("r1", 15, "r6"); ("r6", 100,"r5"); ("r7", 25, "r5"); ("r5", 150,"r4"); ("r3", 30, "r7"); ("r7", 90, "r4"); ] let star_node = "r4" let _ = remove_empty_edges ( abs_weight ( graph_of_mgraph ( starify_graph e1 star_node)))

Counter in Python

Presenting here two implementations of a counter.

What does the counter do?

Given a base n, this counter will allow you to do base n counting. What's base-n counting? There are n digits: 0, 1, 2, ..., n - 1. At each place, the digit changes from i to i + 1 if i < n - 1, and to 0 if i = n - 1. This change happens when the change at that place is triggered. And when does the trigger happen. For the unit's place, the trigger happens whenever the function is called. For all other places, the trigger happens when the previous place's digit rolls over from n - 1 to 0. That's all. That's a bit technical description for the simple act of counting we learn in our KG. But if we want to implement the counter, it needs to be written in this algorithmic language.

A 3-bit binary (base-2) counter goes like:

000, 001, 010, 011, 100, 101, 110, 111, 000, ...

A 2-digit base-4 counter would count as:

00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 00, ...

What do we usually do in day-to-day counting? decimal (base-10) counting.

How do we Use the Counter Program?

Below is a piece of code that could be used to implement a binary counter on a 3-bit number.

base = 2
inc = makeCounter_iter(base)
n = [0, 0, 0]
print n
for i in range(base ** len(n)):
    n = inc(n)
    print n

 The inc(n) gives n + 1 in the base n number system which is pre-decided while instantiating the counter:

base = 2

#!/usr/bin/python
def makeCounter_iter(base):
    def isZero(lst): return lst == [0] * len(lst)

    def inc(num):
        if(len(num) > 1):
            rem = inc(num[:-1])
            if(isZero(rem)):
                if(num[-1] == base - 1):    rem.extend([0]) 
                else:                rem.extend([num[-1] + 1])
            else:    rem.extend([num[-1]])
            return rem
        else:
            new = [0]
            if(not num[0] == base - 1):    new[0] = num[0] + 1
            return new
    return inc

Now follows the recursive version.

#!/usr/bin/python
def makeCounter_rec(base):
    def incDigit(num, pos):
        new = num[:]
        if(num[pos] == base - 1):
            new[pos] = 0
            if(pos < len(num) - 1):    return incDigit(new, pos + 1)
        else:
            new[pos] = new[pos] + 1
        return new

    def inc(num): return incDigit(num, 0)
    return inc

Any day, the recursive implementation trumps over the iterative version. The recursive implementation is smaller and more readable because it's very like the way the process of counting is formally defined in the beginning of the article.

Functional Programming Flavour

One thing to notice is that we use functional language aspect of python. The function makeCounter (makeCounter_iter and makeCounter_rec) is a higher order function that returns another function inc, the increment function. Also, the value of base is fixed in the creation context of inc inside the makeCounter function. The inc function uses the value of base at a place in the code which is typically outside the lexical scope where base is defined. This is known as the closure feature of functional programming. In a typical object-oriented scenario, this effect is achieved using the builder design pattern.