### Context and Definitions

You are in charge of developing a new cool JavaScript library that provides functionality similar to that of [Underscore.js](http://underscorejs.org/).

You have started by adding a new  **list data type** to your library. You came up with a design of a data structure that represents an [algebraic data type](http://en.wikipedia.org/wiki/Algebraic_data_type) as a pair of elements:

```python
class Cons:
  def __init__(self, head, tail):
    self.head = head
    self.tail = tail
```

You are pretty smart, because using this new data type, we can easily build a list of elements. For instance, a list of numbers:

```python
numbers = Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, None)))))
```

In a code review with your boss, you explained him how every *cons cell* contains a "value" in its head, and in its tail it contains either another cons cell or null. We know we have reached the end of the data structure when the tail is null.

So, your boss is pretty excited about this new data structure and wants to know if you will be able to build some more  functionality around it. In a demo you did this week for the rest of your team, in order to illustrate how this works, you showed them a method to transform a list of items of your list data type into a JavaScript array:

```python
  # added to the class implementation:
  def to_array(self):
    tail = self.tail
    new_tail = (tail.to_array() if tail is not None else [])
    return [self.head] + new_tail
```

And they were amazed when you simply did this:

```python
print(numbers.to_array())  # yields [1,2,3,4,5]
```

### The New Requirements

Now, the team is convinced that this is the way to go and they would like to build the library around this cool new data type, but they want you to provide a few more features for them so that they can start using this type in solving some real world problems.

You have been reading about a technique called  [applicative programming](http://quod.lib.umich.edu/s/spobooks/bbv9810.0001.001/1:15?rgn=div1;view=fulltext) which basically consists in applying a function to every element in a list.  So, you gave it some thought and you have decided to start adding features  like **filter**, **map** and **reduce**. Basically you want to provide equivalent functionality to that of JavaScript arrays and in the future even more.

So, you will now add:

 - [filter](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter?redirectlocale=en-US&redirectslug=JavaScript%2FReference%2FGlobal_Objects%2FArray%2Ffilter): create a new algebraic list containing only the elements that satisfy a predicate function. 
 - [map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter?redirectlocale=en-US&redirectslug=JavaScript%2FReference%2FGlobal_Objects%2FArray%2Ffilter) : create a new list in which every element is the result of applying a function provided as argument.
 - fromArray:  a convenient complementary method  that creates a list out of a JavaScript array.

For this Kata, the definition of `Cons` and the prototypal/class method `toArray`/`to_array`/`into_vec` are already loaded in your environment.

### Examples of Usage

```python
numbers = Cons.from_array([1,2,3,4,5])
numbers.filter(lambda x: x % 2 == 0).to_array()  # yields [2,4]
numbers.map(lambda x: x * x).to_array()  # yields [1,4,9,16,25]

digits = Cons.from_array(["1","2","3","4","5"])
integers = digits.map(int) \
                 .filter(lambda n: n > 3) \
                 .to_array()  # yields [4,5]
```

In other words:

 - The static method `Cons.fromArray` (or `from_array`, `from_iter`) produces `Cons(1, Cons(2, Cons(3, Cons 4, Cons 5, null)))))`.
  - Above filter creates a new list: `Cons(2, Cons(4, null))`.
 -  So does above map:  `Cons(1, Cos(4, Cons(9, Cons(16, Cons(25, null)))))`.

Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures
Skill types: Data structures

Starter code:
def __init__(self, head, tail):
	

Solutions:
class Cons:

	def __init__(self, head, tail):
		self.head = head
		self.tail = tail

	def to_array(self):
		return [self.head] + (self.tail.to_array() if self.tail is not None else [])

	@classmethod
	def from_array(cls, arr):
		if not arr:
			return None
		return Cons(arr.pop(0), Cons.from_array(arr) if arr else None)

	def filter(self, fn):
		return Cons.from_array(list(filter(fn, self.to_array())))

	def map(self, fn):
		return Cons.from_array(list(map(fn, self.to_array())))


class Cons:

	def __init__(self, value, tail):
		self.value = value
		self.tail = tail

	def to_array(self, lst=None):
		if lst is None:
			lst = []
		lst.append(self.value)
		if self.tail is not None:
			self.tail.to_array(lst)
		return lst

	@classmethod
	def from_array(cls, arr):
		head = None
		for x in reversed(arr):
			head = Cons(x, head)
		return head

	def filter(self, fn):
		if fn(self.value):
			return Cons(self.value, self.tail and self.tail.filter(fn))
		else:
			return self.tail and self.tail.filter(fn)

	def map(self, fn):
		return Cons(fn(self.value), self.tail and self.tail.map(fn))


class Cons:

	def __init__(self, head, tail):
		(self.head, self.tail) = (head, tail)
	to_array = lambda self: [self.head] + (self.tail.to_array() if self.tail is not None else [])
	from_array = classmethod(lambda cls, arr, i=0, v=None: None if not arr else v if i == len(arr) else cls.from_array(arr, i + 1, Cons(arr[len(arr) - 1 - i], v)))
	filter = lambda self, fn: self.from_array(list(filter(fn, self.to_array())))
	map = lambda self, fn: self.from_array(list(map(fn, self.to_array())))


class Cons:

	def __init__(self, head, tail):
		self.head = head
		self.tail = tail

	def to_array(self):
		return [self.head] + (self.tail.to_array() if self.tail else [])

	@classmethod
	def from_array(cls, arr):
		return cls(arr[0], cls.from_array(arr[1:])) if arr else None

	def filter(self, f):
		tail = self.tail.filter(f) if self.tail else None
		return Cons(self.head, tail) if f(self.head) else tail

	def map(self, f):
		return Cons(f(self.head), self.tail.map(f) if self.tail else None)


class Cons:

	def __init__(self, head, tail):
		self.head = head
		self.tail = tail

	def to_array(self):
		return [self.head] + (self.tail.to_array() if self.tail is not None else [])

	@classmethod
	def from_array(cls, arr):
		if arr:
			return Cons(arr[0], Cons.from_array(arr[1:]) if len(arr) > 1 else None)
		return None

	def filter(self, fn):
		if self.tail:
			return Cons(self.head, self.tail.filter(fn)) if fn(self.head) else self.tail.filter(fn)
		return self if fn(self.head) else None

	def map(self, fn):
		if self.tail:
			return Cons(fn(self.head), self.tail.map(fn))
		return Cons(fn(self.head), None)


class Cons:

	def __init__(self, head, tail):
		self.head = head
		self.tail = tail

	def to_array(self):
		return [self.head] + (self.tail.to_array() if self.tail is not None else [])

	@classmethod
	def from_array(cls, arr):
		c = None
		if len(arr) == 0:
			return c
		for i in range(len(arr) - 1, -1, -1):
			c = Cons(arr[i], c)
		return c

	def filter(self, fn):
		buf = self
		t = []
		while buf is not None:
			if fn(buf.head):
				t.append(buf.head)
			buf = buf.tail
		return Cons.from_array(t)

	def map(self, fn):
		buf = self
		t = []
		while buf is not None:
			t.append(fn(buf.head))
			buf = buf.tail
		return Cons.from_array(t)


class Cons:

	def __init__(self, head, tail=None):
		self.head = head
		self.tail = tail

	def to_array(self):
		return [self.head] + (self.tail.to_array() if self.tail is not None else [])

	@classmethod
	def from_array(cls, arr):
		if len(arr) == 0:
			return None
		E = cls(arr[0])
		e = E
		for i in range(len(arr) - 1):
			e.tail = cls(arr[i + 1])
			e = e.tail
		return E

	def filter(self, fn):
		al = list(filter(fn, self.to_array()))
		return self.from_array(al)

	def map(self, fn):
		(head, tail) = (self.head, self.tail)
		al = list(map(fn, self.to_array()))
		return self.from_array(al)