main.coco

# Helpers:

#### Operators:
operator $$  # apply ($)
operator %%  # over (%)
operator <$  # fmapConst
operator <*>  # ap
operator *>  # seqAr
operator <*  # seqAl
operator >>>=  # bind (>>=)
operator >>>  # seqM (>>)
operator =<<<  # bindFrom (=<<)
operator ++  # chain
operator !!  # at


#### Imports:
import sys
import fractions as _fractions
import math as _math
import ast as _ast
from math import gcd as _gcd

from prelude.util import *  # type: ignore

#### Untyped built-ins:
_max: -> T.Any = max
_min: -> T.Any = min
_zip: -> T.Any = zip
_abs: -> T.Any = abs
_round: -> T.Any = round
_fmap: -> T.Any = fmap  # type: ignore
_reduce: -> T.Any = reduce
_all: -> T.Any = all
_any: -> T.Any = any
_map: -> T.Any = map
_filter: -> T.Any = filter
_int: -> T.Any = int
_sum: -> T.Any = sum
_reversed: -> T.Any = reversed
_print: -> T.Any = print
_cycle: -> T.Any = cycle  # type: ignore
_ceil: -> T.Any = _math.ceil
_floor: -> T.Any = _math.floor




# Standard types, classes, and related functions:

## Basic data types:

#### Bool:
Bool = bool

not_: bool -> bool
not_ = (not)

otherwise: bool = True

#### Maybe:
class Maybe:
    @staticmethod
    def __pure__(x: Ta) -> Maybe = Just(x)

    @staticmethod
    def __fail__(msg: str) -> Maybe = nothing

    @staticmethod
    def __mempty__() -> Maybe = nothing

data Nothing() from Maybe:
    """
    -- Nothing is the data type; use nothing for the canonical instance
    """

nothing: Maybe = Nothing()

data Just(x) from Maybe

derivingOrd(Nothing, Just)

case def maybe:
    type(default: Tb, func: Ta -> Tb, x: Maybe) -> Tb

    case(default, _, Nothing()) = default
    case(_, func, Just(x)) = func x

#### Either:
class Either:
    @staticmethod
    def __pure__(x: Ta) -> Either = Right(x)

    @staticmethod
    def __fail__(msg: str) -> Either = Left(msg)

data Left(x) from Either:
    @staticmethod
    def __bool__() -> bool = False

    def __fmap__(self, func: Ta -> Tb) -> Either = self

data Right(x) from Either

derivingOrd(Left, Right)

case def either:
    type(left_func: Ta -> Tc, right_func: Tb -> Tc, x: Either) -> Tc

    case(left_func, _, Left(x)) = left_func x
    case(_, right_func, Right(x)) = right_func x

#### Ordering:
class Ordering:
    @staticmethod
    def __mempty__() -> Ordering = eq

data LT() from Ordering:
    @staticmethod
    def __bool__() -> bool = True

data EQ() from Ordering

data GT() from Ordering:
    @staticmethod
    def __bool__() -> bool = True

derivingOrd(LT, EQ, GT)
derivingBoundedEnum(LT, EQ, GT)

lt: Ordering = LT()
eq: Ordering = EQ()
gt: Ordering = GT()

#### Char:
Char = T.NewType("Char", str)

#### String:
String = str


### Tuples:
fst: (Ta; Tb) -> Ta
fst = .[0]

snd: (Ta; Tb) -> Tb
snd = .[1]

def curry_tuple(func: (Ta; Tb) -> Tc) -> (Ta, Tb) -> Tc =
    """
    -- curry a function of a tuple into a Python-style multi-place function
    """
    (*args) -> func(args)  # type: ignore

def uncurry_tuple(func: (Ta, Tb) -> Tc) -> (Ta; Tb) -> Tc =
    """
    -- uncurry a Python-style multi-place function into a function of a tuple
    """
    args -> func(*args)



## Basic type classes:

#### Eq:
class Eq(T.Protocol):
    def __eq__(self, other: object) -> bool = bot

#### Ord:
class Ord(Eq, T.Protocol, T.Generic[Tcontra]):
    def __lt__(self: Tcontra, other: Tcontra) -> bool = bot
    def __gt__(self: Tcontra, other: Tcontra) -> bool = bot
    def __le__(self: Tcontra, other: Tcontra) -> bool = bot
    def __ge__(self: Tcontra, other: Tcontra) -> bool = bot


