Carlos Cordoba avatar Carlos Cordoba committed 51d7b32

Change package name to funckit

Comments (0)

Files changed (23)

 README
 setup.py
 test.py
-functional/__init__.py
-functional/datastruct.py
-functional/functional_cw.py
-functional/functional_goopy.py
-functional/functional_mathematica.py
-functional/functional_xoltar.py
-functional/lazy.py
-functional/operators.py
-functional/partial.py
+funckit/__init__.py
+funckit/datastruct.py
+funckit/cw.py
+funckit/goopy.py
+funckit/mathematica.py
+funckit/xoltar.py
+funckit/lazy.py
+funckit/operators.py
+funckit/partial.py
 tests/__init__.py
 tests/support.py
-tests/test_functional.py
+tests/test_funckit.py
 Introduction
 ============
 
-The aim of functional is to provide Python users with a good set of tools
-to do functional programming. It contains the work of Collin
-Winter, author of the functional module, Google's goopy project and
-the Xoltar module by Bryn Keller.
-Besides it adds several useful functions found in Mathematica and Ocaml.
+funckit: A kit for functional programming in Python.
 
-You can find functions such as fold_left, fold_right, nest, as well
-as well as binary operators of various sorts that make function application easier.
-functional also includes sane versions of the Python builtins map() and filter(),
-written without the weird semantics of the builtin versions.
+funckit provides Python users with a more or less complete kit of functional
+programming constructs, such as scanr and scanl, several map versions,
+currying, composition, list flattening, as well as a couple of infix
+operators to make function applications easier. It gathers functions found
+in Google's old goopy module, Collin Winters' functional module and Bryn
+Keller's excellent Xoltar module. It also adds several functions found
+in Haskell, Ocaml and Mathematica.
 
 Installation
 ============
 Documentation
 =============
 
-Please refer to the project's website: http://bitbucket.org/juliusc/functional/
+Please refer to the project's website: http://bitbucket.org/ccordoba12/funckit/
 
 Copyright/License
 =================

funckit/__init__.py

+"""
+This modules provides commonly-used tools for functional programming.
+"""
+
+from datastruct import *
+from cw import *
+from goopy import *
+from mathematica import *
+from xoltar import *
+from lazy import *
+from operators import *
+from partial import *
+#################################################################
+### The C version of partial originally by Hye-Shik Chang <perky@FreeBSD.org>
+### with adaptations by Raymond Hettinger <python@rcn.com>
+### translated into Python by Collin Winter <collinw@gmail.com>
+###
+### All other function definitions translated to Python by
+### Collin Winter from the Haskell originals found in the
+### Haskell 98 Report, edited by Simon Peyton-Jones <simonpj@microsoft.com>
+###
+### With modifications and additions by Carlos Cordoba <ccordoba12@gmail.com>
+###
+### Copyright (c) 2004-2006 Python Software Foundation.
+### All rights reserved.
+#################################################################
+
+# TODO: Change the name of this package to haskell.py. Change
+# the names of fold_{left, right}_list to the haskell ones
+
+import itertools as it
+
+### fold_left
+#################################################################
+fold_left = reduce
+foldl = reduce
+
+### fold_right
+#################################################################
+def _foldr(func, itr, base):
+    try:
+        first = itr.next()
+        if base is None:
+            itr, peek = it.tee(itr)
+            try:
+                peek.next()
+            except StopIteration:
+                return first
+    except StopIteration:
+        return base
+
+    return func(first, _foldr(func, itr, base))
+
+def fold_right(func, sequence, start=None):
+    """
+    Like reduce (a.k.a fold_left), but starts from the end of the sequence and
+    works back towards the beginning.
+    For example:
+    fold_right(f, [1, 2, 3]) is equivalent to f(1, f(2, 3))
+    and
+    fold_right(f, [1, 2, 3], 0) is equivalent to f(1, f(2, f(3, 0)))
+    
+    Parameters
+    ----------
+    func : callable
+        A function to fold over the sequence
+    sequence : any sequence
+        Sequence whose elements one wants to fold
+    start : element, optional
+        If start is present, it is placed before the items of the sequence in
+        the calculation, and serves as a default when the sequence is empty.
+    
+    Returns
+    -------
+    An element according to the func used and the iterable.
+    
+    Notes
+    -----
+    It's much faster to use a start element than not to use it (perhaps 3 times
+    faster or more).
+    
+    Examples
+    --------
+    >>> from operator import sub
+    >>> fold_right(sub, [1, 2, 3])
+    2
+    >>> fold_right(sub, [1, 2, 3], 1)
+    1
+    >>> fold_left(sub, [1, 2, 3], 1)
+    -5
+    """
+    if not callable(func):
+        raise TypeError("First argument to fold_right must be callable")
+    
+    sequence = iter(sequence)
+    return _foldr(func, sequence, start)
+    
+foldr = fold_right
+
+### scanl
+#################################################################
+
+def _scanl(func, itr,  base):
+    """
+    In Haskell:
+    
+    scanl        :: (a -> b -> a) -> a -> [a] -> [a]
+    scanl f q xs =  q : (case xs of
+                              [] -> []
+                            x:xs -> scanl f (f q x) xs)
+    """
+    if base is not None:
+        yield base
+    else:
+        base = itr.next()
+        yield base
+        
+    for o in itr:
+        base = func(base, o)
+        yield base
+    raise StopIteration
+
+def fold_left_list(func, sequence, start=None):
+    """
+    Produce an iterator of the successively folded values of a sequence,
+    starting from the left.
+    For example:
+    fold_left_list(f, [1, 2, 3], 0) is equivalent to
+    [0, f(0, 1), f(f(0, 1), 2), f(f(f(0, 1), 2), 3)]
+    
+    Parameters
+    ----------
+    func : callable
+        A function to fold over the iterable
+    sequence : Any sequence
+        Sequence whose elements one wants to fold
+    start : element, optional
+        If start is present, it is placed before the items of the sequence in
+        the calculation, and serves as a default when the sequence is empty.
+    
+    Returns
+    -------
+    An iterator of folded elements according to the func used and the sequence.
+    
+    Examples
+    --------
+    >>> from operator import add, sub
+    >>> list(fold_left_list(add, [1, 2, 3]))
+    [1, 3, 6]
+    >>> list(fold_left_list(sub, [1, 2, 3], 1))
+    [1, 0, -2, -5]
+    """
+    if not callable(func):
+        raise TypeError("First argument to fold_left_list must be callable")
+    
+    return _scanl(func, iter(sequence), start)
+   
+scanl = fold_left_list
+
+### scanr
+#################################################################
+
+def _scanr(func, x_xs, q0):
+    """
+    In Haskell:
+    
+    scanr             :: (a -> b -> b) -> b -> [a] -> [b]
+    scanr f q0 []     =  [q0]
+    scanr f q0 (x:xs) =  f x q : qs
+                         where qs@(q:_) = scanr f q0 xs
+    """
+    try:
+        # Handle the empty-list condition
+        x = x_xs.next()
+        if q0 is None:
+            x_xs, peek = it.tee(x_xs)
+            try:
+                peek.next()
+            except StopIteration:
+                yield x
+                raise StopIteration
+    except StopIteration:
+        yield q0
+        raise StopIteration
+
+    qs = _scanr(func, x_xs, q0)
+
+    q = qs.next()
+    yield func(x, q)
+
+    # this is the ": qs" from the Haskell definition
+    yield q
+    while True:
+        if q0 is None:
+            n = qs.next()
+            if n is None:
+                break
+            yield n
+        else:
+            yield qs.next()
+
+def fold_right_list(func, sequence, start=None):
+    """
+    Produce an iterator of the successively folded values of a sequence,
+    starting from the right.
+    For example:
+    fold_right_list(f, [1, 2, 3], 0) is equivalent to
+    [f(1, f(2, f(3, 0))), f(2, f(3, 0)), f(3, 0), 0]
+    
+    Parameters
+    ----------
+    func : callable
+        A function to fold over the iterable
+    sequence : Any sequence
+        Sequence whose elements one wants to fold
+    start : element, optional
+        If start is present, it is placed before the items of the sequence in
+        the calculation, and serves as a default when the sequence is empty.
+    
+    Returns
+    -------
+    An iterator of folded elements according to the func used and the sequence.
+    
+    Examples
+    --------
+    >>> from operator import add
+    >>> list(fold_right_list(add, [1, 2, 3]))
+    [6, 5, 3]
+    >>> list(fold_right_list(add, [1, 2, 3], 0))
+    [6, 5, 3, 0]
+    """
+    if not callable(func):
+        raise TypeError("First argument to scanr must be callable")
+    
+    return _scanr(func, iter(sequence), start)
+        
+scanr = fold_right_list
+
+### flip
+################################################################
+
+def flip(func):
+    """
+    flip causes a function to take its non-keyword arguments in reverse order.
+    The returned function is a wrapper around the original one that makes
+    this happen.
+    
+    Parameters
+    ----------
+    func : callable
+        A function to reverse its args
+    
+    Returns
+    -------
+    A function whose args are in reversed order from the original one
+    
+    Examples
+    --------
+    >>> from operator import sub
+    >>> sub(4,5)
+    -1
+    >>> flip(sub)(4,5)
+    1
+    """
+    if not callable(func):
+        raise TypeError("First argument to flip must be callable")
+    
+    def flipped_func(*args, **kwargs):
+        return func(*reversed(args), **kwargs)
+    return flipped_func
+
+### id
+################################################################
+
+def id(obj):
+    """
+    The identity function. id(obj) returns obj unchanged.
+    
+    Examples
+    --------
+    >>> obj = object()
+    >>> id(obj) is obj
+    True
+    """
+    return obj
+
+### filter
+################################################################
+    
+def filter(function, iterable):
+    """
+    Applies function to each element of iterable, returning a list
+    of those elements where function returned True. Basically, this
+    is like the builtin filter, except that functional.filter() treats
+    subclasses of str/tuple/unicode correctly, and that filter()'s
+    return type is always list.
+    
+    Parameters
+    ----------
+    func : callable
+        A function used to filter values of the iterable
+    iterable : Any sequence
+        Sequence whose elements one wants to filter
+    
+    Returns
+    -------
+    It always returns a list
+    """
+
+    if function is bool:
+        return [x for x in iterable if x]
+
+    return [x for x in iterable if function(x)]

funckit/datastruct.py

+### Dictionary and sequence functions 
+
+## Copyright (C) 2002 Bryn Keller
+
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## Lesser General Public License for more details.
+
+## You should have received a copy of the GNU Lesser General Public
+## License along with this library; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+__version__ = "1.0.0"
+
+from operator import concat
+
+def mapdict(itemfunc, dictionary):
+    """
+    Much like the builtin function 'map', but works on dictionaries.
+    *itemfunc* should be a function which takes one parameter, a (key,
+    value) pair, and returns a new (or same) (key, value) pair to go in
+    the dictionary.
+    """
+    return dict(map(itemfunc, dictionary.items()))
+
+
+def filterdict(itemfunc, dictionary):
+    """
+    Filters a dictionary like 'filter' filters a list. *itemfunc*
+    should be a function which takes two parameter, a(key, value) pair
+    and returns 1 if the pair should be in the new dictionary,
+    0 otherwise.
+    """
+    return dict(filter(itemfunc, dictionary.items()))
+
+def invertdict(dictionary):
+    """
+    Takes a dictionary and returns a new one, with the keys and values
+    exchanged.
+    """
+    return mapdict(lambda (key, value):(value, key), dictionary)
+
+### list/sequence functions
+class Unsupplied:
+    pass
+
+from goopy import some
+def none_of(func,  sequence):
+    """
+    none_of(func, sequence)
+    Returns True if for every element in sequence, func returns False.
+    """
+    return not some(func,  sequence)
+
+def head(sequence):
+    """
+    Returns the first element of a sequence.
+    """
+    return sequence[0]
+
+def tail(sequence):
+    """
+    Returns the slice of *sequence* containing all elements after the first.
+    """
+    return sequence[1:]
+
+def last(sequence):
+    """
+    Returns the last element of a sequence
+    """
+    return sequence[-1]
+
+def dropWhile(func, seq):
+    """
+    Returns a copy of *seq*, removing all the items for which *func*
+    returns true, until an item is reached which *func* returns false
+    for. Example:
+    >>> lessThanFive = curry_function(operator.lt, Blank, 5)
+    >>> dropWhile(lessThanFive, [1, 2, 3, 7, 2 ,1])
+    [7, 2, 1]
+    >>>    
+    """
+    res = []
+    dropping = 1
+    for thing in seq:
+        if dropping:            
+            if not func(thing):
+                dropping = 0
+        if not dropping:
+            res.append(thing)
+    return res
+
+def takeWhile(func, seq):
+    """
+    Returns a copy of *seq*, up until the point in the sequence where
+    *func* returns false.
+    Example:
+    >>> lessThanFive = curry_function(operator.lt, Blank, 5)
+    >>> takeWhile(lessThanFive, [1, 2, 3, 7, 2 ,1])
+    [1, 2, 3]
+    >>>    
+    """
+    res = []
+    for thing in seq:
+        if not func(thing):
+            break
+        res.append(thing)
+    return res
+
+def concatMap(func, seq):
+    """
+    Maps *func* over *seq*, and concatentates the resulting list.
+    """
+    return reduce(concat, map(func, seq))
+
+def unzip(seq):
+    """
+    Takes a list of tuples and returns a list of lists of the component parts
+    of the tuples.
+    Example:
+    >>> unzip([(1,2,3), (4,5,6), (7,8,9)])
+    [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
+    >>>    
+    """
+    res = []
+    sample = seq[0]
+    for thing in sample:
+        res.append([])
+    for item in seq:
+        for i in range(len(item)):
+            res[i].append(item[i])
+    return res
+
+def zipWith(func, *seqs):
+    """
+    Like zip, but applies func to the tuples instead of just returning the
+    tuples.
+    Example:
+    >>> zipWith(operator.add, [1, 2, 3], [1, 2, 3])
+    [2, 4, 6]
+    >>>    
+    """
+    def mapper(thing):
+        return func(*thing)
+    return map(mapper, zip(*seqs))
+# -*- coding: utf-8 -*-
+
+# Copyright (c) 2005, Google Inc.
+# All rights reserved.
+# 
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+# 
+#     * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#     * Redistributions in binary form must reproduce the above
+# copyright notice, this list of conditions and the following disclaimer
+# in the documentation and/or other materials provided with the
+# distribution.
+#     * Neither the name of Google Inc. nor the names of its
+# contributors may be used to endorse or promote products derived from
+# this software without specific prior written permission.
+# 
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+# Copyright (c) Carlos Córdoba 2009
+# Various additions and modifications
+
+"""
+Handy things for functional style programming.
+"""
+
+import math as _math
+
+def some(f, lst):
+  """some(f, lst) -> true if F applied to some element of LST is true"""
+  
+  for x in lst:
+    if f(x):
+      return 1
+  return 0
+
+def every(f, lst):
+  """every(f, lst) -> true if F applied to every element of LST is true"""
+  
+  for x in lst:
+    if not f(x):
+      return 0
+  return 1
+
+def find(p, lst, start=0):
+  """find(p, lst, start)
+
+  Returns the first index i (>= START) where P(LST[i]) is true or
+  -1 if there is none.
+  """
+  
+  for i in xrange(start, len(lst)):
+    if p(lst[i]):
+      return i
+
+  return -1
+
+def _remove_unhashable_duplicates(lst, key):
+  result = []
+  if key == None:
+    for v in lst:
+      if v not in result:
+        result.append(v)
+  else:
+    seen_keys = []
+    for v in lst:
+      this_key = key(v)
+      if this_key not in seen_keys:
+        result.append(v)
+        seen_keys.append(this_key)
+  return result
+  
+def remove_duplicates(lst, key=None):
+  """
+  Returns a list equivalent to SEQ with repeated elements removed.
+  (The first occurence of each value is retained.  Note that this is the
+   opposite of the Common Lisp default behavior.)
+
+  If KEY is provided, then repeats are detected by comparing KEY(ELEMENT)
+  for each element.
+  """
+  
+  d = {}
+  result = []
+  if key == None:
+    for v in lst:
+      try:
+        if not d.has_key(v):
+          result.append(v)
+          d[v] = 1
+      except TypeError:
+        return _remove_unhashable_duplicates(lst, key)
+  else:
+    for v in lst:
+      thiskey = key(v)
+      try:
+        if not d.has_key(thiskey):
+          result.append(v)
+          d[thiskey] = 1
+      except TypeError:
+        return _remove_unhashable_duplicates(lst, key)
+  return result
+
+def intersection(a, b):
+  """
+  intersection(a, b) -> list of items in both A and B
+
+  The order of the result items is unspecified.
+  
+  If all items are hashable, then this algorithm is
+  O(size(a) + size(b)); otherwise, it is O(size(a) * size(b))
+  """
+  
+  try:
+    # Try using a dictionary.
+    d = {}
+    for x in b:
+      d[x] = 1
+    c = [x for x in a if d.has_key(x)]
+  except TypeError:                     # really want HashError
+    c = [x for x in a if x in b]
+  return c
+
+def list_classify(f, lst):
+  """Given function F and list F, return tuple (matched, nonmatched),
+  where matched is a list of all elements E for which F(E) is true, and
+  nonmatched the remainder.
+  """
+  
+  matched = []
+  nonmatched = []
+  for e in lst:
+    if f(e):
+      matched.append(e)
+    else:
+      nonmatched.append(e)
+  return matched, nonmatched
+
+def reverse(lst):
+  """reverse(lst) -> reversed copy of LST"""
+  
+  lst = lst[:]
+  lst.reverse()
+  return lst
+  
+def first_difference(lst):
+  """first_difference(lst) -> the first differences of the values in LST"""
+  
+  d = []
+  last = None
+  for v in lst:
+    if last != None:
+      d.append(v - last)
+    last = v
+  return d
+
+def cyclic_pairs(lst):
+  """cyclic_pairs(lst)
+
+  Returns the cyclic pairs of LST as a list of 2-tuples.
+  """
+
+  n = len(lst)
+  assert(n >= 2)
+  cps = []
+  for i in xrange(n - 1):
+    cps.append((lst[i], lst[i + 1]))
+  cps.append((lst[n - 1], lst[0]))
+  return cps
+
+def number_of_leading(p, lst):
+  """number_of_leading(p, lst)
+
+  Returns the number of leading elements X of LST for which P(X) is true.
+  """
+  
+  i = 0
+  for v in lst:
+    if not p(v):
+      break
+    i += 1
+  return i
+
+def number_of_trailing(p, lst):
+  """number_of_trailing(p, lst)
+
+  Returns the number of trailing elements X of LST for which P(X) is true.
+  """
+
+  n = len(lst)
+  for i in xrange(n - 1, -1, -1):
+    if not p(lst[i]):
+      return (n - 1) - i
+  return len(lst)
+
+### Flatten
+################################################################
+def _flatten_once(seq):
+  """
+  Return a list with the contents of SEQ with sub-lists and tuples "exploded".
+  This is only done one-level deep.
+  """
+
+  lst = []
+  for x in seq:
+    if type(x) is list or type(x) is tuple:
+      for val in x:
+        lst.append(val)
+    else:
+      lst.append(x)
+  return lst
+
+def _flatten_all(seq):
+  """
+  Returns a list of the contents of seq with sublists and tuples "exploded".
+  The resulting list does not contain any sequences, and all inner sequences
+  are exploded.  For example:
+
+  >>> flatten([7,(6,[5,4],3),2,1])
+  [7,6,5,4,3,2,1]
+  """
+  lst = []
+  for el in seq:
+    if type(el) == list or type(el) is tuple:
+      lst.extend(flatten(el))
+    else:
+      lst.append(el)
+  return lst
+
+from mathematica import nest
+
+def flatten(seq, n=0):
+  """
+  flatten(seq, n) -> list
+  
+  Returns a list of the contents of seq with sublists and tuples "exploded"
+  at level n. If not level is given, or n=0, then flatten "explodes" all
+  sublists and tuples.
+  
+  EXAMPLE:
+      li = [[1, 2], [3, [4], 5], [6, [7, 8]]]
+      flatten(li, 1) is equal to [1, 2, 3, [4], 5, 6, [7, 8]]
+  """
+  
+  if n < 0:
+        raise TypeError("n has to be bigger than zero")
+  elif n == 0:
+       return _flatten_all(seq)
+  
+  return nest(_flatten_once, seq, n)
+## lazy.py provides support for lazy expressions and datastructures.
+## Copyright (C) 2000 Bryn Keller
+
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## Lesser General Public License for more details.
+
+## You should have received a copy of the GNU Lesser General Public
+## License along with this library; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+from types import *
+from xoltar import *
+import sys
+
+
+__version__ = '0.8.0'
+
+if hasattr(sys, '_getframe'):
+    _getStackFrame = sys._getframe
+else:
+    def _getStackFrame():
+        try:
+            raise RuntimeError
+        except:
+            return sys.exc_info()[2].tb_frame.f_back
+      
+def is_lazy(thing):
+    """
+    Returns 1 if *thing* is a Lazy expression, 0 otherwise.
+    """
+    try:
+        return isinstance(thing, Lazy)
+    except:
+        return 0
+
+class Lazy:
+    """
+    Abstract base class for lazy things.
+    """
+    def eval(self):
+        """
+        Forces this lazy object to evaulate itself fully. Returns
+        the final, strict version of the object, if appropriate.
+        For instance, LazyExpr.eval returns the result of evaluating
+        its expression, and LazyTuple.eval returns a normal tuple.
+        """
+        raise NotImplementedError
+
+    def isEvaluated(self):
+        """
+        Should return 1 if the object has been fully evaluated,
+        0 otherwise.
+        """
+        raise NotImplementedError
+
+class LazyExpr(Lazy):
+    """
+    Lazy expressions are expressions which are not computed until needed.
+    Many functional languages (Haskell, Scheme, OCaml, etc.) provide support
+    for this as a language feature, but a large class of those things can
+    be simulated in Python with this class and/or LazyTuple.
+    Things that will force a lazy expression *expr* to be evaluated:
+        - *expr*.eval()
+        - any value comparison, such as *expr* < 5, or *expr* == "abc"
+        - any sort of operation such as slicing, getattrs, or mathematical
+          opertions, **unless the other operands involved are also lazy.**
+        - calling str(*expr*). Same for int, float, long.
+    A lazy expression is evaluated in the namespaces of the code which constructed
+    it, unless the defaults are overridden. For example:
+
+    a = 5
+    laz = LazyExpr("a * 5")
+    a = 7
+    assert laz == 25
+
+    #Now laz can be used in any context, and will always evaluate to 25, even if
+    #a changes or goes out of scope.
+    """
+    def __init__(self, code, globs = {}, locs = {}):
+        """
+        *code* can be either a code object or a string. Either way, it should
+        be an expression, not a statement. If the *globs* or *locs* params are
+        omitted, the global and local namespaces of the caller will be used
+        for evaluation.
+        """
+        if type(code) == StringType:
+            code = compile(code, 'Lazy expr: ' + code, 'eval')
+        self.__dict__['_code'] = code
+        if not globs or not locs:
+            frame = _getStackFrame().f_back
+            l, g = frame.f_locals, frame.f_globals
+            if not locs:
+                locs = l.copy()
+            if not globs:
+                globs = g.copy()
+        self.__dict__['_globs'] = globs
+        self.__dict__['_locs'] = locs
+
+    def eval(self):
+        """
+        Forces (and returns) the evaluation of the expression.
+        """
+        if not self.__dict__.has_key('_value'):
+            self.__dict__['_value'] = eval(self._code, self._globs, self._locs)
+            #Delete namespaces so we don't prevent GC on their contents...
+            del self.__dict__['_globs']
+            del self.__dict__['_locs']
+        return self.__dict__['_value']
+
+    def __str__(self):
+        """
+        Will cause evaluation.
+        """
+        return str(self.eval())
+
+    def __repr__(self):
+        """
+        Does **not** cause evaluation.
+        """
+        return self._code.co_filename
+
+    def __len__(self):
+        """
+        Will cause evaluation.
+        """
+        return len(self.eval())
+
+    def __mul__(self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() * other.eval()", locs = locals())
+        return self.eval() * other
+
+    def __rmul__(self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() * self.eval()")
+        return other * self.eval()
+
+    def __div__(self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() * other.eval()")
+        return self.eval()/other
+
+    def __rdiv__(self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval()/self.eval()")
+        return other/self.eval()
+
+    def __mod__(self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() % self.eval()")
+        return other % self.eval()
+
+    def __rmod__(self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() % other.eval()")
+        return self.eval() % other
+
+    def __divmod__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("divmod(other.eval(),self.eval())")
+        return divmod(other, self.eval())
+
+    def __pow__ (self, other, modulo):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("pow(self.eval(), other.eval(), modulo)")
+        return pow(self.eval(), other, modulo)
+
+    def __lshift__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() << other.eval()")
+        return self.eval() << other
+
+    def __rshift__ (self, other) :
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() >> other.eval()")
+        return self.eval() >> other
+
+    def __and__ (self, other) :
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() & other.eval()")
+        return self.eval() & other
+
+    def __xor__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() ^ other.eval()")
+        return self.eval() ^ other
+    def __or__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("self.eval() | other.eval()")
+
+    def __radd__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() + self.eval()")
+        return other + self.eval()
+
+    def __rsub__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() - self.eval()")
+        return other - self.eval()
+
+    def __rdivmod__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("divmod(other.eval(), self.eval())")
+        return divmod(other + self.eval())
+
+    def __rpow__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("pow(other.eval(), self.eval())")
+        return pow(other, self.eval())
+
+    def __rlshift__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() << self.eval()")
+        return other << self.eval()
+
+    def __rrshift__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() >> self.eval()")
+        return other >> self.eval()
+
+    def __rand__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() & self.eval()")
+        return other & self.eval()
+
+    def __rxor__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() ^ self.eval()")
+        return other ^ self.eval()
+
+    def __ror__ (self, other):
+        """
+        Will cause evaluation, unless *other* is also lazy.
+        """
+        if isLazy(other):
+            return LazyExpr("other.eval() | self.eval()")
+        return other | self.eval()
+
+    def __neg__ (self):
+        """
+        Will cause evaluation.
+        """
+        return -self.eval()
+
+    def __pos__ (self):
+        """
+        Will cause evaluation.
+        """
+        return +self.eval()
+
+    def __abs__ (self):
+        """
+        Will cause evaluation.
+        """
+        return abs(self.eval())
+
+    def __invert__ (self):
+        """
+        Will cause evaluation.
+        """
+        return not self.eval()
+
+    def __complex__ (self):
+        """
+        Will cause evaluation.
+        """
+        return complex(self.eval())
+
+    def __oct__ (self):
+        """
+        Will cause evaluation.
+        """
+        return oct(self.eval())
+
+    def __hex__ (self):
+        """
+        Will cause evaluation.
+        """
+        return hex(self.eval())
+
+    def __getitem__(self, ntx):
+        """
+        Does **not** cause evaluation.
+        """
+        if isLazy(ntx):
+            return LazyExpr("self.eval()[ntx.eval()]")
+        else:
+            return LazyExpr("self.eval()[ntx]")
+
+    def __getslice__(self, i, j):
+        """
+        Does **not** cause evaluation.
+        """
+        return LazyExpr("self.eval()[i:j]")
+
+    def __delslice__(self, i, j):
+        """
+        Will cause evaluation.
+        """
+        del self.eval()[i:j]
+
+    def __setitem__(self, key, value):
+        """
+        Will cause evaluation.
+        """
+        self.eval()[key] = value
+
+    def __cmp__(self, other):
+        """
+        Will cause evaluation.
+        """
+        return cmp(self.eval(), other)
+
+    def __call__(self, *args, **kwargs):
+        """
+        Will cause evaluation.
+        """
+        return self.eval()(*args, **kwargs)
+
+    def __eq__(self, other):
+        """
+        Will cause evaluation.
+        """
+        return self.eval() == other
+
+    def __lt__(self, other):
+        """
+        Will cause evaluation.
+        """
+        return self.eval() < other
+        
+    def __gt__(self, other):
+        """
+        Will cause evaluation.
+        """
+        return self.eval() > other
+    
+    def __getattr__(self, name):
+        """
+        Does **not** cause evaluation.
+        """
+        if name == '__coerce__':
+            raise AttributeError, name
+        return LazyExpr("getattr(self.eval(), name)")
+
+    def __setattr__(self, name, value):
+        """
+        Will cause evaluation.
+        """
+        setattr(self.eval(), name, value)
+
+    def __delattr__(self, name):
+        """
+        Will cause evaluation.
+        """
+        delattr(self.eval(), name)
+
+    def __int__(self):
+        """
+        Will cause evaluation.
+        """
+        return int(self.eval())
+
+    def __float__(self):
+        """
+        Will cause evaluation.
+        """
+        return float(self.eval())
+
+    def __long__(self):
+        """
+        Will cause evaluation.
+        """
+        return long(self.eval())
+
+    def __copy__(self):
+        """
+        Does **not** cause evaluation.
+        """
+        import copy
+        return LazyExpr("copy.copy(self.eval())")
+
+    def __deepcopy__(self, dict):
+        """
+        Does **not** cause evaluation.
+        """
+        import copy
+        return LazyExpr("copy.deepcopy(self.eval())")
+
+class Uncomputed:
+    """
+    Placeholder value used in LazyTuples when an index is known to exist, but
+    does not need to be computed yet.
+    """
+    pass
+
+
+class LazySequence(Lazy):
+    """
+    Abstract base class for lazy sequences.
+    """
+    def isTerminating(self):
+        """
+        Return 1 if this is a finite sequence, 0 if it is infinitely long.
+        """
+        raise NotImplementedError
+
+    def __str__(self):
+        val = ""
+        try:
+            for i in range(3):
+                if val:
+                    val = val + ", "
+                val = val + str(self[i])
+        except IndexError:
+            pass
+        else:
+            val = val + ", .."
+
+        return "%s (%s)" % (self.__class__.__name__, val)
+        
+    def __mul__(self, other):
+        #TODO: Should this and __add__ play nicely with lazy values?
+        if not self.isTerminating():
+            return self
+        return self.eval() * other
+
+    def __add__(self, other):
+        if not self.isTerminating():
+            return self
+        return self.eval() + other
+
+    def __cmp__(self, other):
+        if self is other:
+            return 0
+        if isinstance(other, LazySequence):
+            if self.isTerminating():
+                if not other.isTerminating():
+                    return -1
+            elif other.isTerminating():
+                return 1
+        elif type(other) == type(()):
+            if not self.isTerminating():
+                return 1
+            else:
+                if cmp(len(self), len(other)):
+                    return cmp(len(self), len(other))
+                else:
+                    for sthing, othing in lazyzip(self, other):
+                        if cmp(sthing, othing):
+                            return cmp(string, othing)
+                    return 0
+        else:
+            return 1
+
+class LazyTuple(LazySequence):
+    """
+    Lazy tuples (equivalent to lazy lists in functional languages) are sequences
+    whose values are calculated on demand. In a normal (strict) tuple, every
+    value in the tuple must be known at the time it is constructed, and it has a
+    definite length. Not so with LazyTuples, which may have potentially infinite
+    length, and the value at a given index is computed only when needed for some
+    other calculation.
+
+    In this implementation, a function is defined which takes two arguments, an
+    index, and the LazyTuple the index is being done on. Whatever this function
+    returns is the value of the LazyTuple at that index. The function will only
+    be called once for each index, and the cached value will be used in
+    subsequent indexing operations.
+
+    For example:
+
+    #Build a lazy list of squares:
+    def square(index, seq):
+        return index * index
+
+    >>>laz = LazTuple(itemFunc = square)
+    >>>print laz[2]
+    4
+    >>>
+
+    #But this is a simple case which can be extrapolated directly from the
+    #index. A better example:
+
+    def factorial(index, seq):
+        if index == 0:
+            return 1
+        else:
+            return seq[index -1] * index
+
+    >>>laz = LazyTuple(itemFunc = factorial)
+    >>>laz[3]
+    6
+    >>>
+
+    In this last example, laz[3] caused factorial to be called with index == 3,
+    which in turn forced the evaluation (because it's necessary for factorial
+    construction) of all the indices prior to 3. In the first example, no
+    other indices need to be computed.
+
+    Note that neither of these examples *terminates*, that is they are both
+    of infinite length (actually they'll overflow from integer multiplication
+    eventually, but's that's not important for this discussion). When dealing
+    with infinite tuples, a few rules apply:
+
+    - *lazytuple*.isTerminating() will return 1 if the tuple has definite length,
+        0 otherwise.
+    - len(*lazytuple*) will raise a RuntimeError if the list is infinite.
+    - if *lazytuple*: will always be true for an infinite tuple.
+    - LazyTuples may be compared normally.
+    - iteration over a LazyTuple with for works fine, but if the tuple doesn't
+      terminate, neither will your loop!
+
+    """
+    def __init__(self, itemFunc = None, length = -1):
+        """
+        *itemFunc* is a function which takes two arguments, *index* and
+        *sequence*, and is used to generate the value at an arbitrary
+        index. If *length* is zero or more, then this is a bounded (finite)
+        LazyTuple. A *length* of -1 indicates a (possibly) infinite tuple,
+        a -2 value indicates a tuple which will eventually terminate, but
+        its exact length is not known at this time.
+        
+        Storage space is never duplicated for LazyTuples and slices taken
+        from them.
+        """
+        self._itemFunc = itemFunc
+        self._memo = []
+        self._evaluated = 0
+        self._length = length
+        
+    def isTerminating(self):
+        """
+        Return 1 if this is a finite tuple, 0 if it is infinitely long.
+        """
+        return self._length >= 0 or self._length == -2
+
+    def __getitem__(self, i):
+        if self._length >= 0 and i >= self._length:
+            raise IndexError, i
+        if i < 0:
+            #Convert to a positive index. Note this forces
+            #the tuple to be completely evaluated if its length isn't
+            #already known. Taking the len() of an infinite tuple
+            #will cause an error.
+            i = len(self) + i            
+        if len(self._memo) > i:
+            val = self._memo[i]
+            if not val is Uncomputed:
+                return self._memo[i]
+        try:
+            val = self._itemFunc(i, self)
+        except IndexError:
+            #Either there was in internal error in the function, or the tuple
+            #is finished. Like errors in __getattr__ methods which cause spurious
+            #AttributeErrors, this may produce unintended results. However, it's
+            #the only way for a possibly infinite tuple to announce it's reached
+            #a limit.
+            self._length = i
+            raise
+        if len(self._memo) <= i:
+            #There are other values at lesser indices that have not been computed
+            #yet. We extend the memo to be at least as big as this (now known)
+            #index. The spots in between we fill with Uncomputed. In the future,
+            #it might be worthwhile to create a variation on this class which
+            #uses a dictionary for _memo instead of a list - such a subclass would
+            #be more efficient for "sparse" tuples, where the value at an index
+            #doesn't depend on the value at a previous index.
+            self._memo.extend([Uncomputed] * ((i+1) - len(self._memo)))
+        self._memo[i] = val
+        return val
+
+    def __getslice__(self, i, j):
+        #TODO: Check for reversed slices?
+        print "LT getslice", i, j
+        if j != sys.maxint:
+            sliceEnd = j
+        else:
+            sliceEnd = -1
+        if self._length > 0:
+            if i >= self._length:
+                raise IndexError, i
+            if j >= self._length and j != sys.maxint:
+                raise IndexError, j
+        return LazySlice(source = self, start = i, end = sliceEnd)
+
+    def __len__(self):
+        if not self.isTerminating():
+            raise RuntimeError, "Non-terminating structure, cannot evaluate len()."
+        if self._length >= 0:
+            return self._length
+        else:
+            self.eval()
+            return len(self._memo)
+
+    def __nonzero__(self):
+        return 1
+
+    def eval(self):
+        if self._length == -1:
+            raise RuntimeError, "Cannot eval a non-terminating sequence."
+        if not self._evaluated:
+            i = 0
+            while 1:
+                try:
+                    self[i]
+                    i = i + 1
+                except IndexError:
+                    self._evaluated = 1
+                    break
+        #This tuple is now fully evaluated, make the _memo a tuple,
+        #so that we don't have spine-copying problems when we have to
+        #return a tuple to clients of .eval(). We can just return them
+        #the original memo.
+        self._memo = tuple(self._memo)
+        return self._memo
+    
+
+class LazySlice(LazySequence):
+    def __init__(self, source, start, end):
+        """
+        """
+        self._start = start
+        self._end = end
+        self._source = source
+        self._evaluated = 0
+        
+    def isTerminating(self):
+        """
+        Return 1 if this is a finite tuple, 0 if it is infinitely long.
+        A value of 2 means unknown.
+        """
+        return self._end > 1 or self._source.isTerminating()
+
+    def __getitem__(self, i):
+        if i >= 0:
+            if i < self._end or self._end < 0:
+                return self._source[i + self._start]
+            else:
+                raise IndexError, i
+        else:
+            if self._end < 0:
+                if not self._source.isTerminating():
+                    raise IndexError, i
+                self._source.eval()
+                if (len(self._source)+ i) >= self._start:
+                    return self._source[i]
+                else:
+                    raise IndexError, i
+            else:
+                adjusted = (self._end - self.start) + i
+                if adjusted >=0:
+                    return self._source[i + self._start]
+                else:
+                    raise IndexError, i
+                
+    def __getslice__(self, i, j):
+        print "LS getslice", i, j
+        newStart = self._start + i
+        if j == sys.maxint:
+            print "Max slice, end is:", self._end            
+            newEnd = self._end
+        elif self._end >= 0 and j > self._end:
+            raise IndexError, j
+        else:
+            if j >= 0:
+                newEnd = self._start + j               
+            else:
+                newEnd = self._end + j
+        return LazySlice(self._source, newStart, newEnd)
+        
+
+    def __len__(self):
+        if not self.isTerminating():
+            raise RuntimeError, "Non-terminating structure, cannot evaluate len()."
+        if self._end >= 0:
+            return self._end - self._start
+        else:
+            self.eval()
+            return len(self)
+
+    def __nonzero__(self):
+        if self._start == self._end:
+            return 0
+        else:
+            return 1
+
+    def eval(self):
+        if self._end < 0:
+            raise RuntimeError, "Cannot eval a non-terminating sequence."
+        if not self._evaluated:
+            i = 0
+            while 1:
+                try:
+                    self[i]
+                    i = i + 1
+                except IndexError:
+                    self._evaluated = 1
+                    self._end = i
+                    break
+        return tuple(self._source._memo[self._start:self._end])
+        
+
+
+
+def integers(index, seq, startFrom = 0, step = 1):
+    """
+    An index function for LazyTuples of consecutive integers.
+    """
+    if index == 0:
+        return startFrom
+    else:
+        return seq[index -1] + step
+
+def naturals(index, seq, startFrom = 1, step = 1):
+    """
+    An index function for LazyTuples of consecutive natural numbers.
+    """
+    assert startFrom > 0
+    return integers(index, seq, startFrom, step)
+
+def lazy_map(func, seq):
+    """
+    Lazy equivalent for the map builtin function.
+    lazy_map returns a LazyTuple whose contents are computed on demand
+    by applying *func* to seq[i], where i is the index that's being accessed.
+    """
+    if isinstance(seq, LazySequence):
+        if seq.isTerminating():
+            length = len(seq)
+        else:
+            length = -1
+    else:
+        length = len(seq)
+    newItemFunc = lambda index, sequence, orig = seq, f = func:f(orig[index])
+    return LazyTuple(itemFunc = newItemFunc, length = length)
+
+def lazy_filter(func, seq):
+    """
+    Lazy equivalent for the filter builtin function.
+    lazy_filter returns a LazyTuple whose contents are computed on demand
+    by filtering as much of the original sequence as necessary to reach
+    a value for the necessary index.
+    """
+    seqIndex = 0
+    class filterhelper:
+        def __init__(self, seq, seqIndex, func):
+            self.seq = seq
+            self.seqIndex = seqIndex
+            self.func = func
+
+        def __call__(self, index, sequence):            
+            while 1:
+                val = self.seq[self.seqIndex]
+                self.seqIndex = self.seqIndex + 1
+                if self.func(val):
+                    return val
+    if isinstance(seq, LazySequence):
+        if seq.isTerminating():
+            length = -2
+        else:
+            length = -1
+    else:
+        length = -2
+    return LazyTuple(itemFunc = filterhelper(seq, seqIndex, func), length = length)
+
+def lazy_reduce(func, seq):
+    """
+    Lazy equivalent for the reduce builtin function.
+    lazy_reduce can only be applied to terminating (non-infinite) tuples.
+    """
+    if isinstance(seq, LazyTuple) and not seq.isTerminating():
+        raise RuntimeError, "Cannot reduce infinite tuple."
+    return LazyExpr("reduce(func, tuple(seq))")
+
+def lazy_zip(*seqs):
+    """
+    Lazy equivalent for the zip builtin function.
+    """
+    def newItemFunc(index, seq, origseqs = seqs):
+        tup = []
+        for orig in origseqs:
+            tup.append(orig[index])
+        return tuple(tup)
+    return LazyTuple(itemFunc = newItemFunc)
+
+
+
+def when(expr, truepart, falsepart = None, force = 0):
+    """
+    Functional equivalent for the if(else) statement.
+    Note that unlike a real if, both truepart and falsepart will be evaluated,
+    unless of couse they are Lazy. If they are lazy, only the selected
+    expression will be returned. To get the selected lazy expression to be
+    evaluated, call with *force* = 1 Example:
+
+    >>> def printAndReturn(arg):
+    ... 	print arg
+    ... 	return arg
+    ...
+    >>> when(0, printAndReturn(0), printAndReturn(1))
+    0
+    1
+    1
+    #Note printAndReturn was called twice.
+
+    >>> when(0, LazyExpr("printAndReturn(0)"), LazyExpr("printAndReturn(1)"))
+    Lazy expr: printAndReturn(1)
+    >>> when(0, LazyExpr("printAndReturn(0)"), LazyExpr("printAndReturn(1)"), 1)
+    1
+    1
+    #because of the last (force) parameter, the chosen lazy expression was
+    #evaluated before returning.
+    >>>
+    """
+    if expr:
+        retval = truepart
+    else:
+        retval = falsepart
+    if isLazy(retval) and force:
+        retval = retval.eval()
+    return retval

funckit/mathematica.py

+# -*- coding: utf-8 -*-
+
+### Functional iterators and applications derived from Mathematica 
+
+## Copyright (C) 2009 Carlos Córdoba
+
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## Lesser General Public License for more details.
+
+## You should have received a copy of the GNU Lesser General Public
+## License along with this library; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+### nest
+################################################################
+def nest(function, expr, n = 1):
+    """
+    nest(function, expr, n) -> object
+    
+    Applies function n times to expr.
+    
+    EXAMPLE:
+    nest(f,e,2) is equivalent to f(f(e))
+    """
+    if not callable(function):
+        raise TypeError("First argument to nest must be callable")
+    
+    if n < 1:
+        raise TypeError("n has to be bigger than zero")
+        
+    result = expr
+        
+    for i in xrange(n):
+        result = function(result)
+    
+    return result
+
+def _nest_list_generator(function, expr, n = 1):
+    """ Yields the succesive applications of function to e"""
+    result = expr
+    yield result
+    
+    for i in xrange(n):
+        result = function(result)
+        yield result
+
+def nest_list(function, expr, n = 1):
+    """
+    nest_list(function, expr, n) -> list
+
+    Gives the list resulting from applying function n times to expr.
+    
+    EXAMPLE:
+      nest_list(f,e,2) is equal to [e, f(e), f(f(e))]
+    """
+    if not callable(function):
+        raise TypeError("First argument to nest must be callable")
+    
+    if n < 1:
+        raise TypeError("n has to be bigger than one")
+
+    return list(_nest_list_generator(function,expr,n))
+
+### rotate_left
+################################################################
+def _rotate_left_once(lst):
+    """
+    _rotate_left_once(list) -> list
+
+    Moves the elements of a list one position to the left.
+    
+    EXAMPLE:
+      _rotate_left_once([1,2,3]) is equal to [2,3,1]
+    """
+    li = lst[1:len(lst)]
+    li.append(lst[0])
+    return li
+
+def rotate_left(lst, n=1):
+    """
+    rotate_left(list, n) -> list
+
+    Moves the elements of a list n positions to the left.
+    
+    EXAMPLE:
+      rotate_left([1,2,3], 2) is equal to [3,1,2]
+    """
+    
+    if n < 1:
+        raise TypeError("n has to be bigger than 1")
+    
+    return nest(_rotate_left_once, lst, n)
+
+### Partition
+################################################################
+# By Terry Hancock and Carlos Cordoba
+
+def list_partition(lst, n, offset=0):
+    """
+    list_partition(list,n) returns list partitioned with n elements
+    per group.
+    
+    list_partition(list,n, offset) returns n elements with offset d.
+
+    If n is not a factor of the length of list, then the reminder
+    elements are dropped.
+
+    EXAMPLES:
+      list_partition([1,2,3,4,5,6],2) returns [[1,2],[3,4],[5,6]]
+      list_partition([1,2,3,4,5,6,7],3) returns [[1,2,3],[4,5,6]]
+      list_partition([1,2,3,4,5,6,7],4,2) returns [1,2,3,4], [3,4,5,6]]
+    """
+    
+    if offset < 0:
+        raise TypeError("offset has to be equal or bigger than 0")
+    
+    if offset == 0:
+        return [lst[k*n:(k+1)*n] for k in range(len(lst)/n)]
+    else:
+        to_sum = filter(lambda x: x+n <= len(lst), xrange(0, len(lst), offset))
+        indexes = [ [x,n+x] for x in to_sum ]
+        return [ lst.__getslice__(*i) for i in indexes ]
+        
+def column(lst, n):
+    """
+    column(lst, n) returns the nth column of a list
+    """
+    return [x[n] for x in lst]
+
+### depth
+################################################################
+
+def depth(iterable):
+    """
+    depth(iterable) -> int
+    
+    Computes the depth of a nested iterable (list or tuple)
+    
+    EXAMPLES:
+        depth(['a', [['b'], 'c']) is equal to 3
+    """
+    if isinstance(iterable, (list, tuple)):
+        return (1 + max(map(depth, iterable)))
+    else:
+        return 0
+
+try:
+    from sage.rings.integer import Integer as integer
+    _is_int = lambda x: isinstance(x, (int, integer))
+except ImportError:
+    _is_int = lambda x: isinstance(x, int)
+    
+from functools import partial as _partial
+
+### map
+################################################################
+
+def map_level(function, iterable, level=1):
+    """
+    map_level(function, iterable, level) -> list
+    
+    Applies function to each element of iterable, returning a list
+    of the resulting values. Basically, this is like the builtin map
+    function (if level=1), except we only take a single iterable and
+    there's none of that map(None, ...) nonsense and it only takes
+    one iterable not several of them.
+    
+    Besides, we add an additional argument called level to apply
+    function to all sublists at any given level of depth on the iterable.
+    
+    EXAMPLES:
+        map_level(str, [[1, 2], [3, [4]], 5], 2) is equal to [['1', '2'], ['3', '[4]'], 5]
+        because it applies str to the sublists at depth two. The main
+        list is considered to be depth one.
+        
+        map_level(str, [[1, 2], [3, [4]], 5], 3) is equal to [[1, 2], [3, ['4']], 5]
+    """
+    
+    if level < 1:
+        raise TypeError("level must be greater than one")
+    elif not _is_int(level):
+        raise TypeError("level must be an number")
+    elif level == 1:
+        return [function(x) for x in iterable]
+    elif level > depth(iterable):
+        return iterable
+    else:
+        def _map_level(seq, count_levels, level):
+            if isinstance(seq, (list, tuple)) and count_levels == level:
+                return map(function, seq)
+            elif isinstance(seq, (list, tuple)):
+                return map(_partial(_map_level, count_levels=count_levels+1, level=level), seq)
+            else:
+                return seq
+        
+        return _map_level(iterable, 1, level)

funckit/operators.py

+# -*- coding: utf-8 -*-
+
+### Infix operators to make code functional programming more succint
+### Inspired by similar operators in Mathematica 
+
+## Copyright (C) 2009 Carlos Córdoba
+
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## Lesser General Public License for more details.
+
+## You should have received a copy of the GNU Lesser General Public
+## License along with this library; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+### Infix operator decorator
+### Taken from http://trac.sagemath.org/sage_trac/ticket/6245
+### with some minor changes
+################################################################
+class _infix_operator:
+    def __init__(self, function, left=None, right=None):
+        self.function = function
+        self.__doc__ = function.__doc__
+        self.left = left
+        self.right = right
+
+    def __ror__(self, left):
+        if self.right is None:
+            if self.left is None:
+                return _infix_operator(self.function, left=left)
+            else:
+                raise SyntaxError, "Infix operator already has its left argument"
+        else:
+            return self.function(left, self.right)
+
+    def __or__(self, right):
+        if self.left is None:
+            if self.right is None:
+                return _infix_operator(self.function, right=right)
+            else:
+                raise SyntaxError, "Infix operator already has its right argument"
+        else:
+            return self.function(self.left, right)
+
+### Map operator
+################################################################
+@_infix_operator
+def at(function,lst):
+    """
+    function |at| list -> list
+    
+    at is an infix operator that returns map(function,list).
+    It's the equivalent to /@ operator in Mathematica.
+    
+    EXAMPLES:
+      sqrt |at| (float |at| [1,2,3,4]) is equal to [1.0, 1.41, 1.73, 2.0]
+    """
+
+    if not callable(function):
+        raise TypeError("First argument to |at| must be callable")
+    
+    return map(function,lst)
+
+### Apply operator
+################################################################
+@_infix_operator
+def app(function,obj):
+    """
+    function |app| obj -> obj
+    
+    app is an infix operator that returns apply(function,obj).
+    It's more or less the equivalent of the @@ operator in Mathematica.
+    (Since Python doesn't have the equivalent of Mathematica's "Heads",
+    it won't do exactly the same)
+
+    EXAMPLES:
+      sum |app| [[1,2,3,4]] is equal to 10
+    """
+
+    if not callable(function):
+        raise TypeError("First argument to |at| must be callable")
+    
+    return apply(function,obj)
+ 

funckit/partial.py

+## partial.py provides support for partial application of functions
+## Copyright (C) 2002 Bryn Keller
+
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## Lesser General Public License for more details.
+
+## You should have received a copy of the GNU Lesser General Public
+## License along with this library; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+import sys
+import operator
+import types
+
+__all__ = ["Void", "v_"]
+
+def void_null_op(name, expr, dict):
+    """
+    Creates an operator for instances of void.
+    """
+    s = """
+def __%s__(self):
+    def %s_void(x):
+        return %s
+    return Partial(%s_void)
+""" % (name, name, expr, name)
+    exec s in globals(), dict
+
+def void_op(name, expr, dict):
+    """
+    Creates an operator for instances of void.
+    """
+    s = """
+def __%s__(self, arg):
+    def %s_void(x):
+        return %s
+    return Partial(%s_void)
+""" % (name, name, expr, name)
+    exec s in globals(), dict
+
+def void_bin_op(name, expr, dict):
+    """
+    Creates a two-argument operator for instances of void.
+    """
+    s = """
+def __%s__(self, arg, arg2):
+    def %s_void(x):
+        return %s
+    return Partial(%s_void)
+""" % (name, name, expr, name)
+    exec s in globals(), dict
+
+
+class Void(object):
+    """
+    Void objects are stand-ins, blanks, or holes in an expression,
+    which can later be filled in. For example:
+
+    v = Void()
+
+    add_one = v + 1
+
+    Now add_one is a function which takes one argument, and returns the
+    argument plus one. This module exports "_", a single underscore, as
+    an instance of Void, because it is suggestive of a blank or missing
+    piece. Here are some more examples:
+
+    import sys
+    from operator import add
+
+    adder = add(1,_)
+    assert map(adder, range(3)) == [1,2,3]
+
+    assert (_ + 5)(5) == 10
+    assert (5 + _)(5) == 10
+    assert (5 * _)(5) == 25
+    assert (_ * 5)(5) == 25
+    assert ((5 + _) * 5)(3) == 40, ((5 + _) * 5)(3)
+    assert ((5 + _) * _)(3)(5) == 40
+    assert ((5 + _) * _)(3, 5) == 40
+
+    lst = []
+    (_.append)(lst)(5)
+    assert lst == [5], lst
+
+    unsplit = ["foo", "ba ba", "baz"]
+    postsplit = [["foo"], ["ba", "ba"], ["baz"]]
+
+    assert mapcall(_.split, unsplit) == postsplit
+    assert mapcall(None, map(_.split, unsplit)) == postsplit
+    assert mapcall(_.split, unsplit, 'o') == [['f','',''], ['ba ba'], ['baz']]
+    assert map(_ + 5, [1,2,3]) == [6,7,8]
+    assert map(_['key'], [{'key':5}]) == [5]
+    assert map(_[0], [(1,2,3),("a", "b", "c"), (10, 20, 30)]) == [1, "a", 10]
+    assert map(_[1:3], [(1,2,3),("a", "b", "c"), (10, 20, 30)]) == [(2,3), ("b", "c"), (20, 30)]
+
+    if sys.version_info[0] > 2 or sys.version_info[1] > 2:
+        revtest = map(_[3:0:-1], [(1,2,3),("a", "b", "c"), (10, 20, 30)])
+        assert revtest == [(3,2), ("c", "b"), (30, 20)], revtest
+    assert len(((_ + 2) * "foo")(3)) == 15
+
+    """
+    import operator
+    d = locals()
+##    void_null_op("hash" "hash(x)", d)
+##    void_null_op("len", "len(x)", d)
+##    void_null_op("nonzero", "truth(x)", d)
+    void_op("lt", "arg < x", d)
+    void_op("le", "arg <= x", d)
+    void_op("gt", "arg > x", d)
+    void_op("ge", "arg >= x", d)
+    void_op("eq", "arg == x", d)
+    void_op("ne", "arg != x", d)
+    void_op("getattr", "getattr(x, arg)", d)
+    void_bin_op("setattr", "setattr(x, arg, arg2)", d)
+    void_op("delattr", "delattr(x, arg)", d)
+    #void_op("getitem", "x[arg]", d)
+#     void_op("getitem",
+#     "type(arg) is types.SliceType and x[arg.start:arg.stop:arg.step] or x[arg]",
+#     d)
+    if (sys.version_info[0] < 3 and sys.version_info[1] < 3):
+        def __getitem__(self, arg):
+            def getitem_void(x):
+                if type(arg) is types.SliceType:
+                    return x[arg.start:arg.stop]
+                else:
+                    return x[arg]
+            return Partial(getitem_void)
+    else:
+        def __getitem__(self, arg):
+            def getitem_void(x):
+                if type(arg) is types.SliceType:
+                    if (arg.step != None):
+                        return x[arg.start:arg.stop:arg.step]
+                    else:
+                        return x[arg.start:arg.stop]
+                else:
+                    return x[arg]
+            return Partial(getitem_void)
+
+    void_op("delitem", "operator.delitem(x, arg)", d)
+    void_op("iter", "iter(x)", d)
+    void_op("contains", "arg in x", d)
+    void_bin_op("setitem", "operator.setitem(x, arg, arg2)", d)
+    void_op("add", "x + arg", d)
+    void_op("radd", "arg + x", d)
+    void_op("mul", "x * arg", d)
+    void_op("rmul", "arg * x", d)
+    void_op("div", "x / arg", d)
+    void_op("rdiv", "arg/x", d)
+    void_op("sub", "x - arg", d)
+    void_op("rsub", "arg - x", d)
+    void_op("mod", "x % arg", d)
+    void_op("rmod", "arg % x", d)
+    void_op("pow", "x ** arg", d)
+    void_op("rpow", "arg ** x", d)
+    void_op("lshift", "x << arg", d)
+    void_op("rlshift", "arg << x", d)
+    void_op("rshift", "x >> arg", d)
+    void_op("rrshift", "arg >> x", d)
+    # To avoid conflicts with the operator module
+    # void_op("or", "x | arg", d)
+    # void_op("ror", "arg | x", d)
+    void_op("and", "x & arg", d)
+    void_op("rand", "arg & x", d)
+    void_op("xor", "xor(x, arg)", d)
+    void_op("rxor", "xor(arg, x)", d)
+##    void_null_op("neg", "-x", d)
+##    void_null_op("pos", "+x", d)
+##    void_null_op("abs", "abs(x)", d)
+##    void_null_op("invert", "~x", d)
+    def __call__(self, *args, **kwargs):
+        def void_call(func):
+            return func(*args, **kwargs)
+        return void_call
+
+
+def partial_op(name, expr, dict):
+    s = """
+def __%s__(self, arg):
+    def %s_partial(x):
+        return %s
+    return Partial(%s_partial)
+""" % (name, name, expr.replace("x", "self.func(x)"), name)
+    exec s in globals(), dict
+
+def partial_bin_op(name, expr, dict):
+    s = """
+def __%s__(self, arg, arg2):
+    def %s_partial(x):
+        return %s
+    return Partial(%s_partial)
+""" % (name, name, expr.replace("x", "self.func(x)"), name)
+    exec s in globals(), dict
+
+class Partial(Void):
+    d = locals()
+    partial_op("delitem", "operator.delitem(x, arg)", d)
+    partial_op("iter", "iter(x)", d)
+    partial_op("contains", "arg in x", d)
+    partial_bin_op("setitem", "operator.setitem(x, arg, arg2)", d)
+    partial_op("add", "x + arg", d)
+    partial_op("radd", "arg + x", d)
+    partial_op("mul", "x * arg", d)
+    partial_op("rmul", "arg * x", d)
+    partial_op("div", "x / arg", d)
+    partial_op("rdiv", "arg/x", d)
+    partial_op("sub", "x - arg", d)
+    partial_op("rsub", "arg - x", d)
+    partial_op("mod", "x % arg", d)
+    partial_op("rmod", "arg % x", d)
+    partial_op("pow", "x ** arg", d)
+    partial_op("rpow", "arg ** x", d)
+    partial_op("lshift", "x << arg", d)
+    partial_op("rlshift", "arg << x", d)
+    partial_op("rshift", "x >> arg", d)
+    partial_op("rrshift", "arg >> x", d)
+    # To avoid conflicts with the operator module
+    # partial_op("or", "x | arg", d)
+    # partial_op("ror", "arg | x", d)
+    partial_op("and", "x & arg", d)
+    partial_op("rand", "arg & x", d)
+    partial_op("xor", "xor(x, arg)", d)
+    partial_op("rxor", "xor(arg, x)", d)
+    def __init__(self, func):
+        self.__dict__['func'] = func
+        Void.__init__(self)
+
+    def __call__(self, *args):
+        func = self.func
+        args = list(args)
+        if not args:
+            return func()
+        for arg in args:
+            func = func(arg)
+        return func
+   
+v_ = Void()

funckit/xoltar.py

+## functional.py provides support for a functional style of Python programming.
+## Copyright (C) 2000 Bryn Keller
+
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+## Lesser General Public License for more details.
+
+## You should have received a copy of the GNU Lesser General Public
+## License along with this library; if not, write to the Free Software
+## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+"""
+xoltar.py provides support for a functional style of Python programming.
+
+It includes support for curried functions, and  some higher-order functions
+for composing, sequencing, and otherwise manipulating functions.
+"""
+
+from types import *
+import sys
+from copy import copy
+import string
+import operator
+import traceback
+from goopy import every
+from datastruct import mapdict
+
+__version__ = "1.2.0"
+
+
+class Ref:
+    """
+    A simple class to hold a value. Useful when one wishes to share a value
+    between functions, or otherwise access the value from a local scope without
+    using a 'global' statement to avoid rebinding the name locally.
+    """
+    def __init__(self, val):
+        self.val = val
+
+class Blank:
+    """
+    When passed in a call to curry, or to a curried function, this is treated as a placeholder
+    for future calls to replace.
+    """
+    pass
+
+b_ = Blank
+
+def blend(func, original, mix):
+    """
+    This function returns a list based on *original*, with any elements that
+    *func* returns nonzero for replaced one by one with items from *mix*.
+    Any unused items in *mix* appear at the end of the new list. If there are
+    items which should be replaced, but there are no more items in *mix*, then
+    those items are left unchanged.
+    """
+    mixIndex = 0
+    build = []
+    mixlen = len(mix)
+    for item in original:
+        if mixIndex < mixlen and func(item):
+            build.append(mix[mixIndex])
+            mixIndex = mixIndex + 1
+        else:
+            build.append(item)
+    if mixIndex < mixlen:
+        build.extend(list(mix[mixIndex:]))
+    return build
+
+
+class FuncMethUnion:
+    """