# 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 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

// An implementation for IO programs which turns them into side-effects
def run[A](program: IO[A]): A = program match {
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 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)
}
}
```

## 15 thoughts on “Functional Programming for Beginners”

1. Marco Faustinelli says:

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

• Rúnar says:

Marco,

You want the code for foldLeft and foldRight? It’s a much better exercise to write them yourself.

• Marco Faustinelli says:

This is a polite “no”, I reckon… :-)

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.

• Rúnar says:

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 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
^
: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?

• Rúnar says:

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. Duduk says:

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?

Regards,
Duduk

• Rúnar says:

Because test(C) is another way of writing (in this case) f(s => C(s)).

• Duduk says:

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.

Regards.
Duduk

• Duduk says:

Didn’t come out quite as I typed it
Meant to say: <: C]

• Duduk says:

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

Regards,
Duduk

6. Great talk, now I need “Type Level Programming for Beginners” :) Any suggestions?

7. Joseph says:

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!