TOrd = T.TypeVar("TOrd", bound=Ord)

case def compare:
    type(x: Ord, y: Ord) -> Ordering
    case(x, y if x == y) = eq
    case(x, y if x < y) = lt
    case(x, y if x > y) = gt

\max: (TOrd, TOrd) -> TOrd  # type: ignore
\max = _max

\min: (TOrd, TOrd) -> TOrd  # type: ignore
\min = _min

#### Enum:
type Enum = Ord &: (+) &: (-)
TEnum = T.TypeVar("TEnum", bound=Enum)

succ: TEnum -> TEnum
succ = (1+.)

pred: TEnum -> TEnum
pred = (.-1)

toEnum = NotImplemented

fromEnum: Enum -> int
fromEnum = _int

def enumFrom(first: TEnum) -> TEnum$[] =
    iterate(succ, first)

def enumFromThen(first: TEnum, second: TEnum) -> TEnum$[] =
    step = fromEnum(second) - fromEnum(first)
    iterate((.+step), first) if step >= 0 else ()  # type: ignore

def enumFromTo(first: TEnum, last: TEnum) -> TEnum$[] =
    dist = fromEnum(last) - fromEnum(first)
    iterate(succ, first)$[:dist+1] if dist >= 0 else ()  # type: ignore

def enumFromThenTo(first: TEnum, second: TEnum, last: TEnum) -> TEnum$[] =
    step = fromEnum(second) - fromEnum(first)
    dist = fromEnum(last) - fromEnum(first)
    steps = dist/step if step != 0 else 0
    if steps < 0:
        return ()
    counter = iterate((.+step), first)
    counter$[:int(steps)+1] if steps != 0 else counter


#### Bounded:
class _HasBounds(T.Protocol):
    def __maxBound__(self) -> T.Any = bot
    def __minBound__(self) -> T.Any = bot

type Bounded = bool | _HasBounds | T.Iterable[Bounded]
TBounded = T.TypeVar("TBounded", bound=Bounded)

def minBound(b: TBounded) -> TBounded =
    """
    -- minBound is overridden by the __minBound__ method
    -- the default implementation recursively calls fmap (__fmap__) with minBound
    """
    # Check if bool
    if b `isinstance` bool:
        return False  # type: ignore

    # Check if overridden
    if b `hasattr` "__minBound__":
        return b.__minBound__()  # type: ignore

    # Default implementation
    fmap(minBound, b)  # type: ignore

def maxBound(b: TBounded) -> TBounded =
    """
    -- maxBound is overridden by the __maxBound__ method
    -- the default implementation recursively calls fmap (__fmap__) with maxBound
    """
    # Check if bool
    if b `isinstance` bool:
        return True  # type: ignore

    # Check if overridden
    if b `hasattr` "__maxBound__":
        return b.__maxBound__()  # type: ignore

    # Default implementation
    fmap(maxBound, b)  # type: ignore



## Numbers:

### Numeric types:

#### Int:
Int = int

#### Integer:
Integer = int

#### Float:
Float = float

#### Double:
Double = float

#### Rational:
Rational = _fractions.Fraction

def over(x, y) =
    """
    import Data.Ratio
    over :: Integer -> Integer -> Rational
    over = (%)
    """
    Rational x y
(%%) = over

#### Word:
Word = Int


### Numeric type classes:

#### Num:
type Num = int | float | Rational
TNum = T.TypeVar("TNum", bound=Num)

negate: TNum -> TNum
negate = (-)

\abs: TNum -> TNum
\abs = _abs

case def signum:
    type(x: Num) -> int
    case(0) = 0
    case(x if x > 0) = 1
    case(x if x < 0) = -1

def fromInteger(x: Integer) -> Num = x

#### Real:
Real = Num

case def toRational:
    type(real: Real) -> Rational
    case(real `isinstance` float) =
        Rational.from_float(real)
    case(real) =
        Rational(real)

#### Integral:
Integral = int

def quot(x: int, y: int) -> int =
    divxy = x // y
    divxy + (1 if divxy < 0 and x % y != 0 else 0)

