[Exercise] A functional programming library

Joe

This one is longer than the traditional exercises we post here and is meant to be a gentle introduction to the Functional Programming paradigm. But first some (uber simplified) theory:

Manipulating functions
Most of you are already familiar with the following concepts and can easily skip it and start programming. For the rest of you who are completely new to this, a small introduction.

If you come from an exclusive background in C, C++, C# or Java (and to a large extent PHP), this should help you understand the most recent evolutions of your language.

1- Higher order functions: functions vs data

You may have learned that your code consists of two things: The data you are manipulating (usually organized in some sort of data structure, like a dictionary or a list), and the functions you are applying on these structures.

One of the main features of functional programming is that functions are treated exactly like data, and can be manipulated and modified dynamically at run-time[*]. You will sometimes hear the term higher-order functions. A HO function is a function that accepts another function as argument and/or returns another function. A dead simple example in python:

def say_hello():
    print 'hello'

# The argument f is a function
def twice(f):
    """ calls the function f two times. For example

    >>> twice(say_hello)
    hello
    hello
        
    """
    f()
    f()

[*] - Note that Lisp, one of the first functional-flavored languages, stretches this concept to the extreme.[/i]

2 - Iterables

When I say iterables, I mean any collection of data that can be iterated over. This could mean, for instance, an array, a linked list, a stack or the keys of a dictionary. One way to look at it is to consider iterable as a super class (or an interface) for all these data containers.

If you're familiar with iterators, then it's the preferred way to do this exercise. If not, you could work on any list of elements. For example:
- any of Vector, ArrayList or Linked Lists in C++, C# and Java.
- Linked Lists in C. To make it easier, consider a linked list of integers.
- Arrays in PHP, Perl and Ruby.
- Lists in Python.
- Tables in Lua.
- ...

Exercise
The goal of this exercise is to write a small library adding functional flavor to your favorite language.
Note that most familiar languages here on the forum, will implement them natively (C is the only one I can think of which doesn't); obviously the goal is to reimplement them, so do not use them in your solutions.

Higher Order functions

- map(func, iter)
returns an iterable containing func(x) for each x in iter.
e. g: map(double, [1, 2, 3]) -> [2, 4, 6]

- filter(func, iter)
returns an iterable containing each x in iter, such as func(x) == True
e. g: filter(is_even, [1, 2, 3, 4]) -> [2, 4]

- head(iter)
returns the first element of the iterator
e. g: head([1, 2, 3]) -> 1

- tail(iter)
returns the iterable minus its first element
e. g: tail([1, 2, 3]) -> [2, 3]

- range(start, end)
returns an iterable containing all the integers from start to end-1
e. g: range(3, 8) -> [3, 4, 5, 6, 7]

Operators
This idea is taken from Python.
Write a function that behaves like each of the following operators:

+, *, -, /, %
==, !=, >, >=, <, <=
or, and, not

Bonus points (intermediate)

Write the HO function accumulate:

- accumulate(func, iter, initial)
returns a single value obtained by successively calling func
on the elements of the iterator (and starting with the initial value).

e. g: accumulate(operator.add, [1, 2, 3], 10) -> 16
explanation:
- operator.add is the function that takes two args and returns their sum.
- 16 is therefore the sum of all the elements plus the initial value(10).
- 1 + 2 + 3 + 10 = 16

Question:
What happens if func is not associative? What is the result of accumulate(operator.divide, [1, 2, 3, 4, 5], 1)?
How can you solve that ambiguity?

Bonus points (difficult)

How can you make the function range() lazily evaluated, without using yield or other builtin mechanisms?

Ra8

You mean something like this ?
If this is it, i'll post the others soon, if not please let me know

#include <iostream>
#include <vector>

using namespace std;
int doubleMe(int x)
{
    return x*2;
}
vector<int> map(int (*f)(int), vector<int> a)
{
    for(int i=0;i<a.size();i++)
    {
        a[i]=f(a[i]);
    }
    return a;
}
int main()
{
    vector<int> a(1,1);
    a.push_back(2);
    a.push_back(3);
    a=map(doubleMe,a);
    for(int i=0;i<a.size();i++)
    {
        cout << a[i] <<endl;
    }
    return 0;
}

EDIT:
ok then:
map:

template <class T>
T doubleMe(T x)
{
    return x*2;
}
template <class T>
vector<T> map(T (*f)(T), vector<T> a)
{
    for(int i=0;i<a.size();i++)
    {
        a[i]=f(a[i]);
    }
    return a;
}

filter:

template <class T>
bool isEven(T x)
{
    return !(x%2);
}
template <class T>
vector<T> filter(bool (*f)(T), vector<T> a)
{
    vector<T> r(0);
    for(int i=0;i<a.size();i++)
    {
        if(f(a[i]))
            r.push_back(a[i]);
    }
    return r;
}

head and tail:

template <class T>
T head(vector<T> a)
{
    return a[0];
}

template <class T>
T tail(vector<T> a)
{
    return a[a.size()-1];
}

range:

template <class T>
vector<T> range(T s, T e)
{
    vector<T> r(0);
    for(int i=s;i<e;i++)
        r.push_back(s++);
    return r;
}

The + operator:

template <class T>
T add(T x1, T x2)
{
    do
    {
        x1=x1^x2;
        x2=((x1^x2)&x2)<<1;
    }while(x1&x2);
    return x1^x2;
}

I'll continue later

about the accumulate function...
in your example operator.add
What two arguments?
is it:
first iteration: 1+2 =3
second: 3+3 =6
third: 6+10=16
?

Joe

@Ra8: Yes this is the general idea.

A few comments, though.

- I don't like that you limit your containers to int only.
- Function pointers seem inherently fragile to use. How about using something like this?

Of course these remarks are just opinions and you're free to work on the exercise as you please.

Also, I'm not by any chance a C++ expert. Maybe using function pointers is better than the method I suggest. I guess it's up to you to tell us which approach is better :)

