Functional Programming for Beginners

Video of a talk given at Boston Area Scala Enthusiasts’ Jan 2011 meeting at Google Cambridge. Covers what FP actually means in unambiguous terms, and how to perform various programming tasks while staying pure.

Slides are here:

Code for the IO data structure mentioned but not shown at the end of the talk is given here:

  sealed trait IO[A] 
  case object ReadLn extends IO[String]
  case class WriteLn(s: String) extends IO[Unit]
  case class Const[A](a: A) extends IO[A]
  case class Compose[A, B](a: IO[A], f: A => IO[B]) extends IO[B]

  // An example program which reads a line and writes it out again
  def readThenWrite: IO[Unit] =
    Compose(ReadLn, WriteLn)

  // An implementation for IO programs which turns them into side-effects
  def run[A](program: IO[A]): A = program match {
    case ReadLn => readLine
    case WriteLn(s) => println(s)
    case Const(a) => a
    case Compose(a, f) => run(f(run(a)))

  // An implementation for IO programs which turns them into list transitions
  def run[A](program: IO[A], in: List[String], out: List[String]): (A, List[String], List[String]) =
    program match {
      case ReadLn => (in.head, in.tail, out)
      case WriteLn(x)  => ((), in, x :: out)
      case Const(a) => (a, in, out)
      case Compose(ioa, f) => {
        val (a, tmpi, tmpo) = run(ioa, in, out)
        run(f(a), tmpi, tmpo)
About these ads

15 thoughts on “Functional Programming for Beginners

  1. Runar, I would be very grateful if you could post the content of the board at 42:00. The recap of foldLeft and foldRight you did is rather insightful. Or maybe it is just thanks to the Scala syntax :-) Anyway, please may I have it?: at least the first two lines are unreadable throughout the whole video.
    Have a nice day,
    Marco Faustinelli

  2. Thanks for the IO code. I’m starting to work through Paul Hudak’s The Haskell School of Expression and porting the code to Scala. I’ll use this IO code as a starting point translating his code that uses Haskell’s IO monad.

    • Seth!

      I guess you could just keep expanding this, adding combinators that you need. When hudak starts drawing on the screen, there’s no reason you couldn’t have IO combinators for manipulating Java 2D contexts.

  3. Hey Runar,

    I’m having some trouble compiling the above. Specifically:

    def run[A, B](program: IO[A]): List[B] => (A, List[B]) = program match {
    case ReadLn => xs => (xs.head, xs.tail)
    case WriteLn(x) => xs => ((), x :: xs)
    case Const(a) => xs => (a, xs)
    case Compose(a, f) => xs => run(f(run(a)(xs)._1))

    Which gives the following errors:

    :14: error: type mismatch;
    found : B
    required: A
    case ReadLn => xs => (xs.head, xs.tail)
    :15: error: type mismatch;
    found : x$1.type (with underlying type String)
    required: B
    case WriteLn(x) => xs => ((), x :: xs)
    :17: error: polymorphic expression cannot be instantiated to expected type;
    found : [(some other)B(in method run)](List[(some other)B(in method run)]) => (A, List[(some other)B(in method run)])
    required: (A, List[B(in method run)])
    case Compose(a, f) => xs => run(f(run(a)(xs)._1))

    The errors seem justified. Any ideas?

    • SSanj,

      There was an additional type argument messing things up. The code from the talk given this past weekend is correct. I’ve replaced the code here with that code.

  4. Hi Rúnar,

    Thanks for the great talk. I didn’t pay much attention to functional languages while I was at university which was a real shame. Over the last few months, I’ve started to get really interested by them and this talk has helped to to really get a grasp on things which I was struggling with (like everything being immutable).

    I’m going to try to use some of these concepts more-and-more in my every-day life of being a JavaScript developer, after all, it IS a functional language ;)

    Thanks again!

  5. Hello Rúnar,

    I was wondering what is the mechanism that allows WriteLn (in your IO example) to be used as the second argument in Compose, whose type is (after inference) String => IO[Unit].

    Or to base my question on an even simpler example, given:
    case class C (s: String)
    def test (f: String => Any) { prinltn (“ok”) }
    Why does test(C) type-checks, compiles, and prints ok when run?


      • Ahh, I get it now, generated companion object actually extends (in my example) Function1[String,C].
        Or to put it differently in not so many words: C.type <: C) :-)

        A neat trick, one of scala’s many.
        And if I may say so – a great talk and post, one of yours many.


      • Oh, forget it, I was trying to type a generalized type constraint, but it wouldn’t come out right.
        I’ll stop spamming now…


  6. Type Level Programming for Beginners sounds very good! The talk is really great. I tried to read the slides and… Ops! I see the slides in html format!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s