haskpy.types.linkedlist.LinkedList

LinkedList

class LinkedList(match)

Bases: Monad, Monoid, Foldable, Eq

Linked-list with “lazy” Cons

The “lazy” Cons makes it possible to construct infinite lists. For instance, an infinite list of a repeated value 42 can be constructed as:

>>> repeat(42)
Cons(42, Cons(42, Cons(42, Cons(42, Cons(42, Cons(42, ...))))))

You can use, for instance, scanl and map to create more complex infinite lists from a simple one:

>>> xs = repeat(1).scanl(lambda acc, x: acc + x)
>>> xs
Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Cons(6, ...))))))
>>> xs.map(lambda x: x ** 2)
Cons(1, Cons(4, Cons(9, Cons(16, Cons(25, Cons(36, ...))))))

Note that this works also for very long lists:

>>> xs.drop(10000)
Cons(10001, Cons(10002, Cons(10003, Cons(10004, Cons(10005, Cons(10006, ...))))))

One can create infinite lists by using a recursive definition:

>>> xs = Cons(42, lambda: xs)

But beware that this kind of recursive definition doesn’t always work as one might expect. For instance, the following construction causes huge recursion depths:

>>> xs = Cons(1, lambda: xs.map(lambda y: y + 1))
>>> xs
Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil)))))
>>> xs.drop(10000)
RecursionError: maximum recursion depth exceeded while calling a Python object

This happens because each value depends recursively on all the previous values

__add__(other)

Append two monoids

Using + operator to append two monoid values seems natural because that’s what Python is doing by default because lists are concatenated with +.

__annotations__ = {}

__contains__(x)

Override elem if you want to change the default implementation

__eq__(other)

LinkedList a -> LinkedList a -> bool

__eq_test__(other, data=None)

__hash__ = None

__iter__()

Override to_iter if you want to change the default implementation

__len__()

Override length if you want to change the default implementation

__lshift__(x)

Sequence with << similarly as with <* and << in Haskell

__matmul__(x)

Application operand @ applies similarly as <*> in Haskell

f @ x translates to f.apply_to(x), x.apply(f) and apply(f, x).

Why @ operator?

• It’s not typically used as often as some other more common operators so less risk for confusion.

• The operator is not a commutative as isn’t apply either.

• If we see matrix as some structure, then matrix multiplication takes both left and right operand inside this structure and gives a result also inside this structure, similarly as apply does. So it’s an operator for two operands having a similar structure.

• The operator evaluates the contained function(s) at the contained value(s). Thus, f “at” x makes perfect sense.

__mod__(f)

Use % as bind operator similarly as >>= in Haskell

That is, x % f is equivalent to bind(x, f) and x.bind(f).

Why % operator?

• It’s not very often used so less risk for confusion.

• It’s not commutative as isn’t bind either.

• It is similar to bind in a sense that the result has the same unit as the left operand while the right operand has different unit.

• The symbol works visually as a line “binds” two circles and on the other hand two circles tell about two similar structures on both sides but those structures are just on different “level”.

__ne__(other)

Inequality comparison: Eq a => a -> a -> bool

Can be used as != operator.

The default implementation uses __eq__.

__repr(maxdepth=5)

__rpow__(f)

Lifting operator ** lifts similarly as <$> in Haskell

f ** x translates to x.map(f) and map(f, x).

Why ** operator?

• It’s not typically used as often as multiplication or addition so less risk of confusion.

• It’s not commutative operator as isn’t lifting either.

• The two operands have very different roles. They are not at the same “level”.

• The right operand is “higher”, that is, it’s inside a structure and the left operand is kind of “raised to the power” of the second operand, where the “power” is the functorial structure.

• The same operand is also used for function composition because function composition is just mapping. Visually the symbol can be seen as chaining two stars similarly as function composition chains two functions.

__rshift__(x)

Sequence with >> similarly as with *> and >> in Haskell

_scanl(f, acc)

append(ys)

LinkedList a -> LinkedList a -> LinkedList a

apply(f)

m a -> m (a -> b) -> m b

self :: m a

f :: m (a -> b)

Default implementation is based on bind and map. In order to use bind, let’s write its type as follows:

bind :: m (a -> b) -> ((a -> b) -> m b) -> m b

Let’s also use a simple helper function:

h = g -> map g self :: (a -> b) -> m b

Now:

bind f h :: m b

apply_first(x)

Combine two actions, keeping only the result of the first

Apply f => f a -> f b -> f a

apply_second(x)

Combine two actions, keeping only the result of the second

Apply f => f a -> f b -> f b