NuclearVision

In python i was able to define those:

## HOs
def map(func, iter):
    mapped = []
    for i in in iter:
        mapped.append(func(i))
    return mapped

def filter(func, iter):
    filtered = []
    for i in iter:
        if func(i)==True:
            filtered.append(i)
    return filtered

def head(iter):
    return iter[0]

def tail(iter):
    iter.pop(0)
    return iter

def range(start, end):
    range = []
    i = start
    while i!=end+1:
        i+=1
        range.append(i)
    return range

## Bonus
from operator import truediv
def appstart(iter, head):
    app = []
    app.append(head)
    for i in iter:
        app.append(i)
    return app
def accumulate(func, iter, initial):
    return reduce(func, appstart(iter, initial))
print accumulate(truediv, [1,2,3,4,5], 1)

@rahmu your accumulate function outputs 0.00833333333333.
By the way, the last bonus question is the xrange(start, end) function i will try to work on it ASAP.

Joe

@Ra8: This is it. A few remarks:

1 - your implementation of tail is faulty. Take another look at the example I gave.

2 - The add function can use "+". Something like this:

template <typename T>
T add (T a, T b)
{ return a + b; }

It's not very challenging to write, but highly useful to use. The most common example is to use it coupled with accumulate. For instance:

sum(iter) == accumulate(add, iter, 0)

This is not possible to write without the add function.

That being said, your implementation is far sexier than mine, and if you manage to implement all the operators that way, we'd all be delighted :)

3 - You are right to notice that the order of evaluation is important for accumulate. I'll try to answer you without giving too much away. The goal of the exercise is to think like a library/module designer and decide how can you present both behaviors to the user in a clean and understandable way.

(For the record, this problem has already been solved, some 50 years ago. But thinking like a library designer is a great exercise and you should do it. I'll post the solution soon.)

Joe

@NuclearVision: Very good :)

