Fn.py: enjoy FP in Python
=========================
Despite the fact that Python is not pure-functional programming
language, it's multi-paradigm PL and it gives you enough freedom to take
credits from functional programming approach. There are theoretical and
practical advantages to the functional style:
- Formal provability
- Modularity
- Composability
- Ease of debugging and testing
``Fn.py`` library provides you with missing "batteries" to get maximum
from functional approach even in mostly-imperative program.
More about functional approach from my Pycon UA 2012 talks: `Functional
Programming with
Python <http://kachayev.github.com/talks/uapycon2012/index.html>`_.
Scala-style lambdas definition
------------------------------
.. code-block:: python
from fn import _
from fn.op import zipwith
from itertools import repeat
assert list(map(_ * 2, range(5))) == [0,2,4,6,8]
assert list(filter(_ < 10, [9,10,11])) == [9]
assert list(zipwith(_ + _)([0,1,2], repeat(10))) == [10,11,12]
More examples of using ``_`` you can find in `test
cases <https://github.com/kachayev/fn.py/blob/master/tests.py>`_
declaration (attributes resolving, method calling, slicing).
**Attention!** If you work in interactive python shell, your should remember that ``_`` means "latest output" and you'll get unpredictable results. In this case, you can do something like ``from fn import _ as X`` (and then write functions like ``X * 2``).
If you are not sure, what your function is going to do, you can print it:
.. code-block:: python
from fn import _
print (_ + 2) # "(x1) => (x1 + 2)"
print (_ + _ * _) # "(x1, x2, x3) => (x1 + (x2 * x3))"
``_`` will fail with ``ArityError`` (``TypeError`` subclass) on inaccurate number of passed arguments. This is one more restrictions to ensure that you did everything right:
.. code-block:: python
>>> from fn import _
>>> (_ + _)(1)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "fn/underscore.py", line 82, in __call__
raise ArityError(self, self._arity, len(args))
fn.underscore.ArityError: (_ + _) expected 2 arguments, got 1
Persistent data structures
--------------------------
**Attention:** Persistent data structures are under active development.
Persistent data structure is a data structure that always preserves the previous version of itself when it is modified (more formal information on `Wikipedia <http://goo.gl/8VveOH>`_). Each operation with such data structure yields a new updated structure instead of in-place modification (all previous versions are potentially available or GC-ed when possible).
Lets take a quick look:
.. code-block:: python
>>> from fn.immutable import SkewHeap
>>> s1 = SkewHeap(10)
>>> s2 = s1.insert(20)
>>> s2
<fn.immutable.heap.SkewHeap object at 0x10b14c050>
>>> s3 = s2.insert(30)
>>> s3
<fn.immutable.heap.SkewHeap object at 0x10b14c158> # <-- other object
>>> s3.extract()
(10, <fn.immutable.heap.SkewHeap object at 0x10b14c050>)
>>> s3.extract() # <-- s3 isn't changed
(10, <fn.immutable.heap.SkewHeap object at 0x10b11c052>)
If you think I'm totally crazy and it will work despairingly slow, just give it 5 minutes. Relax, take a deep breath and read about few techniques that make persistent data structures fast and efficient: `structural sharing <http://en.wikipedia.org/wiki/Persistent_data_structure#Examples_of_persistent_data_structures>`_ and `path copying <http://en.wikipedia.org/wiki/Persistent_data_structure#Path_Copying>`_.
To see how it works in "pictures", you can check great slides from Zach Allaun's talk (StrangeLoop 2013): `"Functional Vectors, Maps And Sets In Julia" <http://goo.gl/Cp1Qsq>`_.
And, if you are brave enough, go and read:
- Chris Okasaki, "Purely Functional Data Structures" (`Amazon <http://goo.gl/c7ptkk>`_)
- Fethi Rabhi and Guy Lapalme, "Algorithms: A Functional Programming Approach" (`Amazon <http://goo.gl/00BxTO>`_)
Available immutable data structures in ``fn.immutable`` module:
- ``LinkedList``: most "obvious" persistent data structure, used as building block for other list-based structures (stack, queue)
- ``Stack``: wraps linked list implementation with well-known pop/push API
- ``Queue``: uses two linked lists and lazy copy to provide O(1) enqueue and dequeue operations
- ``Deque`` (in progress): `"Confluently Persistent Deques via Data
Structural Bootstrapping" <http://goo.gl/vVTzx3>`_
- ``Deque`` based on ``FingerTree`` data structure (see more information below)
- ``Vector``: O(log32(n)) access to elements by index (which is near-O(1) for reasonable vector size), implementation is based on ``BitmappedTrie``, almost drop-in replacement for built-in Python ``list``
- ``SkewHeap``: self-adjusting heap implemented as a binary tree with specific branching model, uses heap merge as basic operation, more information - `"Self-adjusting heaps" <http://goo.gl/R1PZME>`_
- ``PairingHeap``: `"The Pairing-Heap: A New Form of Self-Adjusting Heap" <http://goo.gl/aiVtPH>`_
- ``Dict`` (in progress): persistent hash map implementation based on ``BitmappedTrie``
- ``FingerTree`` (in progress): `"Finger Trees: A Simple General-purpose Data Structure" <http://goo.gl/Bzo0df>`_
Use appropriate doc strings to get more information about each data structure as well as sample code.
To get more clear vision of how persistent heaps work (``SkewHeap`` and ``PairingHeap``), you can look at slides from my talk `"Union-based heaps" <http://goo.gl/VMgdG2>`_ (with analyzed data structures definitions in Python and Haskell).
**Note.** Most functional languages use persistent data structures as basic building blocks, well-known examples are Clojure, Haskell and Scala. Clojure community puts much effort to popularize programming based on the idea of data immutability. There are few amazing talk given by Rich Hickey (creator of Clojure), you can check them to find answers on both questions "How?" and "Why?":
- `"The Value of Values" <http://goo.gl/137UG5>`_
- `"Persistent Data Structures and Managed References" <http://goo.gl/M3vZ7E>`_
Streams and infinite sequences declaration
------------------------------------------
Lazy-evaluated Scala-style streams. Basic idea: evaluate each new
element "on demand" and share calculated elements between all created
iterators. ``Stream`` object supports ``<<`` operator that means pushing
new elements when it's necessary.
Simplest cases:
.. code-block:: python
from fn import Stream
s = Stream() << [1,2,3,4,5]
assert list(s) == [1,2,3,4,5]
assert s[1] == 2
assert list(s[0:2]) == [1,2]
s = Stream() << range(6) << [6,7]
assert list(s) == [0,1,2,3,4,5,6,7]
def gen():
yield 1
yield 2
yield 3
s = Stream() << gen << (4,5)
assert list(s) == [1,2,3,4,5]
Lazy-evaluated stream is useful for infinite sequences, i.e. fibonacci
sequence can be calculated as:
.. code-block:: python
from fn import Stream
from fn.iters import take, drop, map
from operator import add
f = Stream()
fib = f << [0, 1] << map(add, f, drop(1, f))
assert list(take(10, fib)) == [0,1,1,2,3,5,8,13,21,34]
assert fib[20] == 6765
assert list(fib[30:35]) == [832040,1346269,2178309,3524578,5702887]
Trampolines decorator
---------------------
``fn.recur.tco`` is a workaround for dealing with TCO without heavy stack utilization. Let's start from simple example of recursive factorial calculation:
.. code-block:: python
def fact(n):
if n == 0: return 1
return n * fact(n-1)
This variant works, but it's really ugly. Why? It will utilize memory too heavy cause of recursive storing all previous values to calculate final result. If you will execute this function with big ``n`` (more then ``sys.getrecursionlimit()``) CPython will fail with
.. code-block:: python
>>> import sys
>>> fact(sys.getrecursionlimit() * 2)
... many many lines of stacktrace ...
RuntimeError: maximum recursion depth exceeded
Which is good, cause it prevents you from terrible mistakes in your code.
How can we optimize this solution? Answer is simple, lets transform function to use tail call:
.. code-block:: python
def fact(n, acc=1):
if n == 0: return acc
return fact(n-1, acc*n)
Why this variant is better? Cause you don't need to remember previous values to calculate final result. More about `tail call optimization <http://en.wikipedia.org/wiki/Tail_call>`_ on Wikipedia. But... Python interpreter will execute this function the same way as previous one, so you won't win anything.
``fn.recur.tco`` gives you mechanism to write "optimized a bit" tail call recursion (using "trampoline" approach):
.. code-block:: python
from fn import recur
@recur.tco
def fact(n, acc=1):
if n == 0: return False, acc
return True, (n-1, acc*n)
``@recur.tco`` is a decorator that execute your function in ``while`` loop and check output:
- ``(False, result)`` means that we finished
- ``(True, args, kwargs)`` means that we need to call function again with other arguments
- ``(func, args, kwargs)`` to switch function to be executed inside while loop
The last variant is really useful, when you need to switch callable inside evaluation loop. Good example for such situation is recursive detection if given number is odd or even:
.. code-block:: python
>>> from fn import recur
>>> @recur.tco
... def even(x):
... if x == 0: return False, True
... return odd, (x-1,)
...
>>> @recur.tco
... def odd(x):
... if x == 0: return False, False
... return even, (x-1,)
...
>>> print even(100000)
True
**Attention:** be careful with mutable/immutable data structures processing.
Itertools recipes
-----------------
``fn.uniform`` provides you with "unification"
of lazy functionality for few functions to work the same way in Python
2+/3+:
- ``map`` (returns ``itertools.imap`` in Python 2+)
- ``filter`` (returns ``itertools.ifilter`` in Python 2+)
- ``reduce`` (returns ``functools.reduce`` in Python 3+)
- ``zip`` (returns ``itertools.izip`` in Python 2+)
- ``range`` (returns ``xrange`` in Python 2+)
- ``filterfalse`` (returns ``itertools.ifilterfalse`` in Python 2+)
- ``zip_longest`` (returns ``itertools.izip_longest`` in Python 2+)
- ``accumulate`` (backported to Python < 3.3)
``fn.iters`` is high-level recipes to work with iterators. Most
of them taken from `Python
docs <http://docs.python.org/2.7/library/itertools.html#itertools.product>`_
and adopted to work both with Python 2+/3+. Such recipes as ``drop``,
``takelast``, ``droplast``, ``splitat``, ``splitby`` I have already
submitted as `docs patch <http://bugs.python.org/issue16774>`_ which is
review status just now.
- ``take``, ``drop``
- ``takelast``, ``droplast``
- ``head`` (alias: ``first``), ``tail`` (alias: ``rest``)
- ``second``, ``ffirst``
- ``compact``, ``reject``
- ``iterate``
- ``consume``
- ``nth``
- ``padnone``, ``ncycles``
- ``repeatfunc``
- ``grouper``, ``powerset``, ``pairwise``
- ``roundrobin``
- ``partition``, ``splitat``, ``splitby``
- ``flatten``
- ``iter_except``
More information about use cases you can find in docstrings for each
function in `source
code <https://github.com/kachayev/fn.py/blob/master/fn/iters.py>`__ and
in `test
cases <https://github.com/kachayev/fn.py/blob/master/tests.py>`_.
High-level operations with functions
------------------------------------
``fn.F`` is a useful function wrapper to provide easy-to-use partial
application and functions composition.
.. code-block:: python
from fn import F, _
from operator import add, mul
# F(f, *args) means partial application
# same as functools.partial but returns fn.F instance
assert F(add, 1)(10) == 11
# F << F means functions composition,
# so (F(f) << g)(x) == f(g(x))
f = F(add, 1) << F(mul, 100)
assert list(map(f, [0, 1, 2])) == [1, 101, 201]
assert list(map(F() << str << (_ ** 2) << (_ + 1), range(3))) == ["1", "4", "9"]
It also give you move readable in many cases "pipe" notation to deal with functions composition:
.. code-block:: python
from fn import F, _
from fn.iters import filter, range
func = F() >> (filter, _ < 6) >> sum
assert func(range(10)) == 15
You can find more examples for compositions usage in ``fn._``
implementation `source
code <https://github.com/kachayev/fn.py/blob/master/fn/underscore.py>`__.
``fn.op.apply`` executes given function with given positional arguments
in list (or any other iterable). ``fn.op.flip`` returns you function
that will reverse arguments order before apply.
.. code-block:: python
from fn.op import apply, flip
from operator import add, sub
assert apply(add, [1, 2]) == 3
assert flip(sub)(20,10) == -10
assert list(map(apply, [add, mul], [(1,2), (10,20)])) == [3, 200]
``fn.op.foldl`` and ``fn.op.foldr`` are folding operators. Each accepts function with arity 2 and returns function that can be used to reduce iterable to scalar: from left-to-right and from right-to-left in case of ``foldl`` and ``foldr`` respectively.
.. code-block:: python
from fn import op, _
folder = op.foldr(_ * _, 1)
assert 6 == op.foldl(_ + _)([1,2,3])
assert 6 == folder([1,2,3])
Use case specific for right-side folding is:
.. code-block:: python
from fn.op import foldr, call
assert 100 == foldr(call, 0 )([lambda s: s**2, lambda k: k+10])
assert 400 == foldr(call, 10)([lambda s: s**2, lambda k: k+10])
Function currying
-----------------
``fn.func.curried`` is a decorator for building curried functions, for example:
.. code-block:: python
>>> from fn.func import curried
>>> @curried
... def sum5(a, b, c, d, e):
... return a + b + c + d + e
...
>>> sum5(1)(2)(3)(4)(5)
15
>>> sum5(1, 2, 3)(4, 5)
15
Functional style for error-handling
-----------------------------------
``fn.monad.Option`` represents optional values, each instance of ``Option`` can be either instance of ``Full`` or ``Empty``. It provides you with simple way to write long computation sequences and get rid of many ``if/else`` blocks. See usage examples below.
Assume that you have ``Request`` class that gives you parameter value by its name. To get uppercase notation for non-empty striped value:
.. code-block:: python
class Request(dict):
def parameter(self, name):
return self.get(name, None)
r = Request(testing="Fixed", empty=" ")
param = r.parameter("testing")
if param is None:
fixed = ""
else:
param = param.strip()
if len(param) == 0:
fixed = ""
else:
fixed = param.upper()
Hmm, looks ugly.. Update code with ``fn.monad.Option``:
.. code-block:: python
from operator import methodcaller
from fn.monad import optionable
class Request(dict):
@optionable
def parameter(self, name):
return self.get(name, None)
r = Request(testing="Fixed", empty=" ")
fixed = r.parameter("testing")
.map(methodcaller("strip"))
.filter(len)
.map(methodcaller("upper"))
.get_or("")
``fn.monad.Option.or_call`` is good method for trying several variant to end computation. I.e. use have ``Request`` class with optional attributes ``type``, ``mimetype``, ``url``. You need to evaluate "request type" using at least one attribute:
.. code-block:: python
from fn.monad import Option
request = dict(url="face.png", mimetype="PNG")
tp = Option \
.from_value(request.get("type", None)) \ # check "type" key first
.or_call(from_mimetype, request) \ # or.. check "mimetype" key
.or_call(from_extension, request) \ # or... get "url" and check extension
.get_or("application/undefined")
Installation
------------
To install ``fn.py``, simply:
.. code-block:: console
$ pip install fn
Or, if you absolutely must:
.. code-block:: console
$ easy_install fn
You can also build library from source
.. code-block:: console
$ git clone https://github.com/kachayev/fn.py.git
$ cd fn.py
$ python setup.py install
Work in progress
----------------
"Roadmap":
- ``fn.monad.Either`` to deal with error logging
- C-accelerator for most modules
Ideas to think about:
- Scala-style for-yield loop to simplify long map/filter blocks
Contribute
----------
1. Check for open issues or open a fresh issue to start a discussion
around a feature idea or a bug.
2. Fork the repository on Github to start making your changes to the
master branch (or branch off of it).
3. Write a test which shows that the bug was fixed or that the feature
works as expected.
How to find me
--------------
- Twitter: `@kachayev <https://twitter.com/kachayev>`_
- Email: kachayev <at> gmail.com
History
=======
06.04.2013
----------
- added initial origin param to ``fn.Stream``
- ``monad.Option`` is flatten by default, Full(Empty) -> Empty, Empty(Full) -> Empty
- added ``op.unfold`` operator
31.03.2013
----------
- added example of using tail call optimization with changing callable
16.02.2013
----------
- fixed @23 about flipping of underscore function
- added special uniform module
- fixed @22 (underscore functions representation)
- adjustments to unary operators processing in underscore
02.02.2013
----------
- prelimitary implementation of ``recur.tco`` to deal with recursive functions
- ``iters.flatten`` is reimplemented to work with different iterators
27.01.2013
----------
- ``iters.accumulate`` - backported version for Python < 3.3
- first implementation for ``monad.Option`` with tests and README samples
23.01.2013
----------
- ``fn.Stream`` slice is another ``fn.Stream``
- ``fn.Stream`` got new public method ``cursor`` to get position on next evaluated element
21.01.2013
----------
- Update documentation with special ``fn._`` use cases for interactive shells
- Move ``zipwith`` from ``fn.iters`` to ``fn.op``
- ``fn._`` dump to string
18.01.2013
----------
- Added 22 itertools recipes to ``fn.iters``
- Documentation is converted to RST
17.01.2013
----------
- Unit tests coverage for ``fn.stream.Stream``
- ``_StreamIterator`` works fine both in Python 2/3
16.01.2013
----------
- Finished underscore module functionality
- Test cases for all implemented modules/functions
- Update in Readme file with several fixes
- Get rid of F.flip classmethod in pref. for simple building blocks
- Optimized version for fn.op.flip operator
14.01.2013
----------
- Simplest ``Stream`` implementation
- Code samples for streams, labdas (``_``) and functions compositions
- Plan, contribute section in readme file
13.01.2013
----------
- Full list of ideas on paper
- Repository is created
- Initial commit
Raw data
{
"_id": null,
"home_page": "https://github.com/kachayev/fn.py",
"name": "fn",
"maintainer": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": null,
"author": "Alexey Kachayev",
"author_email": "kachayev@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/a2/32/9d184dc2e8225af558e155a3865d610df8533d5d48a2ed5943bf8a30a137/fn-0.4.3.tar.gz",
"platform": "UNKNOWN",
"description": "Fn.py: enjoy FP in Python\n=========================\n\nDespite the fact that Python is not pure-functional programming\nlanguage, it's multi-paradigm PL and it gives you enough freedom to take\ncredits from functional programming approach. There are theoretical and\npractical advantages to the functional style:\n\n- Formal provability\n- Modularity\n- Composability\n- Ease of debugging and testing\n\n``Fn.py`` library provides you with missing \"batteries\" to get maximum\nfrom functional approach even in mostly-imperative program.\n\nMore about functional approach from my Pycon UA 2012 talks: `Functional\nProgramming with\nPython <http://kachayev.github.com/talks/uapycon2012/index.html>`_.\n\nScala-style lambdas definition\n------------------------------\n\n.. code-block:: python\n\n from fn import _\n from fn.op import zipwith\n from itertools import repeat\n\n assert list(map(_ * 2, range(5))) == [0,2,4,6,8]\n assert list(filter(_ < 10, [9,10,11])) == [9]\n assert list(zipwith(_ + _)([0,1,2], repeat(10))) == [10,11,12]\n\nMore examples of using ``_`` you can find in `test\ncases <https://github.com/kachayev/fn.py/blob/master/tests.py>`_\ndeclaration (attributes resolving, method calling, slicing).\n\n**Attention!** If you work in interactive python shell, your should remember that ``_`` means \"latest output\" and you'll get unpredictable results. In this case, you can do something like ``from fn import _ as X`` (and then write functions like ``X * 2``).\n\nIf you are not sure, what your function is going to do, you can print it:\n\n.. code-block:: python\n\n from fn import _\n\n print (_ + 2) # \"(x1) => (x1 + 2)\"\n print (_ + _ * _) # \"(x1, x2, x3) => (x1 + (x2 * x3))\"\n\n``_`` will fail with ``ArityError`` (``TypeError`` subclass) on inaccurate number of passed arguments. This is one more restrictions to ensure that you did everything right: \n\n.. code-block:: python\n\n >>> from fn import _\n >>> (_ + _)(1)\n Traceback (most recent call last):\n File \"<stdin>\", line 1, in <module>\n File \"fn/underscore.py\", line 82, in __call__\n raise ArityError(self, self._arity, len(args))\n fn.underscore.ArityError: (_ + _) expected 2 arguments, got 1\n\n\nPersistent data structures\n--------------------------\n\n**Attention:** Persistent data structures are under active development.\n\nPersistent data structure is a data structure that always preserves the previous version of itself when it is modified (more formal information on `Wikipedia <http://goo.gl/8VveOH>`_). Each operation with such data structure yields a new updated structure instead of in-place modification (all previous versions are potentially available or GC-ed when possible).\n\nLets take a quick look:\n\n.. code-block:: python\n\n >>> from fn.immutable import SkewHeap\n >>> s1 = SkewHeap(10)\n >>> s2 = s1.insert(20)\n >>> s2\n <fn.immutable.heap.SkewHeap object at 0x10b14c050>\n >>> s3 = s2.insert(30)\n >>> s3\n <fn.immutable.heap.SkewHeap object at 0x10b14c158> # <-- other object\n >>> s3.extract()\n (10, <fn.immutable.heap.SkewHeap object at 0x10b14c050>)\n >>> s3.extract() # <-- s3 isn't changed\n (10, <fn.immutable.heap.SkewHeap object at 0x10b11c052>)\n\nIf you think I'm totally crazy and it will work despairingly slow, just give it 5 minutes. Relax, take a deep breath and read about few techniques that make persistent data structures fast and efficient: `structural sharing <http://en.wikipedia.org/wiki/Persistent_data_structure#Examples_of_persistent_data_structures>`_ and `path copying <http://en.wikipedia.org/wiki/Persistent_data_structure#Path_Copying>`_.\n\nTo see how it works in \"pictures\", you can check great slides from Zach Allaun's talk (StrangeLoop 2013): `\"Functional Vectors, Maps And Sets In Julia\" <http://goo.gl/Cp1Qsq>`_.\n\nAnd, if you are brave enough, go and read:\n\n- Chris Okasaki, \"Purely Functional Data Structures\" (`Amazon <http://goo.gl/c7ptkk>`_)\n- Fethi Rabhi and Guy Lapalme, \"Algorithms: A Functional Programming Approach\" (`Amazon <http://goo.gl/00BxTO>`_)\n\nAvailable immutable data structures in ``fn.immutable`` module:\n\n- ``LinkedList``: most \"obvious\" persistent data structure, used as building block for other list-based structures (stack, queue)\n- ``Stack``: wraps linked list implementation with well-known pop/push API\n- ``Queue``: uses two linked lists and lazy copy to provide O(1) enqueue and dequeue operations\n- ``Deque`` (in progress): `\"Confluently Persistent Deques via Data\n Structural Bootstrapping\" <http://goo.gl/vVTzx3>`_\n- ``Deque`` based on ``FingerTree`` data structure (see more information below)\n- ``Vector``: O(log32(n)) access to elements by index (which is near-O(1) for reasonable vector size), implementation is based on ``BitmappedTrie``, almost drop-in replacement for built-in Python ``list``\n- ``SkewHeap``: self-adjusting heap implemented as a binary tree with specific branching model, uses heap merge as basic operation, more information - `\"Self-adjusting heaps\" <http://goo.gl/R1PZME>`_\n- ``PairingHeap``: `\"The Pairing-Heap: A New Form of Self-Adjusting Heap\" <http://goo.gl/aiVtPH>`_\n- ``Dict`` (in progress): persistent hash map implementation based on ``BitmappedTrie``\n- ``FingerTree`` (in progress): `\"Finger Trees: A Simple General-purpose Data Structure\" <http://goo.gl/Bzo0df>`_\n\nUse appropriate doc strings to get more information about each data structure as well as sample code.\n\nTo get more clear vision of how persistent heaps work (``SkewHeap`` and ``PairingHeap``), you can look at slides from my talk `\"Union-based heaps\" <http://goo.gl/VMgdG2>`_ (with analyzed data structures definitions in Python and Haskell).\n\n**Note.** Most functional languages use persistent data structures as basic building blocks, well-known examples are Clojure, Haskell and Scala. Clojure community puts much effort to popularize programming based on the idea of data immutability. There are few amazing talk given by Rich Hickey (creator of Clojure), you can check them to find answers on both questions \"How?\" and \"Why?\":\n\n- `\"The Value of Values\" <http://goo.gl/137UG5>`_\n- `\"Persistent Data Structures and Managed References\" <http://goo.gl/M3vZ7E>`_\n\nStreams and infinite sequences declaration\n------------------------------------------\n\nLazy-evaluated Scala-style streams. Basic idea: evaluate each new\nelement \"on demand\" and share calculated elements between all created\niterators. ``Stream`` object supports ``<<`` operator that means pushing\nnew elements when it's necessary.\n\nSimplest cases:\n\n.. code-block:: python\n\n from fn import Stream\n\n s = Stream() << [1,2,3,4,5]\n assert list(s) == [1,2,3,4,5]\n assert s[1] == 2\n assert list(s[0:2]) == [1,2]\n\n s = Stream() << range(6) << [6,7]\n assert list(s) == [0,1,2,3,4,5,6,7]\n\n def gen():\n yield 1\n yield 2\n yield 3\n\n s = Stream() << gen << (4,5)\n assert list(s) == [1,2,3,4,5]\n\nLazy-evaluated stream is useful for infinite sequences, i.e. fibonacci\nsequence can be calculated as:\n\n.. code-block:: python\n\n from fn import Stream\n from fn.iters import take, drop, map\n from operator import add\n\n f = Stream()\n fib = f << [0, 1] << map(add, f, drop(1, f))\n\n assert list(take(10, fib)) == [0,1,1,2,3,5,8,13,21,34]\n assert fib[20] == 6765\n assert list(fib[30:35]) == [832040,1346269,2178309,3524578,5702887]\n\nTrampolines decorator\n---------------------\n\n``fn.recur.tco`` is a workaround for dealing with TCO without heavy stack utilization. Let's start from simple example of recursive factorial calculation:\n\n.. code-block:: python\n\n def fact(n):\n if n == 0: return 1\n return n * fact(n-1)\n\nThis variant works, but it's really ugly. Why? It will utilize memory too heavy cause of recursive storing all previous values to calculate final result. If you will execute this function with big ``n`` (more then ``sys.getrecursionlimit()``) CPython will fail with \n\n.. code-block:: python\n\n >>> import sys\n >>> fact(sys.getrecursionlimit() * 2)\n ... many many lines of stacktrace ...\n RuntimeError: maximum recursion depth exceeded\n\nWhich is good, cause it prevents you from terrible mistakes in your code.\n\nHow can we optimize this solution? Answer is simple, lets transform function to use tail call:\n\n.. code-block:: python\n\n def fact(n, acc=1):\n if n == 0: return acc\n return fact(n-1, acc*n)\n\nWhy this variant is better? Cause you don't need to remember previous values to calculate final result. More about `tail call optimization <http://en.wikipedia.org/wiki/Tail_call>`_ on Wikipedia. But... Python interpreter will execute this function the same way as previous one, so you won't win anything.\n\n``fn.recur.tco`` gives you mechanism to write \"optimized a bit\" tail call recursion (using \"trampoline\" approach):\n\n.. code-block:: python\n\n from fn import recur\n\n @recur.tco\n def fact(n, acc=1):\n if n == 0: return False, acc\n return True, (n-1, acc*n)\n\n``@recur.tco`` is a decorator that execute your function in ``while`` loop and check output: \n\n- ``(False, result)`` means that we finished \n- ``(True, args, kwargs)`` means that we need to call function again with other arguments\n- ``(func, args, kwargs)`` to switch function to be executed inside while loop\n\nThe last variant is really useful, when you need to switch callable inside evaluation loop. Good example for such situation is recursive detection if given number is odd or even:\n\n.. code-block:: python\n\n >>> from fn import recur\n >>> @recur.tco\n ... def even(x):\n ... if x == 0: return False, True\n ... return odd, (x-1,)\n ... \n >>> @recur.tco\n ... def odd(x):\n ... if x == 0: return False, False\n ... return even, (x-1,)\n ... \n >>> print even(100000)\n True\n\n**Attention:** be careful with mutable/immutable data structures processing.\n\nItertools recipes\n-----------------\n\n``fn.uniform`` provides you with \"unification\"\nof lazy functionality for few functions to work the same way in Python\n2+/3+:\n\n- ``map`` (returns ``itertools.imap`` in Python 2+)\n- ``filter`` (returns ``itertools.ifilter`` in Python 2+)\n- ``reduce`` (returns ``functools.reduce`` in Python 3+)\n- ``zip`` (returns ``itertools.izip`` in Python 2+)\n- ``range`` (returns ``xrange`` in Python 2+)\n- ``filterfalse`` (returns ``itertools.ifilterfalse`` in Python 2+)\n- ``zip_longest`` (returns ``itertools.izip_longest`` in Python 2+)\n- ``accumulate`` (backported to Python < 3.3)\n\n``fn.iters`` is high-level recipes to work with iterators. Most\nof them taken from `Python\ndocs <http://docs.python.org/2.7/library/itertools.html#itertools.product>`_\nand adopted to work both with Python 2+/3+. Such recipes as ``drop``,\n``takelast``, ``droplast``, ``splitat``, ``splitby`` I have already\nsubmitted as `docs patch <http://bugs.python.org/issue16774>`_ which is\nreview status just now.\n\n- ``take``, ``drop``\n- ``takelast``, ``droplast``\n- ``head`` (alias: ``first``), ``tail`` (alias: ``rest``)\n- ``second``, ``ffirst``\n- ``compact``, ``reject``\n- ``iterate``\n- ``consume``\n- ``nth``\n- ``padnone``, ``ncycles``\n- ``repeatfunc``\n- ``grouper``, ``powerset``, ``pairwise``\n- ``roundrobin``\n- ``partition``, ``splitat``, ``splitby``\n- ``flatten``\n- ``iter_except``\n\nMore information about use cases you can find in docstrings for each\nfunction in `source\ncode <https://github.com/kachayev/fn.py/blob/master/fn/iters.py>`__ and\nin `test\ncases <https://github.com/kachayev/fn.py/blob/master/tests.py>`_.\n\nHigh-level operations with functions\n------------------------------------\n\n``fn.F`` is a useful function wrapper to provide easy-to-use partial\napplication and functions composition.\n\n.. code-block:: python\n\n from fn import F, _\n from operator import add, mul\n\n # F(f, *args) means partial application \n # same as functools.partial but returns fn.F instance\n assert F(add, 1)(10) == 11\n\n # F << F means functions composition,\n # so (F(f) << g)(x) == f(g(x))\n f = F(add, 1) << F(mul, 100)\n assert list(map(f, [0, 1, 2])) == [1, 101, 201]\n assert list(map(F() << str << (_ ** 2) << (_ + 1), range(3))) == [\"1\", \"4\", \"9\"]\n\nIt also give you move readable in many cases \"pipe\" notation to deal with functions composition:\n\n.. code-block:: python\n\n from fn import F, _\n from fn.iters import filter, range\n\n func = F() >> (filter, _ < 6) >> sum\n assert func(range(10)) == 15\n\nYou can find more examples for compositions usage in ``fn._``\nimplementation `source\ncode <https://github.com/kachayev/fn.py/blob/master/fn/underscore.py>`__.\n\n``fn.op.apply`` executes given function with given positional arguments\nin list (or any other iterable). ``fn.op.flip`` returns you function\nthat will reverse arguments order before apply.\n\n.. code-block:: python\n\n from fn.op import apply, flip\n from operator import add, sub\n\n assert apply(add, [1, 2]) == 3\n assert flip(sub)(20,10) == -10\n assert list(map(apply, [add, mul], [(1,2), (10,20)])) == [3, 200]\n\n``fn.op.foldl`` and ``fn.op.foldr`` are folding operators. Each accepts function with arity 2 and returns function that can be used to reduce iterable to scalar: from left-to-right and from right-to-left in case of ``foldl`` and ``foldr`` respectively. \n\n.. code-block:: python\n\n from fn import op, _\n\n folder = op.foldr(_ * _, 1)\n assert 6 == op.foldl(_ + _)([1,2,3])\n assert 6 == folder([1,2,3])\n\nUse case specific for right-side folding is:\n\n.. code-block:: python\n \n from fn.op import foldr, call \n\n assert 100 == foldr(call, 0 )([lambda s: s**2, lambda k: k+10])\n assert 400 == foldr(call, 10)([lambda s: s**2, lambda k: k+10])\n\n\nFunction currying\n-----------------\n\n``fn.func.curried`` is a decorator for building curried functions, for example:\n\n.. code-block:: python\n\n >>> from fn.func import curried\n >>> @curried\n ... def sum5(a, b, c, d, e):\n ... return a + b + c + d + e\n ...\n >>> sum5(1)(2)(3)(4)(5)\n 15\n >>> sum5(1, 2, 3)(4, 5)\n 15\n\n\nFunctional style for error-handling\n-----------------------------------\n\n``fn.monad.Option`` represents optional values, each instance of ``Option`` can be either instance of ``Full`` or ``Empty``. It provides you with simple way to write long computation sequences and get rid of many ``if/else`` blocks. See usage examples below. \n\nAssume that you have ``Request`` class that gives you parameter value by its name. To get uppercase notation for non-empty striped value:\n\n.. code-block:: python\n\n class Request(dict):\n def parameter(self, name):\n return self.get(name, None)\n\n r = Request(testing=\"Fixed\", empty=\" \")\n param = r.parameter(\"testing\")\n if param is None:\n fixed = \"\"\n else:\n param = param.strip()\n if len(param) == 0:\n fixed = \"\"\n else:\n fixed = param.upper()\n\n\nHmm, looks ugly.. Update code with ``fn.monad.Option``:\n\n.. code-block:: python\n\n from operator import methodcaller\n from fn.monad import optionable\n\n class Request(dict):\n @optionable\n def parameter(self, name):\n return self.get(name, None)\n\n r = Request(testing=\"Fixed\", empty=\" \")\n fixed = r.parameter(\"testing\")\n .map(methodcaller(\"strip\"))\n .filter(len)\n .map(methodcaller(\"upper\"))\n .get_or(\"\")\n\n``fn.monad.Option.or_call`` is good method for trying several variant to end computation. I.e. use have ``Request`` class with optional attributes ``type``, ``mimetype``, ``url``. You need to evaluate \"request type\" using at least one attribute:\n\n.. code-block:: python\n\n from fn.monad import Option\n\n request = dict(url=\"face.png\", mimetype=\"PNG\")\n tp = Option \\\n .from_value(request.get(\"type\", None)) \\ # check \"type\" key first\n .or_call(from_mimetype, request) \\ # or.. check \"mimetype\" key\n .or_call(from_extension, request) \\ # or... get \"url\" and check extension\n .get_or(\"application/undefined\")\n\n\nInstallation\n------------\n\nTo install ``fn.py``, simply:\n\n.. code-block:: console\n\n $ pip install fn\n\nOr, if you absolutely must:\n\n.. code-block:: console\n\n $ easy_install fn\n\nYou can also build library from source\n\n.. code-block:: console\n\n $ git clone https://github.com/kachayev/fn.py.git\n $ cd fn.py\n $ python setup.py install\n\nWork in progress\n----------------\n\n\"Roadmap\":\n\n- ``fn.monad.Either`` to deal with error logging \n- C-accelerator for most modules\n\nIdeas to think about:\n\n- Scala-style for-yield loop to simplify long map/filter blocks\n\nContribute\n----------\n\n1. Check for open issues or open a fresh issue to start a discussion\n around a feature idea or a bug.\n2. Fork the repository on Github to start making your changes to the\n master branch (or branch off of it).\n3. Write a test which shows that the bug was fixed or that the feature\n works as expected.\n\nHow to find me\n--------------\n\n- Twitter: `@kachayev <https://twitter.com/kachayev>`_\n- Email: kachayev <at> gmail.com\n\n\nHistory\n=======\n\n06.04.2013\n----------\n\n- added initial origin param to ``fn.Stream``\n- ``monad.Option`` is flatten by default, Full(Empty) -> Empty, Empty(Full) -> Empty\n- added ``op.unfold`` operator \n\n31.03.2013\n----------\n\n- added example of using tail call optimization with changing callable\n\n16.02.2013\n----------\n\n- fixed @23 about flipping of underscore function\n- added special uniform module\n- fixed @22 (underscore functions representation)\n- adjustments to unary operators processing in underscore\n\n02.02.2013\n----------\n\n- prelimitary implementation of ``recur.tco`` to deal with recursive functions\n- ``iters.flatten`` is reimplemented to work with different iterators\n\n27.01.2013\n----------\n\n- ``iters.accumulate`` - backported version for Python < 3.3\n- first implementation for ``monad.Option`` with tests and README samples\n\n23.01.2013\n----------\n\n- ``fn.Stream`` slice is another ``fn.Stream``\n- ``fn.Stream`` got new public method ``cursor`` to get position on next evaluated element\n\n21.01.2013\n----------\n\n- Update documentation with special ``fn._`` use cases for interactive shells\n- Move ``zipwith`` from ``fn.iters`` to ``fn.op``\n- ``fn._`` dump to string\n\n18.01.2013\n----------\n\n- Added 22 itertools recipes to ``fn.iters``\n- Documentation is converted to RST\n\n17.01.2013\n----------\n\n- Unit tests coverage for ``fn.stream.Stream``\n- ``_StreamIterator`` works fine both in Python 2/3\n\n16.01.2013\n----------\n\n- Finished underscore module functionality\n- Test cases for all implemented modules/functions\n- Update in Readme file with several fixes\n- Get rid of F.flip classmethod in pref. for simple building blocks\n- Optimized version for fn.op.flip operator\n\n14.01.2013\n----------\n\n- Simplest ``Stream`` implementation\n- Code samples for streams, labdas (``_``) and functions compositions\n- Plan, contribute section in readme file\n\n13.01.2013\n----------\n\n- Full list of ideas on paper\n- Repository is created\n- Initial commit",
"bugtrack_url": null,
"license": "Copyright 2013 Alexey Kachayev\n\n Licensed under the Apache License, Version 2.0 (the \"License\");\n you may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n http://www.apache.org/licenses/LICENSE-2.0\n\n Unless required by applicable law or agreed to in writing, software\n distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions and\n limitations under the License.",
"summary": "Implementation of missing features to enjoy functional programming in Python",
"version": "0.4.3",
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "a2329d184dc2e8225af558e155a3865d610df8533d5d48a2ed5943bf8a30a137",
"md5": "757108fd7e1ac574ee32e7993740d4a3",
"sha256": "f8cd80cdabf15367a2f07e7a9951fdc013d7200412743d85b88f2c896c95bada"
},
"downloads": -1,
"filename": "fn-0.4.3.tar.gz",
"has_sig": false,
"md5_digest": "757108fd7e1ac574ee32e7993740d4a3",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 38634,
"upload_time": "2014-08-08T11:02:13",
"upload_time_iso_8601": "2014-08-08T11:02:13.890249Z",
"url": "https://files.pythonhosted.org/packages/a2/32/9d184dc2e8225af558e155a3865d610df8533d5d48a2ed5943bf8a30a137/fn-0.4.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2014-08-08 11:02:13",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "kachayev",
"github_project": "fn.py",
"travis_ci": true,
"coveralls": false,
"github_actions": false,
"lcname": "fn"
}
JSON
