Creating the simplest data structures using functions in Python

Introduction : The summer before last, I discovered a great SICP book - reading only the first section of the book opened up a new world of functional programming for me. Anonymous functions, functions that return functions, higher order functions. In the second section of the book, the authors showed that it is possible with the help of functions alone to create different data structures, such as a pair, a list, or even trees! Today I would like to implement some of the ideas in this book in the Python programming language. Of course, only with the help of functions.

Start : Python is a great programming language that supports almost all programming paradigms. Python is easy to understand, and a basic knowledge of the language is enough to read this article. Also, do not be superfluous to view this article .

I. Creating a pair. What is a couple?
A pair is an ordered set that consists of two elements, presumably of different types. It is worth noting that in PL Python, a tuple (pair is a special case of a tuple) is a special type of data that is very often used and is created as follows: p = (a1, a2, .., an) . But since we agreed to use only functions, we will have to create our own implementation of the pair:

def make_pair(x,y): return lambda n: x if n==0 else y def first(p): return p(0) def second(p): return p(1) 

Wait a minute But make_pair returns a function, not a pair. In fact, the pair in our representation is the function, which takes any number as an argument, and returns the first element if the argument is 0, and the second in the opposite case. To increase the level of abstraction, we also created functions for accessing the elements of our pair: first and second . Make sure that our implementation of the pair works as it should:

  p = make_pair(5,6) first(p) #5 second(p) #6 p1 = make_pair('hello',6) first(p1) #'hello' 

Ii. List What is a list?

A list is an abstract data type that is an ordered set of values ​​in which a value can occur more than once.

Now we are implementing a coherent list - one of the possible implementations of the list.

The important list is a basic dynamic data structure in computer science, consisting of nodes, each of which contains both the actual data and one or two links ("bundles") to the next and / or previous list node

In fact, a coherent list can be represented as a pair, which consists of two values: the “head” of the list and its “tail”. For example, the list [1,2,3,4] can be represented as follows:

 l = make_pair(1,make_pair(2,make_pair(3,4))) first(l) #1 first(second(l)) #2 

Now add support for empty lists. An empty list is a list that contains no items. When accessing its elements, it must somehow report an error.

 def nil(): def closure(n): raise Exception return closure null = nil() first(null) #Exception second(null) #Exception def create_list(x): return make_pair(x,null) 

Unfortunately, the functions first and second are not intuitive functions of access to the elements of the list. It’s much more familiar to work with the head and tail functions.

 def head(l): return first(l) def tail(l): return second(l) 

Here it is worth remembering that in Python, functions are first class objects.
Therefore, the code can be greatly simplified:

 head = first tail = second 

The basic operation on the list is adding a new item to the head of the list:

 def add_to_list(l,x): return make_pair(x,l) 

Everything is extremely simple: we create a new list, the “head” of which is the new element, and the “tail” is the previous list.
You can stop here, because in fact we created a full-fledged data type - a list, but perhaps we should also consider traversing the list.

 def iterate_over_list(l,f): if l==null: return else: f(head(l)) iterate_over_list(tail(l),f) 

The simplest operation is to go through all the elements and call some function f to each element of the list. For example, using this function, you can display a list on the screen:

 def print_list(l): def put(n): print n iterate_over_list(l,put) l = create_list(5) l =add_to_list(l,6) l = add_to_list(l,7) print_list(l) #7 6 5 

')
How does the iterate_over_list function work ? It recursively applies the function f to the head of the list L, until L equals the empty list.
Now we implement the basic functional operations on lists:
map (l, f) is a function that translates a list into a new list, applying some function f to its elements.
filter (l, p) is a function that creates a new list that includes only those elements that correspond to a certain predicate p.
accumulate (l, op, initial) - more commonly known as reduce.

The _map function works recursively: if the list is empty, then we return an empty list, otherwise we return a new list whose head is the result of applying the function f to the first element of the list l, and the tail is the result of applying the function _map to the tail of the list l.

 def _map(l,f): if null_seq(l): return null else: return make_pair(f(head(l)),_map(tail(l),f)) l = make_list(5) l = add_to_list(l,6) l = add_to_list(l,7) l2 = _map(l,lambda n: n*n) iterate_over_list(l2,pr) # 49 36 25 def _filter(l,p): if null_seq(l): return null else: if p(head(l)): return make_pair(head(l),_filter(tail(l),p)) else: return _filter(tail(l),p) def accumulate(l,op,initial): if null_seq(l): return initial else: return accumulate(tail(l),op,op(initial,head(l))) #      accumulate from operator import add _sum = accumulate(l,add,0) 

And the final touch is the range function. If you have read this element, you will probably be able to implement this function yourself.


Instead of conclusion
Of course, no one will use such techniques in "real" programming, but I hope that this article will still be able to help someone to master the functional programming.