I have been reading the book Grokking Algorithms by Aditya Bhargava.
While the examples in the book are given in Python2, the concepts the book is presenting are language agnostic.
These blog posts are notes taken from exploration of the algorithms and ideas from the book.
Goal: Express a binary search in a functional style in Python.
(I'm not sure I succeeded!)
Noting this here thinking that I could use reduce to write a functional binary search function.
Free download: http://www.oreilly.com/programming/free/files/functional-programming-python.pdf
These reduce() expressions are awkward, but they also illustrate how powerful the function is in its generality: anything that can be computed from a sequence of successive elements can (if awkwardly) be expressed as a reduction.
The function functools.reduce() is very general, very powerful, and very subtle to use to its full power. It takes successive items of an iterable, and combines them in some way.
From Python documentation: https://docs.python.org/3.5/library/functools.html
Apply function of two arguments cumulatively to the items of sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the sequence. If the optional initializer is present, it is placed before the items of the sequence in the calculation, and serves as a default when the sequence is empty. If initializer is not given and sequence contains only one item, the first item is returned.
In [1]:
( # colors for logging display
BLUE,
GREEN,
YELLOW,
RED,
) = (
'blue',
'green',
'yellow',
'red',
)
In [2]:
# demonstration of reduce
# Thinking I could use with binary search
from functools import reduce
reduce(lambda x, y: (x, y), range(1, 10), 0)
Out[2]:
In [3]:
reduce(lambda x, y: (x, y), reversed(range(1, 10)), 0)
Out[3]:
In [4]:
import os
# dynamically get an objects attr without typing all the dots
# return join of path of os
reduce(getattr, ('path', 'join',), os)
Out[4]:
In [5]:
from random import choice
def sorted_random_numbers(limit=50):
"""Create a sorted collection of pseudorandom numbers of pseudorandom length with a minimum length of 10.
:limit: max length of list returned
"""
chosen = []
def random_number():
number = None
while number not in chosen:
number = choice(range(1000))
if number:
chosen.append(number)
return number
return sorted(random_number() for _ in range(10, choice(range(11, limit))))
In [6]:
number_lists = [sorted_random_numbers() for _ in range(10)]
# choose a random item to find in the list
lists_with_item = [(item, choice(item)) for item in number_lists]
In [7]:
import click
def echo(message, color):
"""Display a colored message."""
logger.info(click.style(''.join((' ', message)), fg=color))
In [8]:
import logging
import importlib
importlib.reload(logging) # IPython starts logging so have to reload
logger = logging.getLogger(__name__)
logging.basicConfig(level=logging.DEBUG)
echo('Logger is working.', YELLOW)
In [9]:
# view of the test data
SPACE = ' '
for list_, needle in lists_with_item:
echo(SPACE.join(("List to search:", repr(list_))), GREEN)
echo(SPACE.join(("Item to find:", str(needle))), RED)
In [10]:
def imperative_binary_search(list_, item):
"""Binary search algorithm in an imperative style.
Inspired by Grokking Algorithms: http://bit.ly/grokking-algorithms.
:list_: collection through which to search
:item: item for which to search in the collection
"""
if not list_:
raise ValueError('List is empty.')
low = 0
high = len(list_) - 1
while low <= high:
mid = (low + high) // 2 # python3 integer division
guess = list_[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
raise ValueError("{} not found.".format(item))
In [11]:
lists, items = zip(*lists_with_item)
assert [list_[imperative_binary_search(list_, item)]
for list_, item
in lists_with_item] \
== list(items)
echo('{} successfully found items {}'.format(imperative_binary_search, items), GREEN)
In [12]:
lists_with_item_empty_list = lists_with_item[:]
lists_with_item_empty_list.append(([], None))
try:
assert [list_[imperative_binary_search(list_, item)]
for list_, item
in lists_with_item_empty_list]\
== list(items)
except ValueError as e:
error = repr(e)
assert error == "ValueError('List is empty.',)"
echo(repr(e), YELLOW)
echo(repr(lists_with_item_empty_list[-1]), YELLOW)
In [13]:
lists_with_item_not_found = lists_with_item[:]
lists_with_item_not_found.append(([1, 3], 2))
try:
assert [list_[imperative_binary_search(list_, item)]
for list_, item
in lists_with_item_not_found]\
== list(items)
except ValueError as e:
error = repr(e)
assert error == "ValueError('2 not found.',)"
echo(repr(e), YELLOW)
echo(repr(lists_with_item_not_found[-1]), YELLOW)
In [14]:
# calculate the midpoint index of list
mid = lambda list_: len(list_) // 2
In [15]:
# split list into left and right halves using [:] slicing
splits = lambda list_: (list_[:mid(list_)], list_[mid(list_) + 1:])
In [16]:
guess = lambda list_: list_[mid(list_)]
In [17]:
# Is the guess the item?
is_item = lambda list_, item: guess(list_) == item
In [18]:
# return the left half if guess is > item else return the right half
sublist = lambda item, list_: splits(list_)[0] if guess(list_) > item else splits(list_)[1]
In [19]:
# check list
def error_check(list_, message):
if not list_:
raise ValueError(message)
In [20]:
def search(item, list_):
error_check(list_, "List is empty.")
while not is_item(list_, item):
list_ = sublist(item, list_)
error_check(list_, "Item not found.")
return True
In [21]:
# test substrate
list_ = sorted_random_numbers()
item = choice(list_)
echo(str(list_), BLUE)
echo(str(item), BLUE)
In [22]:
found = search(item, list_)
for item in (item, list_, found):
echo(repr(item), GREEN)
In [30]:
tests = tuple(search(item, list_) for list_, item in lists_with_item)
echo(repr(tests), GREEN)
assert all(tests)
In [25]:
try:
search(0, list_)
except ValueError as e:
echo("ValueError expected.", GREEN)
echo(repr(ValueError(e)), GREEN)
In [26]:
try:
search(0, list())
except ValueError as e:
echo("ValueError expected.", GREEN)
echo(repr(ValueError(e)), GREEN)