sealed trait List[+A]
case class Cons[A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]
object ListT {
import Functor._
import Monad._
def apply[A, M[_]: Monad](x: M[List[A]]) =
new MonadOps[A, ({ type λ[ɑ] = M[List[ɑ]] })#λ](x)
implicit def monad[M[_]: Monad]: Monad[({ type λ[ɑ] = M[List[ɑ]] })#λ] =
new Monad[({ type λ[ɑ] = M[List[ɑ]] })#λ] {
private lazy val m: Monad[M] = implicitly[Monad[M]]
def pure[A](a: A): M[List[A]] =
if (a == null) m.pure(Nil) else m.pure(Cons(a, Nil))
def join[A](xss: List[List[A]]): List[A] =
match {
xss case Nil => Nil
case Cons(h, t) => List.semigroup.sconcat(h, join(t))
}
override def map[A, B](ma: M[List[A]])(f: A => B): M[List[B]] =
.map(ma) { as =>
mdef map(xs: List[A]): List[B] =
match {
xs case Cons(h, t) => Cons(f(h), map(t))
case Nil => Nil
}
map(as)
}
def flatMap[A, B](ma: M[List[A]])(f: A => M[List[B]]): M[List[B]] =
.flatMap(ma) { as =>
mList.traversable.sequence(as map f) map { join (_) }
}
}
}
object List {
import Functor._
import Semigroup._
def apply[A](h: A, t: List[A]): List[A] =
Cons(h, t)
implicit def semigroup[A]: Semigroup[List[A]] =
new Semigroup[List[A]] {
def sconcat(a1: List[A], a2: List[A]): List[A] =
match {
a1 case Cons(h, t) => Cons(h, t <> a2)
case Nil => a2
}
}
implicit val monad: Monad[List] = ListT.monad[ID]
implicit val foldable: Foldable[List] =
new Foldable[List] {
override def foldr[A, B](f: (A, B) => B)(z: B)(fa: List[A]): B =
match {
fa case Cons(h, t) => foldr(f)(f(h, z))(t)
case Nil => z
}
}
implicit val traversable: Traversable[List] =
new Traversable[List] {
override def sequence[A, F[_]: Applicative](x: List[F[A]])
(implicit ft: Functor[List]): F[List[A]] =
.foldr(
foldable(a: F[A], b: F[List[A]]) =>
[Applicative[F]].ap(
implicitly{
b map => {
as : A =>
a.sconcat(as, Cons(a, Nil))
semigroup}
}
)(a)
)(implicitly[Applicative[F]].pure(Nil))(x)
}
}
import Applicative._
import Foldable._
import Monad._
import Traversable._
{
println for {
<- List(6, List(3, Nil))
x <- List(7, List(3, Nil))
y = x * y
z } yield z
} // Cons(42,Cons(18,Cons(21,Cons(9,Nil))))
{
println foldr((x: Int, y: Int) => x * y)(7)(List(2, List(3, Nil)))
} // 42
{
println sequence(List(List(6, Nil), List(List(7, Nil), Nil)))
} // Cons(Cons(6,Cons(7,Nil)),Nil)
case class Box[A](a: A)
implicit def boxMonad[M[_]: Monad]: Monad[Box] =
new Monad[Box] {
def pure[A](a: A): Box[A] =
Box(a)
def flatMap[A, B](ma: Box[A])(f: A => Box[B]): Box[B] =
f(ma.a)
}
{
println for {
<- ListT(Box(List(6, Nil)))
x <- ListT(Box(List(7, Nil)))
y } yield x * y
} // Box(Cons(42,Nil))
This file is literate Scala, and can be run using Codedown:
$ curl \
https://earldouglas.com/posts/type-classes/applicative.md \
https://earldouglas.com/posts/type-classes/foldable.md \
https://earldouglas.com/posts/type-classes/functor.md \
https://earldouglas.com/posts/type-classes/id.md \
https://earldouglas.com/posts/type-classes/monad.md \
https://earldouglas.com/posts/type-classes/monoid.md \
https://earldouglas.com/posts/type-classes/semigroup.md \
https://earldouglas.com/posts/type-classes/traversable.md \
https://earldouglas.com/posts/type-classes/list.md |
codedown scala | xargs -0 scala -nc -e
Cons(42,Cons(18,Cons(21,Cons(9,Nil))))
42
Cons(Cons(6,Cons(7,Nil)),Nil)
Box(Cons(42,Nil))