Skip to content

Instantly share code, notes, and snippets.

@chirlo
Created August 6, 2014 15:03
Show Gist options
  • Save chirlo/dbf3d6b18e8afce5da64 to your computer and use it in GitHub Desktop.
Save chirlo/dbf3d6b18e8afce5da64 to your computer and use it in GitHub Desktop.
object SUG_Monads {
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
def distribute[A, B](fab: F[(A, B)]): (F[A], F[B]) =
(map(fab)(_._1), map(fab)(_._2))
def codistribute[A, B](e: Either[F[A], F[B]]): F[Either[A, B]] =
e fold (map(_)(Left(_)), map(_)(Right(_)))
}
trait Monad[F[_]] extends Functor[F] {
def unit[A](a: => A): F[A]
def flatMap[A, B](ma: F[A])(f: A => F[B]): F[B]
def map[A, B](ma: F[A])(f: A => B): F[B] = flatMap(ma)(a => unit(f(a)))
def map2[A, B, C](ma: F[A], mb: F[B])(f: (A, B) => C): F[C] = flatMap(ma)(a => map(mb)(b => f(a, b)))
//EX:3
def traverse[A, B](la: List[A])(f: A => F[B]): F[List[B]] =
la.foldRight(unit(List[B]())) { (a, lb) =>
map2(f(a), lb)(_ :: _)
}
def sequence[A](lma: List[F[A]]): F[List[A]] = traverse(lma)(identity)
//EX:4-5
//all combinations of length n with elements from ma
def replicateM[A](n: Int, ma: F[A]): F[List[A]] =
sequence(List.fill(n)(ma))
//EX: 6
def filterM[A](ms: List[A])(f: A => F[Boolean]): F[List[A]] =
ms.foldRight(unit(List[A]())) { (a, fla) =>
map2(f(a), fla)((b, la) => if (b) a :: la else la)
}
// filterM and and traverse are almos identical, let's abstract
def traverseL[A, B, C](la: List[A])(f: A => F[B])(g: (A, B) => List[C]): F[List[C]] =
la.foldRight(unit(Nil: List[C]))((a, l) => map2(f(a), l)((x, y) => g(a, x) ++ y))
def traverse2[A, B](la: List[A])(f: A => F[B]): F[List[B]] =
traverseL(la)(f)((a, b) => List(b))
def filter2[A](ms: List[A])(f: A => F[Boolean]): F[List[A]] =
traverseL(ms)(f)((a, b) => if (b) List(a) else List())
//try to abstract over Traversable, but have to give the empty. It it was a Monoid....hmmmm
def traverseC[A, B, C, L[x] <: Traversable[x]](la: L[A])(f: A => F[B])(empty: L[C])(g: (A, B) => L[C]): F[L[C]] =
la.foldRight(unit(empty))((a, l) => map2(f(a), l)((x, y) => {
(g(a, x) ++ y).asInstanceOf[L[C]]
}))
//traverse Vector...
def traverseV[A, B, C](la: Vector[A])(f: A => F[B])(g: (A, B) => Vector[C]): F[Vector[C]] =
traverseC(la)(f)(Vector[C]())(g)
def traverseVector[A, B](la: Vector[A])(f: A => F[B]): F[Vector[B]] =
traverseC(la)(f)(Vector[B]())((a, b) => Vector(b))
def filterMVector[A](la: Vector[A])(f: A => F[Boolean]): F[Vector[A]] =
traverseC(la)(f)(Vector[A]())((a, b) => if (b) Vector(a) else Vector())
//these 2 look very similar, if L was a Monoid (zero, mappend) AND a Monad(pure) ...
//EX:7
def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] = a => flatMap(f(a))(g)
//EX:12
def join[A](mma: F[F[A]]): F[A] =
flatMap(mma)(identity)
//EX:13
def composeJ[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] = a =>
join(map(f(a))(g))
def flatMapJ[A, B](ma: F[A])(f: A => F[B]): F[B] =
join(map(ma)(f))
}
//EX:1-a
val optionMonad = new Monad[Option] {
def unit[A](a: => A): Option[A] = Some(a)
def flatMap[A, B](ma: Option[A])(f: A => Option[B]): Option[B] = ma.fold(None: Option[B])(f)
}
//EX:1-b
val streamMonad = new Monad[Stream] {
def unit[A](a: => A): Stream[A] = Stream(a)
def flatMap[A, B](ma: Stream[A])(f: A => Stream[B]): Stream[B] = ma.flatMap(f)
}
//EX:1-c
val listMonad = new Monad[List] {
def unit[A](a: => A): List[A] = List(a)
def flatMap[A, B](ma: List[A])(f: A => List[B]): List[B] = ma.flatMap(f)
}
import com.algae.fpinscala.State
//EX:2
def stateMonad[S] = {
type St[x] = State[S, x]
new Monad[St] {
def unit[A](a: => A) = State unit (a)
def flatMap[A, B](ma: St[A])(f: A => St[B]) = ma flatMap (f)
}
}
//EX:17
case class Id[A](value: A)
val monid = new Monad[Id] {
def unit[A](a: => A) = Id(a)
def flatMap[A, B](ma: Id[A])(f: A => Id[B]): Id[B] = f(ma.value)
}
//EX:18 : similar to state, but apply the same parameter to all invocations
case class Reader[R, A](run: R => A)
def readerMonad[R] = new Monad[({ type Rex[x] = Reader[R, x] })#Rex] {
def unit[A](a: => A): Reader[R, A] = Reader(_ => a)
def flatMap[A, B](st: Reader[R, A])(f: A => Reader[R, B]): Reader[R, B] = Reader { r =>
val a = st.run(r)
f(a).run(r)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment