Skip to content

Instantly share code, notes, and snippets.

@huitseeker
Created January 1, 2012 22:44
Show Gist options
  • Save huitseeker/1548553 to your computer and use it in GitHub Desktop.
Save huitseeker/1548553 to your computer and use it in GitHub Desktop.
Every single freshman CS question in ˜80 lines of Scala
import Stream._
object Curryfication {
def curry [A,B,C](f:Pair[A,B] ⇒ C) = (x:A) ⇒ (y:B) ⇒ f (x,y)
def uncurry [A,B,C](f: A ⇒ B ⇒ C) = (x:Pair[A,B]) ⇒ f (x._1) (x._2)
}
trait Curried[S,R] {
type Fun
def curry : (S ⇒ R) ⇒ Fun
}
class CurriedDefault {
implicit def ZeroC[S,R] = new Curried[S,R]{
type Fun = S ⇒ R
def curry = f ⇒ f
}
}
object Curried extends CurriedDefault{
def apply[S,R] (f:S ⇒ R) (implicit c:Curried[S,R]) : c.Fun =
c.curry(f)
implicit def SuccC[T,S,R] (implicit c:Curried[S,R]) =
new Curried[Pair[T,S],R] {
type Fun = T ⇒ c.Fun
def curry = f ⇒ x ⇒ c.curry(y ⇒ f(x,y))
}
}
trait Uncurried [S] {
type Tuple
type Return
def uncurry : S ⇒ Tuple ⇒ Return
}
class UncurriedDefault {
implicit def ZeroUC[S] = new Uncurried[S ⇒ S]{
type Tuple = S
type Return = S
def uncurry = f ⇒ f
}
}
object Uncurried extends UncurriedDefault{
def apply[S] (f:S) (implicit uc:Uncurried[S]) : uc.Tuple ⇒ uc.Return =
uc.uncurry(f)
implicit def SuccUC[S,R] (implicit uc:Uncurried[R]) =
new Uncurried[S ⇒ R]{
type Tuple = Pair[S,uc.Tuple]
type Return = uc.Return
def uncurry = f ⇒ x ⇒ uc.uncurry(f (x._1)) (x._2)
}
}
trait RecStream [S,Base] {
def prod : (S ⇒ Base) ⇒ S ⇒ Pair[Base, S]
def rstream : (S ⇒ Base) ⇒ S ⇒ Stream[Base]
}
class RecStreamDefault {
implicit def ZeroRS[S] = new RecStream[S,S] {
def prod = xs ⇒ ss ⇒ (ss, xs (ss))
def rstream = xs ⇒ ss ⇒ ss #:: rstream (xs) (xs(ss))
}
}
object RecStream extends RecStreamDefault {
def apply[S,B](f:S ⇒ B) (implicit rs:RecStream[S,B]): S ⇒ Stream[B] =
rs.rstream(f)
implicit def SuccRS[R,B] (implicit rs:RecStream[R,B]) =
new RecStream[Pair[B,R],B] {
def prod = f ⇒ a ⇒ (a._1, rs.prod (y ⇒ f (a._1,y)) (a._2))
def rstream = f ⇒ a ⇒
a._1 #:: rstream (f) (rs.prod (y ⇒ f (a._1,y)) (a._2))
}
}
object Test{
def increaser : Int ⇒ Stream[Int] =
RecStream((x:Int) ⇒ x + 1)
def fibonacci : Pair[Int,Int] ⇒ Stream [Int] =
RecStream(x ⇒ x._1 + x._2)
def sumthree (x:Int)(y:Int)(z:Int) = x+y+z
// def sumthreestream = RecStream(sumthree)
def uncst = Uncurried(sumthree _)
def sumthreestream = RecStream(uncst)
def curriedsumthreestream = Curried(sumthreestream)
def main(args:Array[String]) = {
fibonacci(0,1).take(10).print
print ("\n")
increaser(0).take(10).print
print ("\n")
increaser(1).take(10).print
print ("\n")
sumthreestream(0,(0,1)).take(10).print
print("\n")
curriedsumthreestream(0)(0)(1).take(10).print
print("\n")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment