### 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: interview

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 is not None else [])
      
    @classmethod
    def from_array(cls, arr):
        if arr:
            return Cons(arr[0], Cons.from_array(arr[1:]))
    
    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, 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):
        return cls(arr.pop(0), cls.from_array(arr)) if arr else None
    
    def filter(self, fn):
        return self.from_array([e for e in self.to_array() if fn(e)])
    
    def map(self, fn):
        return 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 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):
        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):
        return Cons(arr[0], Cons.from_array(arr[1:])) if arr else None

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

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

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):
        #TODO: convert a Python list to an algebraic list.
        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):
        #TODO: construct new algebraic list containing only elements
        #      that satisfy the predicate.
        al = list(filter(fn, self.to_array()))
        return self.from_array(al)
        
        
    def map(self, fn):
        #TODO: construct a new algebraic list containing all elements
        #      resulting from applying the mapper function to a list.
        head, tail = self.head, self.tail
        al = list(map(fn, self.to_array()))
            
        return self.from_array(al)