319 lines
8.5 KiB
Python
319 lines
8.5 KiB
Python
from abc import abstractmethod
|
|
from functools import partial, reduce
|
|
|
|
from typing import Callable, Iterator, TypeVar, Iterable, Sized, Any, cast, Union
|
|
|
|
from .typing import Applicative
|
|
from .typing import Functor
|
|
from .typing import Monoid
|
|
from .typing import Monad
|
|
|
|
TSource = TypeVar("TSource")
|
|
TResult = TypeVar("TResult")
|
|
TSelector = Callable[[TSource, 'List[TSource]'], Union[TSource, 'List[TSource]']]
|
|
|
|
|
|
class List(Iterable[TSource], Sized):
|
|
"""The list monad.
|
|
|
|
Wraps an immutable list built from lambda expressions.
|
|
"""
|
|
|
|
@classmethod
|
|
def unit(cls, value: Any) -> 'List':
|
|
"""Wrap a value within the singleton list."""
|
|
return List.empty().cons(value)
|
|
|
|
pure = unit
|
|
|
|
@classmethod
|
|
def empty(cls) -> 'List[TSource]':
|
|
"""Create an empty list."""
|
|
return Nil()
|
|
|
|
@classmethod
|
|
def from_iterable(cls, iterable: Iterable) -> 'List':
|
|
"""Create list from iterable."""
|
|
|
|
iterator = iter(iterable)
|
|
|
|
def recurse() -> List:
|
|
try:
|
|
value = next(iterator)
|
|
except StopIteration:
|
|
|
|
return List.empty()
|
|
return List.unit(value).append(recurse())
|
|
return List.empty().append(recurse())
|
|
|
|
@classmethod
|
|
def concat(cls, xs):
|
|
"""mconcat :: [m] -> m
|
|
|
|
Fold a list using the monoid. For most types, the default
|
|
definition for mconcat will be used, but the function is
|
|
included in the class definition so that an optimized version
|
|
can be provided for specific types.
|
|
"""
|
|
|
|
def reducer(a, b):
|
|
return a + b
|
|
|
|
return reduce(reducer, xs, Nil())
|
|
|
|
@abstractmethod
|
|
def head(self) -> TSource:
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def tail(self) -> 'List[TSource]':
|
|
"""Return tail of List."""
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def apply(self, something: 'List') -> 'List':
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def map(self, mapper: Callable[[TSource], TResult]) -> 'List[TResult]':
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def bind(self, fn: Callable[[TSource], 'List[TResult]']) -> 'List[TResult]':
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def cons(self, element: TSource) -> 'List[TSource]':
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def append(self, other: 'List[TSource]') -> 'List[TSource]':
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def null(self) -> bool:
|
|
"""Return True if List is empty."""
|
|
raise NotImplementedError
|
|
|
|
@abstractmethod
|
|
def __add__(self, other):
|
|
raise NotImplementedError
|
|
|
|
|
|
class Cons(List[TSource]):
|
|
"""The list cons case monad."""
|
|
|
|
def __init__(self, run: Callable[[TSelector], Union[TSource, List[TSource]]]) -> None:
|
|
"""Initialize List."""
|
|
|
|
self._list = run
|
|
|
|
def cons(self, element: TSource) -> List[TSource]:
|
|
"""Add element to front of List."""
|
|
|
|
return Cons(lambda sel: sel(element, self))
|
|
|
|
def head(self) -> TSource:
|
|
"""Retrive first element in List."""
|
|
|
|
run = self._list
|
|
return cast(TSource, run(lambda head, _: head))
|
|
|
|
def tail(self) -> 'List[TSource]':
|
|
"""Return tail of List."""
|
|
|
|
run = self._list
|
|
return cast(List[TSource], run(lambda _, tail: tail))
|
|
|
|
def null(self) -> bool:
|
|
"""Return True if List is empty."""
|
|
return False
|
|
|
|
def map(self, mapper: Callable[[TSource], TResult]) -> List[TResult]:
|
|
"""Map a function over a List."""
|
|
return (self.tail().map(mapper)).cons(mapper(self.head()))
|
|
|
|
def apply(self, something: 'List') -> 'List':
|
|
# fs <*> xs = [f x | f <- fs, x <- xs]
|
|
try:
|
|
xs = [f(x) for f in self for x in something]
|
|
except TypeError:
|
|
xs = [partial(f, x) for f in self for x in something]
|
|
|
|
return List.from_iterable(xs)
|
|
|
|
def append(self, other: List[TSource]) -> List[TSource]:
|
|
"""Append other list to this list."""
|
|
|
|
return (self.tail().append(other)).cons(self.head())
|
|
|
|
def bind(self, fn: Callable[[TSource], List[TResult]]) -> List[TResult]:
|
|
"""Flatten and map the List.
|
|
|
|
Haskell: xs >>= f = concat (map f xs)
|
|
"""
|
|
return List.concat(self.map(fn))
|
|
|
|
def __iter__(self) -> Iterator:
|
|
"""Return iterator for List."""
|
|
|
|
yield self.head()
|
|
yield from self.tail()
|
|
|
|
def __or__(self, func):
|
|
"""Use | as operator for bind.
|
|
|
|
Provide the | operator instead of the Haskell >>= operator
|
|
"""
|
|
return self.bind(func)
|
|
|
|
def __rshift__(self, next):
|
|
"""The "Then" operator.
|
|
|
|
Sequentially compose two monadic actions, discarding any value
|
|
produced by the first, like sequencing operators (such as the
|
|
semicolon) in imperative languages.
|
|
|
|
Haskell: (>>) :: m a -> m b -> m b
|
|
"""
|
|
return self.bind(lambda _: next)
|
|
|
|
def __add__(self, other):
|
|
return self.append(other)
|
|
|
|
def __len__(self) -> int:
|
|
"""Return length of List."""
|
|
|
|
return 1 + len(self.tail())
|
|
|
|
def __str__(self) -> str:
|
|
"""Return string representation of List."""
|
|
|
|
return "[%s]" % ", ".join([str(x) for x in self])
|
|
|
|
def __repr__(self) -> str:
|
|
"""Return string representation of List."""
|
|
|
|
return str(self)
|
|
|
|
def __eq__(self, other) -> bool:
|
|
"""Compare if List is equal to other List."""
|
|
|
|
if isinstance(other, Nil):
|
|
return False
|
|
return self.head() == other.head() and self.tail() == other.tail()
|
|
|
|
|
|
class Nil(List[TSource]):
|
|
def __init__(self) -> None:
|
|
"""Initialize List."""
|
|
pass
|
|
|
|
def cons(self, element: TSource) -> 'List[TSource]':
|
|
"""Add element to front of List."""
|
|
|
|
return Cons(lambda sel: sel(element, Nil()))
|
|
|
|
def head(self) -> TSource:
|
|
"""Retrive first element in List."""
|
|
|
|
raise IndexError("List is empty")
|
|
|
|
def tail(self) -> 'List[TSource]':
|
|
"""Return tail of List."""
|
|
|
|
raise IndexError("List is empty")
|
|
|
|
def null(self) -> bool:
|
|
"""Return True if List is empty."""
|
|
return True
|
|
|
|
def map(self, mapper: Callable[[TSource], TResult]) -> List[TResult]:
|
|
"""Map a function over a List."""
|
|
return Nil()
|
|
|
|
def apply(self, something: 'List') -> 'List':
|
|
# fs <*> xs = [f x | f <- fs, x <- xs]
|
|
try:
|
|
xs = [f(x) for f in self for x in something]
|
|
except TypeError:
|
|
xs = [partial(f, x) for f in self for x in something]
|
|
|
|
return List.from_iterable(xs)
|
|
|
|
def append(self, other: List[TSource]) -> List[TSource]:
|
|
"""Append other list to this list."""
|
|
|
|
if self.null():
|
|
return other
|
|
return (self.tail().append(other)).cons(self.head())
|
|
|
|
def bind(self, fn: Callable[[TSource], List[TResult]]) -> List[TResult]:
|
|
"""Flatten and map the List.
|
|
|
|
Haskell: xs >>= f = concat (map f xs)
|
|
"""
|
|
return List.concat(self.map(fn))
|
|
|
|
def __iter__(self) -> Iterator:
|
|
"""Return iterator for List."""
|
|
|
|
while False:
|
|
yield
|
|
|
|
def __or__(self, func):
|
|
"""Use | as operator for bind.
|
|
|
|
Provide the | operator instead of the Haskell >>= operator
|
|
"""
|
|
return self.bind(func)
|
|
|
|
def __rshift__(self, next):
|
|
"""The "Then" operator.
|
|
|
|
Sequentially compose two monadic actions, discarding any value
|
|
produced by the first, like sequencing operators (such as the
|
|
semicolon) in imperative languages.
|
|
|
|
Haskell: (>>) :: m a -> m b -> m b
|
|
"""
|
|
return self.bind(lambda _: next)
|
|
|
|
def __add__(self, other):
|
|
return self.append(other)
|
|
|
|
def __len__(self) -> int:
|
|
"""Return length of List."""
|
|
|
|
return 0
|
|
|
|
def __str__(self) -> str:
|
|
"""Return string representation of List."""
|
|
|
|
return "[%s]" % ", ".join([str(x) for x in self])
|
|
|
|
def __repr__(self) -> str:
|
|
"""Return string representation of List."""
|
|
|
|
return str(self)
|
|
|
|
def __eq__(self, other) -> bool:
|
|
"""Compare if List is equal to other List."""
|
|
|
|
return True if isinstance(other, Nil) else False
|
|
|
|
|
|
assert(isinstance(List, Monoid))
|
|
assert(isinstance(List, Functor))
|
|
assert(isinstance(List, Applicative))
|
|
assert(isinstance(List, Monad))
|
|
|
|
assert(isinstance(Cons, Monoid))
|
|
assert(isinstance(Cons, Functor))
|
|
assert(isinstance(Cons, Applicative))
|
|
assert(isinstance(Cons, Monad))
|
|
|
|
assert(isinstance(Nil, Monoid))
|
|
assert(isinstance(Nil, Functor))
|
|
assert(isinstance(Nil, Applicative))
|
|
assert(isinstance(Nil, Monad))
|