apply_to(x)

f (a -> b) -> f a -> f b

Default implementation is based on apply.

bind(f)

List a -> (a -> List b) -> List b

drop(n)

elem(x)

t a -> a -> bool

empty = Nil

flap(x)

Functor f => f (a -> b) -> a - > f b

fold(monoid)

fold2(monoid)

fold_map(monoid, f)

Monoid m => t a -> (a -> m) -> m (ignoring monoid argument)

The default implementation is based on foldl (or, if not implemented, recursively on foldr). Thus, all possibilities for parallelism is lost.

monoid is the monoidic class of the values inside the foldable. It is only used to determine the identity value.

foldl(combine, initial)

Foldable t => t a -> (b -> a -> b) -> b -> b

Strict left-associative fold

((((a + b) + c) + d) + e)

foldr(combine, initial)

Foldable t => t a -> (a -> b -> b) -> b -> b

Strict right-associative fold. Note that this doesn’t work for infinite lists because it’s strict. You probably want to use foldr_lazy or foldl instead as this function easily exceeds Python maximum recursion depth (or the stack overflows).

..code-block:: python

>>> xs = iterate(lambda x: x + 1, 1)
>>> xs.foldr(lambda y, ys: Cons(2 * y, lambda: ys), Nil)
RecursionError: maximum recursion depth exceeded while calling a Python object

foldr_lazy(combine, initial)

Foldable t => t a -> (a -> (() -> b) -> (() -> b)) -> b -> b

Nonstrict right-associative fold with support for lazy recursion, short-circuiting and tail-call optimization.

HOW ABOUT [a,b,c,d,e,f,g,h,…] -> (a(b(c(d(e))))) UNTIL TOTAL STRING LENGTH IS X?

Parameters:

combinecurried function

See also

haskpy.typeclasses.foldable.foldr_lazy

head(default)

Return head (or default if no head): f a -> a -> a

join()

m (m a) -> m a

Default implementation is based on bind:

self :: m (m a)

identity :: m a -> m a

bind :: m (m a) -> (m a -> m a) -> m a

length()

t a -> int

The default implementation isn’t very efficient as it traverses through the iterator.

map(f)

List a -> (a -> b) -> List b

null()

t a -> bool

pure(x)

a -> LinkedList a

recurse_tco(f, g, acc)

Recursion with tail-call optimization

Type signature:

LinkedList a -> (b -> a -> Either c b) -> (b -> c) -> b -> c

where a is the type of the elements in the linked list, b is the type of the accumulated value and c is the type of the result. Quite often, the accumulated value is also the end result, so b is c and g is an identity function.

As Python supports recursion very badly, some typical recursion patterns are implemented as methods that convert specific recursions to efficients loops. This method implements the following pattern:

>>> return self.match(
...     Nil=lambda: g(acc),
...     Cons=lambda x, lxs: f(acc, x).match(
...         Left=lambda y: y,
...         Right=lambda y: lxs().recurse_tco(f, g, y)
...     )
... )

This recursion method supports short-circuiting and simple tail-call optimization. A value inside Left stops the recursion and returns the value. A value inside Right continues the recursion with the updated accumulated value.

See also

foldl

foldr

foldr_lazy

Examples

For instance, the following recursion calculates the sum of the list elements until the sum exceeds one million:

>>> from haskpy import Left, Right, iterate
>>> xs = iterate(lambda x: x + 1, 1)
>>> my_sum = lambda xs, acc: xs.match(
...     Nil=lambda: acc,
...     Cons=lambda y, ys: acc if acc > 1000000 else my_sum(xs, acc + y)
... )
>>> my_sum(xs, 0)

Unfortunately, this recursion exceeds Python maximum recursion depth because 1000000 is a large enough number. Note that this cannot be implemented with foldl because it doesn’t support short-circuiting. Also, foldr doesn’t work because it’s right-associative so it cannot short-circuit based on the accumulator. But it can be calculated with this recurse_tco method which converts the recursion into a loop internally:

>>> xs.recurse_tco(
...     lambda acc, x: Left(acc) if acc > 1000000 else Right(acc + x),
...     lambda acc: acc,
...     0
... )

replace(x)

Haskell ($>) operator

scanl(f)

sum()

t a -> number

take(n)

to_iter()

t a -> Iter a

Instead of to_list (as in Haskell), let’s provide to_iter. With iterables, we can write efficient implementations for many other methods (e.g., sum, elem) even for large or sometimes infinite foldables.

The default implementation isn’t very efficient as it uses folding to construct the iterator.