pub hkt Functor[Self<T>] {
    fn <U> map(f: fn (t: &T) -> U) -> Self<U> // &self implied
}

pub hkt Applicative[Self<T>] : Functor[Self<T>] {
    static fn lift(t: T) -> Self<T> // static: no implicit self parameter
    fn <U, V> apply(us: &Self<U>) -> Self<V> where T : fn (u: &U) -> V
}

pub hkt Monad[Self<T>] : Applicative[Self<T>] {
    fn <U> flatMap(f: fn (t: &T) -> Self<U>) -> Self<U>
}

// Here, T is a separate type parameter from the container's inner type
// The container's inner type is ..., which can be anything, of any number of parameters
pub hkt Into[Self<...>, T] {
    cons fn into() -> T // consumes self
}

pub hkt Zero[Self<T>] {
    static fn zero() -> Self<T>
}

pub int Iterable<T> : Into[Self<T>, Iterator<T>] {
    /**
     * Iterator for references to contained item(s).
     */
    ref fn iter() -> Iterator<&T> // ref indicates return value cannot outlive self

    def cons fn intoIter() = Into[Self<T>, Iterator<T>].into()
}

pub type Iterator<T> = () -> Option<T>

pub int Exception {
    message: Option<String>
}

pub enum Option<T> : Monad[Self<T>] {
    Some(T),
    None;

    class EmptyOptionException(message: Option<String> = Empty) : Exception

    // cons implies that self is consumed (like Rust `self: Self`)
    cons fn unwrap() -> T = self is Some(t) ? t : throw EmptyOptionException()

    cons fn expect(message: String) -> T {
        if let Some(t) = self {
            t
        } else {
            throw EmptyOptionException(message)
        }
    }

    cons fn unwrapOr(self, other: T) -> T = self is Some(t) ? t : other

    cons fn unwrapOrElse(self, f: fn () -> T) = self is Some(t) ? t : f()

    impl Monad[Self<T>] {
        fn <U> map(f: fn (t: &T) -> U) -> Self<U> = self is Some(t) ? Some(f(t)) : Empty

        static fn lift(t: T) -> Self<T> = Some(t)

        fn <U, V> apply(us: &Self<U>) -> Self<V> where T : fn (u: U) -> V =
                self is Some(f) && us is Some(u) ? Some(f(u)) : Empty
                // note in above that `f` is `&fn (u: U) -> V`, but `f()` is sugar for `(*f)()`

        fn <U> flatMap(f: fn (t: &T) -> Self<U>) -> Self<U> = self is Some(t) ? f(t) : Empty
    }
}

pub class OptionT[M]<T>(fld o: M<Option<T>>) : Monad[Self[M]<T>] where M : Monad[Option<T>] {
    pub fn intoInner() -> M<Option<T>> = Into[Self[M]<T>, M<Option<T>>].into(self)

    pub fn <U> flatMapInner(f: fn (t: &T) -> M<Option<U>>) -> Self[M]<U> {
        OptionT(
            Monad[M].flatMap(o) { ts: &Option<T> ->
                ts is Some(t) ? f(t) : None
            }
        )
    }

    impl Monad[Self[M]<T>] {
        fn <U> map(f: fn (t: &T) -> U) -> Self[M]<U> {
            OptionT(
                    Monad[M].map(o) {
                        // implicit `it` parameter is `&Option<T>`
                        // When destructured, `t` is `&T`
                        it is Some(t) ? Some(f(t)) : None
                    }
            )
        }

        static fn lift(t: T) -> Self[M]<T> = OptionT(Monad[M].lift(Some(t)))

        fn <U, V> apply(us: &Self[M]<U>) -> Self[M]<V> where T : fn (u: &U) -> V {
            OptionT(
                    Monad[M].flatMap(o) { fOpt: &Option<fn (u: &U) -> V> ->
                        fOpt is Some(f)
                                ? Monad[M].map(us.o) { uOpt: &Option<U> ->
                                    uOpt is Some(u) ? Some(f(u)) : None
                                }
                                : Monad[M].lift(None)
                    }
            )
        }

