repository·master·Indexed 25 days ago
https://github.com/kachayev/fn.pyA functional programming library for Python providing Scala-style lambdas, persistent data structures via fn.immutable, lazy-evaluated streams, and tail-call optimization (TCO) via @recur.tco. It includes utilities for partial application and composition with fn.F, curried functions, monads for optional values, and comprehensive iterator operations through fn.uniform and fn.iters.
You can install fn.py using pip or easy_install. Alternatively, you can build the library from source using setup.py.
$ pip install fn
# or
$ easy_install fn
# from source
$ git clone https://github.com/kachayev/fn.py.git
$ cd fn.py
$ python setup.py installThe fn.immutable module provides persistent data structures. These structures preserve previous versions when modified, returning a new updated structure instead of modifying the existing one in-place. This is achieved through techniques like structural sharing and path copying.
Available Data Structures:
LinkedList: Building block for other list-based structures.Stack: Wraps LinkedList with pop/push API.Queue: Provides O(1) enqueue and dequeue operations.Vector: O(log32(n)) access; near-drop-in replacement for Python list based on BitmappedTrie.SkewHeap: Self-adjusting binary tree heap.PairingHeap: Another self-adjusting heap implementation.Deque (in progress): Based on FingerTree.Dict (in progress): Persistent hash map based on BitmappedTrie.FingerTree (in progress).Note: Persistent data structures are under active development.
from fn.immutable import SkewHeap
s1 = SkewHeap(10)
s2 = s1.insert(20)
s3 = s2.insert(30)
s3.extract()The Stream object allows for lazy-evaluated, Scala-style streams. Elements are evaluated on demand, and calculated elements are shared between iterators. You can push new elements into a stream using the << operator.
Streams are particularly useful for defining infinite sequences, such as the Fibonacci sequence.
from fn import Stream
from fn.iters import take, drop, map
from operator import add
# Basic Stream usage
s = Stream() << [1,2,3,4,5]
# Infinite Fibonacci sequence
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]@fn.func.curried decorator to transform a standard function into a curried function, allowing it to be called with one argument at a time or in partial groups.Use the _ symbol from fn to define concise, Scala-style lambdas. This symbol acts as a placeholder for arguments in functional operations like map, filter, and zipwith.
Note for Interactive Shells: In interactive Python shells, _ represents the last output. To avoid conflicts, import it with an alias: from fn import _ as X.
If the number of arguments provided does not match the number of underscores in the expression, an ArityError (a subclass of TypeError) will be raised.
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]The fn.monad.Option type (with implementations Full and Empty) provides a functional way to handle optional values and avoid if/else chains.
@optionable to decorate methods that should return an Option..map(func) to transform the value if it exists..filter(predicate) to discard the value if it doesn't meet a condition..get_or(default) to retrieve the value or a fallback..or_call(func, *args) to attempt an alternative computation if the current Option is empty.The fn.op module provides utilities for applying functions to iterables and performing folds.
apply(f, args): Executes function f with the positional arguments provided in the args iterable.flip(f): Returns a new function that reverses the order of arguments before applying f.foldl(f, initial): A left-to-right folding operator.foldr(f, initial): A right-to-left folding operator.The @recur.tco decorator in fn.recur provides a trampoline mechanism to handle tail-recursive functions without hitting Python's recursion limit.
To use it, your function must return one of the following:
(False, result): Indicates the recursion is finished and returns the final result.(True, args, kwargs): Indicates the function should be called again with the provided arguments.(func, args, kwargs): Indicates the loop should switch to a different callable with the provided arguments.Warning: Be careful when processing mutable/immutable data structures within a trampoline.
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
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)) # TrueThe fn.F wrapper provides functional utilities for partial application and function composition.
F(f, *args) creates a new function with the provided arguments pre-applied (similar to functools.partial).<< operator for left-to-right composition: (F(f) << g)(x) is equivalent to f(g(x)).>> operator to create a readable pipeline of operations.from fn import F, _
from fn.iters import filter, range
from operator import add, mul
# Partial application
assert F(add, 1)(10) == 11
# Function composition (f << g means f(g(x)))
f = F(add, 1) << F(mul, 100)
assert list(map(f, [0, 1, 2])) == [1, 101, 201]
# Pipe notation (>>)
func = F() >> (filter, _ < 6) >> sum
assert func(range(10)) == 15Fn.py provides two main modules for iterator-related tasks:
fn.uniform: Provides a unified interface for common functional primitives to ensure consistent behavior across Python 2 and 3. It includes:
map, filter, reduce, zip, range, filterfalse, zip_longest, accumulate.fn.iters: High-level recipes for working with iterators. Key functions include:
take, drop, takelast, droplasthead (alias: first), tail (alias: rest)second, ffirstcompact, rejectevery, someiterate, consume, nthpadnone, ncycles, repeatfuncgrouper, powerset, pairwise, roundrobinpartition, splitat, splitbyflatten, iter_except, first_true