def rem(x: int, y: int) -> int =
    modxy = x % y
    modxy - (y if modxy != 0 and x // y < 0 else 0)

div: (int, int) -> int
div = (//)

mod: (int, int) -> int
mod = (%)

def quotRem(x: int, y: int) -> (int; int) =
    divxy, modxy = divmod(x, y)
    adj = 1 if divxy < 0 and modxy != 0 else 0
    divxy + adj, modxy - y*adj

divMod = divmod

toInteger: Integral -> Integer
toInteger = _int

#### Fractional:
Fractional = Rational

recip: Fractional -> Fractional
recip = (1/.)

def fromRational(x: Rational) -> Fractional = x

#### Floating:
Floating = float

from math import (
    pi,
    exp,
    log,
    sqrt,
    sin,
    cos,
    tan,
    asin,
    acos,
    atan,
    sinh,
    cosh,
    tanh,
    asinh,
    acosh,
    atanh,
)  # NOQA

def logBase(base: float, x: float) -> float =
    log(x, base)

#### RealFrac:
RealFrac = Rational

def properFraction(x: RealFrac) -> (int; RealFrac) =
    floor_x = floor(x)
    floor_x, x - floor_x

truncate: RealFrac -> int
truncate = _int

\round: RealFrac -> int
\round = _round

ceiling: RealFrac -> int
ceiling = _ceil

floor: RealFrac -> int
floor = _floor

#### RealFloat:
RealFloat = float

def floatRadix(x: float) -> int = 2

def floatDigits(x: float) -> int = 53

def floatRange(x: float) -> (int; int) = (-1021, 1024)

decodeFloat = NotImplemented

encodeFloat = NotImplemented

exponent = NotImplemented

significand = NotImplemented

def scaleFloat(power: int, x: float) -> float =
    x * 2**power

from math import (
    isnan as isNaN,
    isinf as isInfinite,
    atan2,
)  # NOQA

isDenormalized = NotImplemented

def isNegativeZero(x: float) -> bool =
    x == 0 and str(x).startswith("-")

def isIEEE(x: float) -> bool = True


### Numeric functions:
def subtract(x, y) =
    y - x

def even(x: int) -> bool =
    x % 2 == 0

def odd(x: int) -> bool =
    x % 2 == 1

gcd: (int, int) -> int
gcd = abs.._gcd

case def lcm:
    type(x: int, y: int) -> int
    case(_, 0) = 0
    case(0, _) = 0
    case(x, y) =
        abs(y) * (abs(x) // gcd(x, y))

fromIntegral: Integral -> Num
fromIntegral = fromInteger

realToFrac: Real -> Fractional
realToFrac = toRational



## Monoids:
Monoid = T.Iterable
TMonoid = T.TypeVar("TMonoid", bound=Monoid)

data Mempty():
    """
    -- mempty is overridden by the __mempty__ method
    """
    @staticmethod
    def mempty_as(M: TMonoid) -> TMonoid =
        if M `hasattr` "__mempty__":
            return M.__mempty__()  # type: ignore
        makedata(type(M))

mempty: T.Any = Mempty()

def mappend(x: TMonoid, y: TMonoid) -> TMonoid =
    """
    -- mappend is overridden by the __mappend__ method
    -- you may also want to define a __mempty__ method
    -- the default implementation identifies non-identities using __bool__
    """
    # Resolve memptys
    x = x `asTypeOf` y
    y = y `asTypeOf` x

    # Check if overridden
    if x `hasattr` "__mappend__":
        return x.__mappend__(y)  # type: ignore

    # Default implementation
    if not x:
        return y
    if not y:
        return x
    if x `isinstance` tuple and y `isinstance` tuple:
        return zipWith(mappend, x, y) |*> makedata$(type(x))
    (::)(x, y) |*> makedata$(type(x))

def mconcat(ms: TMonoid[]) -> TMonoid =
    foldr(mappend, mempty, ms)  # type: ignore



## Monads and functors:

#### Functor:
class _HasFMap(T.Protocol, T.Generic[Tco]):
    def __fmap__[B](self: Functor[Tco], func: Tco -> B) -> Functor[B] = bot

type Functor[A] = Applicative[A] | _HasFMap[A]
TFunctor = T.TypeVar("TFunctor", bound=Functor)

def \fmap(f: Ta -> Tb, xs: Functor[Ta]) -> Functor[Tb]:  # type: ignore
    """
    -- fmap is overridden by the __fmap__ method
    """
    try:
        # Default implementation
        return _fmap(f, xs)

    except TypeError:
        # Function instance
        if callable(xs):
            return f .. xs  # type: ignore

        raise

def fmapConst(x: Ta, xs: Functor) -> Functor[Ta] =
    """
    fmapConst :: Functor f => (a -> b) -> f a -> f b
    fmapConst = (<$)
    """
    fmap(_ -> x, xs)
(<$) = fmapConst

#### Applicative:
class _DefinesApp(T.Protocol, T.Generic[Tco]):
    def __fmap__[B](self: Functor[Tco], func: Tco -> B) -> Functor[B] = bot
    def __pure__(self: Functor[Tco]) -> Tco = bot

type Applicative[A] = Monad[A] | T.Iterable[A] | _DefinesApp[A]
TApp = T.TypeVar("TApp", bound=Applicative)

if TYPE_CHECKING:
    def pure(x: Ta) -> T.Any:
        ...
else:
    data pure(val):
        """
        return_ = return
        -- pure/return is overridden by the __pure__ method
        """

        def __join__(self) -> T.Any = self.val

        def __call__(self, arg: T.Any) -> T.Any =
            """Implicitly casts pure to the Applicative function instance."""
            self.val

        def pure_as(self, M: TApp) -> TApp:
            # Check if overridden
            if M `hasattr` "__pure__":
                return M.__pure__(self.val)  # type: ignore

            try:
                # Default implementation
                return makedata(type(M), self.val)

            except TypeError:
                # Check for functions
                if callable(M):
                    return const(self.val)  # type: ignore

                # Fallback
                raise

def ap(fs: Applicative[Ta -> Tb], xs: Applicative[Ta]) -> Applicative[Tb] =
    """
    ap :: Applicative f => f (a -> b) -> f a -> f b
    ap = (<*>)
    -- ap is overridden by the __ap__ method
    -- you may also want to define a __pure__ method
    -- the default implementation uses join (__join__) and fmap (__fmap__)
    """
    # Resolve pures
    fs = fs `asTypeOf` xs  # type: ignore
    xs = xs `asTypeOf` fs  # type: ignore

    # Check if overridden
    if fs `hasattr` "__ap__":
        return fs.__ap__(xs)  # type: ignore

    # Default implementation
    fs `bind` f -> fmap(f, xs)  # type: ignore
(<*>) = ap

def seqAr(f1: Applicative, f2: TApp) -> TApp =
    """
    seqAr :: Applicative f => f a -> f b -> f b
    seqAr = (*>)
    """
    fmap(x1 -> x2 -> x2, f1) `ap` f2  # type: ignore
(*>) = seqAr

def seqAl(f1: TApp, f2: Applicative) -> TApp =
    """
    seqAl :: Applicative f => f a -> f b -> f a
    seqAl = (<*)
    """
    fmap(x1 -> x2 -> x1, f1) `ap` f2  # type: ignore
(<*) = seqAl

def liftA2(func: (Ta, Tb) -> Tc) -> (Applicative[Ta], Applicative[Tb]) -> Applicative[Tc] =
    """
    import Control.Applicative
    liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
    """
    (f1, f2) -> fmap(func$, f1) `ap` f2  # type: ignore

#### Monad:
class _DefinesMonad(T.Protocol, T.Generic[Tco]):
    def __fmap__[B](self: Functor[Tco], func: Tco -> B) -> Functor[B] = bot
    def __pure__(self: Functor[Tco]) -> Tco = bot
    def __join__(self: Functor) -> Functor[Tco] = bot

class _DefaultMonad(T.Protocol, T.Generic[Tco]):
    def __iter__(self) -> T.Iterator[Tco] = bot
    def __bool__(self) -> bool = bot

type Monad[A] = _DefaultMonad[A] | ((...) -> A) | _DefinesMonad[A]
TMonad = T.TypeVar("TMonad", bound=Monad)

def bind(m: Monad[Ta], func: Ta -> TMonad) -> TMonad =
    """
    bind :: Monad m => m a -> (a -> m b) -> m b
    bind = (>>=)
    -- bind is overridden by overriding fmap (__fmap__) and join (__join__)
    """
    join(fmap(func, m))  # type: ignore
(>>>=) = bind

def seqM(m1: Monad, m2: TMonad) -> TMonad =
    """
    seqM :: Monad m => m a -> m b -> m b
    seqM = (>>)
    """
    m1 `bind` x -> m2  # type: ignore
(>>>) = seqM

return_ = pure

if TYPE_CHECKING:
    def fail(msg: str) -> T.Any:
        ...
else:
    data fail(msg: str):
        """
        -- fail is overridden by the __fail__ method
        """

        @staticmethod
        def __bool__() -> bool = False

        def __fmap__(self, func: Ta -> Tb) -> T.Any = self

        def fail_as(self, M: TMonad) -> TMonad =
            if M `hasattr` "__fail__":
                return M.__fail__(self.msg)  # type: ignore
            makedata(type(M))

# sequence_ and mapM_ defined in Foldable

def bindFrom(func: Ta -> TMonad, m: Monad[Ta]) -> TMonad =
    """
    bindFrom :: Monad m => (a -> m b) -> m a -> m b
    bindFrom = (=<<)
    """
    m `bind` func
(=<<<) = bindFrom

def join(ms: Monad[TMonad]) -> TMonad:
    """
    import Control.Monad
    join :: Monad m => m (m a) -> m a
    -- join is overridden by the __join__ method
    -- you may also want to define __pure__ and __fail__ methods (pure = return)
    -- the default implementation uses __bool__ and __iter__
    """
    # Resolve ms being pure or fail
    match () :: _ in ms:
        ms = reduce((ms, m) -> ms `asTypeOf` m, ms, ms)  # type: ignore

    # Resolve pures and fails inside of ms
    ms = ms |> fmap$(m -> m `asTypeOf` ms)  # type: ignore

    # Check if overridden
    if ms `hasattr` "__join__":
        return ms.__join__()  # type: ignore

    # Default implementation
    match ms:  # type: ignore

        # Iterable instance
        case () :: _:
            if not ms:
                return ms  # type: ignore
            vals = []  # type: ignore
            fallback = ms
            for m in ms:
                if m:
                    vals.extend(m)  # type: ignore
                else:
                    fallback = m  # type: ignore
            if not vals:
                return fallback  # type: ignore
            return makedata(type(ms), *vals)  # type: ignore

        # Function instance
        case _ if callable(ms):
            return r -> ms(r)(r)  # type: ignore

    else:
        raise TypeError("cannot join non-monad type " + str(type(ms)))

case def do:
    """
    The call
        do([m1, m2, ...], func)
    is equivalent to the sequence of binds
        m1 `bind` x1 ->
            m2 `bind` x2 ->
                ...
                    func(x1, x2, ...)
    which is meant to mimic the do notation
        x1 <- m1
        x2 <- m2
        ...
        func(x1, x2, ...)
    or do can also be used as a decorator such that
        @do$([m1, m2, ...])
        def func(x1, x2, ...) =
            ...
    also does the same thing.
    """
    type(
        monads: TMonad[],
        func: -> TMonad,
    ) -> TMonad
    case([], func) = func()
    case([m] + ms, func) =
        m `bind` x -> do(ms, func$(x))



## Folds and traversals:

#### Foldable:
Foldable = T.Sequence

def sequence_(ms: Foldable[Monad]) -> Monad =
    do(ms, (*xs) -> pure(()))

mapM_: (Ta -> Monad, Foldable[Ta]) -> Monad
mapM_ = sequence_..fmap

def foldMap(func: Ta -> TMonoid, xs: Foldable[Ta]) -> TMonoid =
    mconcat(_map(func, xs))  # type: ignore

def foldl(func: (Tb, Ta) -> Tb, init: Tb, xs: Foldable[Ta]) -> Tb =
    _reduce(func, xs, init)

def foldr(func: (Ta, Tb) -> Tb, init: Tb, xs: Foldable[Ta]) -> Tb =
    _reduce((x, y) -> func(y, x), reversed(xs), init)

foldl1: ((Ta, Ta) -> Ta, Foldable[Ta]) -> Ta
foldl1 = reduce

def foldr1(func: (Ta, Ta) -> Ta, xs: Foldable[Ta]) -> Ta =
    reduce((x, y) -> func(y, x), reversed(xs))

def null(xs: Foldable[Ta]) -> bool =
    len(xs) == 0

length: Foldable -> int
length = len

def elem(e: Ta, xs: Foldable[Ta]) -> bool =
    e in xs

maximum: Foldable[TOrd] -> TOrd
maximum = _max

minimum: Foldable[TOrd] -> TOrd
minimum = _min

\sum: Foldable[TNum] -> TNum
\sum = _sum

product: Foldable[TNum] -> TNum
product = reduce$(*)

#### Traversable:
Traversable = T.Iterable

def _snoc(xs: Ta$[], x: Ta) -> Ta$[] =
    (::)(xs, (x,))

def sequence(fs: Traversable[Monad[Ta]]) -> Monad[Traversable[Ta]] =
    reduce(liftA2(_snoc), fs, pure(())) |> fmap$(xs -> makedata(type(fs), *xs))

sequenceA: Traversable[Applicative[Ta]] -> Applicative[Traversable[Ta]]
sequenceA = sequence  # type: ignore

mapM: (Ta -> Monad[Tb], Traversable[Ta]) -> Monad[Traversable[Tb]]
mapM = sequence..fmap  # type: ignore

traverse: (Ta -> Applicative[Tb], Traversable[Ta]) -> Applicative[Traversable[Tb]]
traverse = mapM  # type: ignore



## Miscellaneous functions:
\id: Ta -> Ta = ident

def dot(f: Tb -> Tc, g: Ta -> Tb) -> Ta -> Tc =
    """
    dot :: (b -> c) -> (a -> b) -> a -> c
    dot = (.)
    """
    f..g  # type: ignore

case def apply:
    """
    apply :: (a -> b) -> a -> b
    apply = ($)
    -- apply will automatically curry functions as in Haskell function
    --  application (see also `of` for the more general version)
    """
    type(
        func: Ta -> Tb,
        arg: Ta,
    ) -> Tb
    type(
        func: (Ta, Tb) -> Tc,
        arg: Ta,
    ) -> Tb -> Tc
    type(
        func: (Ta, Tb, Tc) -> Td,
        arg: Ta,
    ) -> (Tb, Tc) -> Td
    type(
        func: -> Tb,
        arg: Ta,
    ) -> T.Any
    case(func, arg) =
        func `of` arg
($$) = apply

def until(cond: Ta -> bool, func: Ta -> Ta, x: Ta) -> Ta =
    if cond(x):
        return x
    until(cond, func, func(x))  # tail recursive

def asTypeOf(x: Ta, y: Ta) -> Ta:
    """
    -- use asTypeOf to resolve pure, fail, and mempty to the correct type
    -- set asTypeOf.RECURSION_LIMIT to control recursive resolution
    """
    if TYPE_CHECKING: return x

    if not y `isinstance` (pure, fail, Mempty):
        for i in count() |> takewhile$(-> _ < asTypeOf.RECURSION_LIMIT):
            if x `isinstance` pure:
                x = x.pure_as(y)
            elif x `isinstance` fail:
                x = x.fail_as(y)
            elif x `isinstance` Mempty:
                x = x.mempty_as(y)
            else:
                break
    return x

asTypeOf.RECURSION_LIMIT = 3  # type: ignore

def error(msg: str) -> None:
    raise Exception(msg)

def errorWithoutStackTrace(msg: str) -> None:
    raise Exception(msg) from None

undefined: T.Any = None

def seq(x: Ta, y: Tb) -> Tb =
    """
    -- seq doesn't actually do anything here, since Python isn't lazy
    """
    y

def cbv(func: Ta -> Tb, arg: Ta) -> Tb =
    """
    cbv :: (a -> b) -> a -> b
    cbv = ($!)
    -- cbv is just an apply that doesn't curry the provided function
    """
    arg `seq` func(arg)




# List operations:
def cons(x: Ta, xs: Ta$[]) -> Ta$[] =
    """
    cons :: a -> [a] -> [a]
    cons = (:)
    """
    (::)([x], xs)

\map: (Ta -> Tb, Ta$[]) -> Tb$[]  # type: ignore
\map = _map  # type: ignore

def chain(xs: Ta$[], ys: Ta$[]) -> Ta$[] =
    """
    chain :: [a] -> [a] -> [a]
    chain = (++)
    """
    (::)(xs, ys)
(++) = chain

\filter: (Ta -> bool, Ta$[]) -> Ta$[]  # type: ignore
\filter = _filter  # type: ignore

head: Ta$[] -> Ta
head = .$[0]

last: Ta$[] -> Ta
last = .$[-1]

tail: Ta$[] -> Ta$[]
tail = .$[1:]  # type: ignore

init: Ta$[] -> Ta$[]
init = .$[:-1]  # type: ignore

def at(xs: Ta$[], i: int) -> Ta =
    """
    at :: [a] -> Int -> a
    at = (!!)
    """
    xs$[i]
(!!) = at

reverse: Ta[] -> Ta[]
reverse = _reversed



## Special folds:
and_: Foldable[bool] -> bool
and_ = _all

or_: Foldable[bool] -> bool
or_ = _any

\any: ((Ta -> bool), Foldable[Ta]) -> bool
\any = or_..map

\all: ((Ta -> bool), Foldable[Ta]) -> bool
\all = and_..map

def concat(xs: Foldable[Ta$[]]) -> Ta$[] =
    _reduce((::), xs, ())

concatMap: (Ta -> Tb$[], Foldable[Ta]) -> Tb$[]
concatMap = concat..map



## Building lists:

### Scans:
def scanl(func: (Ta, Tb) -> Ta, init: Ta, xs: Tb$[]) -> Ta$[] =
    scan(func, xs, init)

scanl1: ((Ta, Ta) -> Ta, Ta$[]) -> Ta$[]
scanl1 = scan

def scanr(func: (Ta, Tb) -> Ta, init: Ta, xs: Tb[]) -> Ta$[] =
    scan(func, reversed(xs), init)$[::-1]

def scanr1(func: (Ta, Ta) -> Ta, xs: Ta[]) -> Ta$[] =
    scan(func, reversed(xs))$[::-1]

### Infinite lists:
@recursive_generator
def iterate(func: Ta -> Ta, x: Ta) -> Ta$[] =
    [x] :: iterate(func, func(x))

@recursive_generator
def repeat(x: Ta) -> Ta$[] =
    [x] :: repeat(x)

def replicate(n: int, x: Ta) -> Ta$[] =
    repeat(x)$[:n]

if TYPE_CHECKING:
    def \cycle(xs: Ta[]) -> Ta$[]:  # type: ignore
        ...
else:
    @recursive_generator
    def \cycle(xs if len(xs) > 0) =
        _cycle(xs)



## Sublists:
def take(n: int, xs: Ta$[]) -> Ta$[] =
    xs$[:n]

def drop(n: int, xs: Ta$[]) -> Ta$[] =
    xs$[n:]

def splitAt(n: int, xs: Ta$[]) -> (Ta$[]; Ta$[]) =
    reit = reiterable(xs)
    reit$[:n], reit$[n:]

takeWhile: (Ta -> bool, Ta$[]) -> Ta$[]
takeWhile = takewhile

dropWhile: (Ta -> bool, Ta$[]) -> Ta$[]
dropWhile = dropwhile

case def span:
    type(cond: Ta -> bool, xs: Ta[]) -> (Ta[]; Ta[])

    case(_, []) = ([], [])
    case(cond, [x] + xs if cond(x)) =
        ys, zs = span(cond, xs)
        ([x] + ys, zs)
    case(cond, xs) =
        ([], xs)

def break_(cond: Ta -> bool, xs: Ta[]) -> Ta[] =
    """
    break_ = break
    """
    span((not)..cond, xs)  # type: ignore



## Searching lists:
def notElem(e: Ta, xs: Ta[]) -> bool =
    e not in xs

def lookup(key: Ta, assocs: (Ta; Tb)$[]) -> Maybe:
    try:
        return (
            assocs
            |> dropwhile$(pair -> pair[0] != key)
            |> .$[0]
            |> .[1]
            |> Just
        )
    except IndexError:
        return nothing



## Zipping and unzipping lists:
\zip: (Ta$[], Tb$[]) -> (Ta; Tb)$[]  # type: ignore
\zip = _zip  # type: ignore

zip3: (Ta$[], Tb$[], Tc$[]) -> (Ta; Tb; Tc)$[]
zip3 = _zip

def zipWith(func: (Ta, Tb) -> Tc, xs1: Ta$[], xs2: Tb$[]) -> Tc$[] =
    _map(func, xs1, xs2)

def zipWith3(func: (Ta, Tb, Tc) -> Td, xs1: Ta$[], xs2: Tb$[], xs3: Tc$[]) -> Td$[] =
    _map(func, xs1, xs2, xs3)

def unzip(xs: (Ta; Tb)$[]) -> (Ta[]; Tb[]) =
    _zip(*xs) |> _map$(list) |> tuple  # type: ignore

unzip3: (Ta; Tb; Tc)$[] -> (Ta[]; Tb[]; Tc[])
unzip3 = unzip  # type: ignore



## Functions on strings:
lines: str -> str[]
lines = .splitlines()

words: str -> str[]
words = .split()

def unlines(strs: str$[]) -> str =
    "".join(s + "\n" for s in strs)

unwords: str$[] -> str
unwords = " ".join




# Converting to and from String:

## Converting to String:
ShowS = T.Callable[[str], str]

Show = T.Any

showsPrec = NotImplemented

show: Ta -> str
show = repr

def shows(x: Show) -> ShowS =
    s -> repr(x) + s

def showList(xs: Show$[]) -> ShowS =
    s -> repr(list(xs)) + s

def showString(x: str) -> ShowS =
    s -> x + s

showChar: Char -> ShowS
showChar = showString

def showParen(parens: bool, showFunc: ShowS) -> ShowS =
    s -> (
        "(" + showFunc("") + ")" + s if parens
        else showFunc("") + s
    )



## Converting from String:
ReadS = NotImplemented

Read = T.Union[
    str,
    int,
    float,
    bool,
    None,
    tuple,
    list,
    dict,
]

readsPrec = NotImplemented

readList = NotImplemented

reads = NotImplemented

readParen = NotImplemented

def read(s: str) -> Read =
    _ast.literal_eval(s)

lex = NotImplemented




# Basic input and output:

#### IO:
data IO(io_func):
    @staticmethod
    def __pure__(x: Ta) -> IO =
        IO(() -> x)

    @staticmethod
    def __fail__(msg: str) -> IO =
        IO(def () -> raise IOError(msg))

    def __fmap__(self, func: Ta -> Tb) -> IO =
        IO(func..self.io_func)

    def __join__(self) -> IO =
        fmap(unIO, self)  # type: ignore

    @staticmethod
    def __mempty__() -> IO =
        IO(() -> mempty)

    def __mappend__(self, other: IO) -> IO =
        IO(() -> mappend(self.io_func(), other.io_func()))

_nullIO: IO = IO(() -> None)

def asIO(io: IO) -> IO =
    """
    asIO :: IO a -> IO a
    asIO = id
    -- asIO(x) is equivalent to x `asTypeOf` IO(...)
    """
    io `asTypeOf` _nullIO  # type: ignore

def unIO(io: IO) -> T.Any =
    """
    The unIO function is an impure function which performs the
    I/O contained in the given IO object and returns the result.
    In particular, the recommendation is to write
        @unIO
        @do$([io1, io2, ...])
        def main(r1, r2, ...) =
            ...
    which is equivalent to the Haskell code
        main = do
            r1 <- io1
            r2 <- io2
            ...
    """
    asIO(io).io_func()




## Simple I/O operations:

### Output functions:
def putStr(s: str) -> IO =
    IO(_print$(s, end=""))

putChar: Char -> IO
putChar = putStr

def putStrLn(s: str) -> IO =
    IO(_print$(s))

def \print(x: Ta) -> IO =  # type: ignore
    IO(_print$(show(x)))


### Input functions:
getChar: IO = IO(sys.stdin.read$(1))

getLine: IO = IO(input)

getContents: IO = IO(sys.stdin.read)

def interact(func: str -> str) -> IO =
    def do_interact():
        while True:
            input() |> func |> _print
    IO(do_interact)


### Files:
FilePath = str

def readFile(fpath: FilePath) -> IO =
    def do_readFile() -> str:
        with open(fpath, "r+") as f:
            return f.read()
    IO(do_readFile)

def writeFile(fpath: FilePath, text: str) -> IO =
    def do_writeFile() -> None:
        with open(fpath, "w+") as f:
            f.write(text)
    IO(do_writeFile)

def appendFile(fpath: FilePath, text: str) -> IO =
    def do_appendFile() -> None:
        with open(fpath, "a+") as f:
            f.write(text)
    IO(do_appendFile)

def readIO(s: str) -> IO =
    IO(read$(s))

def readLn() -> IO =
    getLine() `bind` readIO  # type: ignore



## Exception handling:
def ioError(err: IOError) -> IO =
    IO(def () -> raise err)

def userError(msg: str) -> IOError =
    IOError(msg)