- you have a (stupid) syntax error in your filter function.
- Your answer to the accumulate question is completely wrong :(

1- appstart can be written like this:

def appstart(iter, head):
    return [head] + iter

(but this is just a detail).

2- The real mistake, you wrongfully assumed that the accumulate I defined and Python's reduce are the same function. (not to mention that I specified avoiding the existing builtins specifically).

The goal of the intermediate question is to make you realize that reduce() is just one flavor of accumulate, and your goal as a library designer is to present the user the most general solutions possible.

Here's a hint I shouldn't be giving you: There's a second version of accumulate which returns the following result:

>>> accumulate2(truediv, [1, 2, 3, 4, 5], 1)
1.875

- One last remark: avoid using the word iter as a variable name in Python. It's a builtin function, and naming conflicts can lead to extremely annoying confusions.

Good job so far, waiting for the rest!

Ra8

tail:

template <class T>
vector<T> tail(vector<T> a)
{
    a.erase(a.begin());
    return a;
}

accumulate:

template <class T>
T accumulate(T (*f)(T,T),vector<T> a, T n)
{
    T r=n;
    for(int i=0;i<a.size();i++)
    {
       r=f(a[i],r);
    }
    return r;
}

Multiply using the add function above

template <class T>
T mul(T x1, T x2)
{
    int i=0;
    T r=0;
    while(x1>>i)
    {
        int t=(x1&(1<<i))?-1:0;
        r=add(r,(t&x2)<<i);
        i=add(i,1);
    }
    return r;
}

Joe

I started the exercise in Lua. Note that all tables are considerd to behave like an array. I have not considered the case of hashmaps.

function map(func, t) 
   local newtable = {}
      
   for i, v in ipairs(t) do
      newtable[i] = func(v)
   end

   return newtable
end


function filter(func, t)
   local newtable = {}

   for _, v in ipairs(t) do
      if func(v) then
         table.insert(newtable, v)
      end
   end

   return newtable
end


function head(t)
   return t[1]
end

function tail(t)

   if # t <= 1 then
      return nil
   end
   
   local newtable = {}

   for i, v in ipairs(t) do
      if i > 1 then
         table.insert(newtable, v)
      end
   end

   return newtable
end 

function range(rstart, rend)
   local newtable = {}
   local i = rstart

   for i = rstart, rend-1 do
      table.insert(newtable, i)
   end

   return newtable
end

I'll post the solution to the intermediate challenge tonight.
As for the difficult one, I will try to solve it using Lua's Coroutines.

NuclearVision

@rahmu i was hoping to see the intermediate challenge solved using python. Though i still don't get it.
Accumulation somehow needs addition(sum), because you're accumulating. But what's wrong with the initial value?
Again, i hope to see the challenge solved in python.

Thanks for your feedback rahmu, i really appreciate it.
And i would like to see those problems solved in haskell. It is the sexiest language i have seen so far.
I think arithma knows best about it, where are you arithma??

Joe

Intermediate challenge (in Python, to help NuclearVision)

The challenge is to write accumulate() such as:

accumulate(operator.add, [1, 2, 3], 10) == 16

The challenge consisted of realizing there are 2 ways to do it:

def accumulate(func, L, init):

    res = init
    for i in L:
        res = func(res, i)
    
    return res

def accumulate2(func, L, init):

    res = init
    for i in L:
        res = func(i, res)

    return res

In our case, accumulate and accumulate2 are equivalent, but only because addition is associative.
The two functions behave radically differently in other cases. Proof in hand:

>>> accumulate(operator.truediv, [1, 2, 3, 4, 5], 1)
0.00833333333333
>>> accumulate2(operator.truediv, [1, 2, 3, 4, 5], 1)
1.875

In a more formal way, accumulate can be called fold (if you ever come across the terms "fold", "accumulate", "reduce" they basically refer to similar things). Actually, accumulate represents a left fold and accumulate2 represents a right-fold.

As a library designer, you want to give both possibilities to your user.

Let's compare how Python and Haskell do this:

Haskell
Haskell may be sexy (?), it doesn't take any risk. It has separate foldr and foldl functions.

For more info (and far better explanations), you should definitely take a look at the Fold article in the Haskell wiki.

Python
Up until Python 2, the standard library had one folding call: reduce().

reduce is similar to a left fold, with an optional init value. If init is not supplied, the first element of the iterable will behave as the initial value.
However, it should be noted that Python has always had some mixed feelings about all these functional tools. The language loves iterators, generators and comprehensions, but despises the functions we've been working on (map, filter, reduce, ...).

As a result, reduce has been removed from the standard library (but is still available in the functools module).

Solution to the challenge + new challenge

The goal of the challenge was to make you realize that there are two kinds of folding (accumulating) and that you should present both to the user.
At this point you should be wondering why Python does not offer a right fold solution in its library. The reason is simple: it is very easy to express a right fold in terms of reduce().

The Python Extra Challenge consists of this: write a right fold using only a reduce call.

NuclearVision

Thanks for the explanation rahmu, I assume I have done it wrong because the function was not associative, so we must initiate from two sides,left and indeed, right.

Thanks again, rahmu.
I love the way you code mate.

arithma

This is a first attempt at twisting iterators. I have some issues regarding my use of templates, especially in the case where I'd need to pass a FilterIterator to another FilterIterator:

#include <iostream>
#include <vector>
#include <algorithm>

template <class Iterator, class Predicate>
class FilterIterator {
    Predicate _f;
    Iterator _i;
    Iterator _e;
public:
    FilterIterator(Iterator i, Iterator e, Predicate f) : _i(i), _e(e), _f(f) {
        _i = std::find_if(_i, _e, _f);
    }
    
    FilterIterator operator++(int){
        _i++;
        _i = std::find_if(_i, _e, _f);
        return *this;
    }
    
    typename Iterator::value_type operator*(){
        return *_i;
    }
    
    bool isEnd(){
        return _i == _e;
    }
};

struct IsOdd{
    bool operator()(int x){
        return (x%2!=0);
    }
};

int main(int argc, const char * argv[])
{
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    
    FilterIterator<std::vector<int>::iterator, IsOdd> itr = FilterIterator<std::vector<int>::iterator, IsOdd>(v.begin(), v.end(), IsOdd());
    
    while(!itr.isEnd()){
        std::cout << *itr << std::endl;
        itr++;
    }

    return 0;
}

Joe

Earlier today, I wrote a very simple implementation of xrange (the lazily evaluated range function) using Lua's Coroutines.

xrange = coroutine.create(
   function (rstart, rend)
      while rstart < rend do
          coroutine.yield(rstart)
          rstart = rstart + 1
      end
   end)

This can be iterated over with something like this:

while coroutine.status(xrange) ~= 'dead' do
   errorfree, value = coroutine.resume(xrange, 2, 7)
   print (value)
end

A lot more should be done in order to make this usable. My first instinct is to reimplement what I already know, namely some sort of iteration mechanism similar to Python's.

Speakin of which, nobody cared about the Python foldr challenge I added subsequently. So here's the answer:

def foldr(func, L, init) = reduce(lambda (x, y): func(y, x), reversed(L), init)

@arithma: technically, you should not be using find_if. Actually the whole point of the exercise was to simply reimplement it. But I see what you did there, and it's far more interesting. It lead me to discover how iterators are managed in C++ and all the operator methods and whatnots.

What's the issue with the templates? Isn't a FilterIterator just another kind of Iterator?

xterm

rahmu wroteEarlier today, I wrote a very simple implementation of xrange (the lazily evaluated range function) using Lua's Coroutines.

That coroutine.yield does 99% of the work. Isn't that considered a builtin mechanism?

Joe

xterm wroteThat coroutine.yield does 99% of the work. Isn't that considered a builtin mechanism?

Absolutely, I did not mean this as a definite answer to the problem.

However I believe that it should be easier to jump from Lua's Coroutines to a more general solution using threads. I honestly don't know if this idea could lead to a solution and I hope I'll find some time to explore this soon.

xterm

Albeit a draf, incomplete and not exhaustive, i started playing around with my own implementation of Underscore.js functions.

My intention is to complete the 'Collections' and 'Arrays' functions.

P.S.: There's a bug in reduce right.

Joe

@xterm: I was reading an old discussion of ours about closures, when it hit me that it could be used simply here. Here's my lazy range() (in Lua):

function range (rstart, rend)
   a = rstart-1

   function xrange()
      a = a + 1
      if a < rend then
	 return a
      else
	 return "End of iterator" --# you could raise an exception
      end
   end

   return xrange
   
end

How to use it:

> f = range(10, 15)
> a = f()
> while a ~= "End of iterator" do
>> print(a)
>> a = f()
>> end
10
11
12
13
14
>