        fn <U> flatMap(f: fn (t: &T) -> Self[M]<U>) -> Self[M]<U> {
            OptionT(
                Monad[M].flatMap(o) {
                    it is Some(t) ? f(t).o : Monad[M].lift(None)
                }
            )
        }
    }

    impl Into<Self[M]<T>, M<Option<T>>> {
        cons fn into() -> M<Option<T>> = o
    }
}

pub int List<T> : Iterable<T> + Zero[Self<T>] + Monad[Self<T>] {
    mut fn add(t: T) -> Void // mut implies &mut self

    // def = default
    // mut = &mut self
    // op = operator overload
    // << = left shift
    def mut op << (t: T) -> Void = add(t)

    ref fn get(i: Int) -> Option<&T> // ref implies that the returned object cannot outlive self
                                     // implied &self

    // Alternative syntax for get(i) definition:
    // fn get(i: Int) -> Option<&T> ref self

    def ref op [] (i: Int) -> Option<&T> = get(i)

    impl Monad[Self<T>] {
        fn <U> map(f: fn (t: &T) -> U) -> Self<U> {
            let out: List<U> = Zero[Self<U>].zero()
            for item in self { // item is &T
                out << f(item)
            }
            out
        }

        static fn lift(t: T) -> Self<T> = ArrayList(t)

        fn <U ,V> apply(us: &Self<U>) -> Self<V> where T : fn (u: &U) -> V {
            let out: List<V> = Zero[Self<V>].zero()
            for f in self { // f is &fn (u: &U) -> V
                for u in us { // u is &&u
                    out << f(*u) // syntax sugar for out.add((*f)(*u))
                }
            }
            out
        }

        fn <U> flatMap(f: fn (t: &T) -> Self<U>) -> Self<U> {
            let out: List<U> = Zero[Self<U>].zero()
            for t in self { // t is &T
                for u in Into[Self<U>, Iterator<U>].into(f(t)) { // u is U
                    out << u // out take ownership of u
                }
            }
            out
        }
    }
}

pub class LinkedList<T> : List<T> {

    // inner classes are static by default
    class Node<T>(data: T) {
        mut next: Option<Self<T>>
    }

    mut fld head: Option<Node<T>>

    impl mut fn add(t: T) -> Void {
        match head {
            None => {
                head = Some(Node(t))
            }
            Some => {
                let mut current: &Option<Node<T>> = &head
                while let Some(next) = &current?.next { // get a reference to current.next, or None if either are none
                    current = next
                }
                current.next = Some(Node(t))
            }
        }
    }

    impl ref fn get(index: Int) -> Option<&T> {
        let mut current: &Option<Node<T>> = &head
        let mut currentIndex = 0
        while currentIndex < index {
            if let Some(next) = &current?.next {
                currentIndex++
                current = next
            } else {
                break
            }
        }
        current is Some(node) ? Some(&node.data) : None
    }

    impl ref fn iter() -> Iterator<&T> {
        let mut current: &Option<Node<T>> = &head
        () -> {
            if let Some(node) = current {
                let data: &T = &node.data
                current = &node.next
                Some(data)
            } else {
                None
            }
        }
    }

    impl Into[Self<T>, Iterator<T>] {
        cons fn into() -> Iterator<T> {
            let mut current: Option<Node<T>> = take(head) // take replaces head with None
            return () -> {
                let result = current
                current = current?.next
                result is Some(node) ? Some(node.data) : None
            }
        }
    }

    impl Zero[Self<T>] {
        static fn zero() -> Self<T> = LinkedList()
    }
}

fn optionTListDemo() {
    let oddsOnly: List<Option<Int>> = [
        Some(1),
        None,
        Some(3),
        None,
        Some(5)
    ]

    let liftedOddsOnly: OptionT[]<> = OptionT(oddsOnly)

    let mapped = liftedOddsOnly
            .flatMapInner { [Some(it), Some(it + 1)] }
            .map { "Value: ${it.toString()}" }

    for o in mapped.intoInner() {
        if o is Some(s) {
            println s
        }
    }
}