λ Tony’s blog λ

An exercise arising from an IRC discussion in #scala:

trait Functor[F[_]] {
  def fmap[A, B](fa: F[A], f: A => B): F[B]
}
 
trait Monad[M[_]] {
  def bind[A, B](ma: M[A], f: A => M[B]): M[B]
  def pure[A](a: A): M[A]
}
 
object ObserveFunctorMonad {
  def observe[K[_]](m: Monad[K]): Functor[K] = error("your homework")
}

Why Functional Programming Matters paraphrased — a result of a discussion in an IRC channel. Others may find value.

A program may be represented as a function that accepts some input and produces some outputλ This function may be composed of parts; other functions and values.

Suppose any function that exists. I will suppose one that is made of parts A, B, C and D. I might denote this A ∘ B ∘ C ∘ D. Now suppose you desire a function that is made of parts A, B, C and E. Then the effort required for your function should be proportional to the effort required for E alone.

The closer you are to achieving this objective for any function, the closer you are to the essence of (pure) functional programming. This exists independently of the programming language, though programming languages will vary significantly in the degree to which they accommodate this objective.

Imperative programming — specifically the scope of a destructive update — is the anti-thesis of this objective.

I am an avid GPS user and I visit Mount Mee State Forest regularly on my dirt bike (Husqvarna TE450). I encounter queries on forums for the locations of the campgrounds in this forest, so here they are:

Neurum Creek Campground
-27.061853° 152.696228°
-27°03′42.67″ 152°41′46.42″

Archer Campground
-27.016317° 152.697767°
-27°00′58.74″ 152°41′51.96″

You can get to Neurum Creek Campground by taking Sellin Road then turning onto Neurum Creek Road and following it north. Archer Campground can be found by taking Sellin Road then Lovedays Road, however, it is easier to approach from the north side of the forest and head south. Both of these campgrounds require a permit through the Environmental Protection Agency (EPA) or you can book online.

There is another campground called Neurum Creek Bush Retreat but this is a different campground to those two mentioned. It is privately owned and I have personally stayed a weekend there and recommend it, especially if you have children or want a weekend of dirt bike riding (though the operators are understandably strict about noise control) since you can head south into Mount Mee State Forest or head over to Beerburrum State Forest. This campground is even further north of the state forest than the other two (which are situated in the forest boundaries), but is a short ride on gravel to the forest entrance.

Here is a reasonably comprehensive GPX file of Mount Mee State Forest including the two campgrounds and many dirt trails. I’d upload it to OpenStreetMap but I have yet to figure that out.

I use a Garmin 60Cx unit.

I hope this helps

Update: I have uploaded all tracks to OSM See here

Nov 17 15:48:39 <jinok> i hate wasting vertical space declaring vals that i need to initialize outside of a try block so i can clean them up in a finally block
Nov 17 15:48:53 <jinok> so i’ve started doing the initialization using lazy vals.

sealed trait Resource[+T] {
  val value: T
  def close: Unit
 
  def use[X](f: T => X) = try { f(value) } finally { close }
}
 
import java.io.InputStream
 
object Resource {
  def resource[T](t: T, c: => Unit) = new Resource[T] {
    val value = t
    def close = c
  }
 
  implicit def InputStreamResource(t: InputStream) = resource(t, t.close)
}
 
object Example {
  import Resource._
 
  def main(args: Array[String]) {
    val in = new java.io.FileInputStream("/etc/passwd")
    // print the first character of /etc/passwd
    println(in use (_.read.toChar))
  }
}

Reader’s exercise: Resource is a functor and monad. Implement the map and flatMap methods. Observe trickiness and ask why?

Re: Comments on http://jamesshore.com/Blog/The-Decline-and-Fall-of-Agile.html

For example

Well, okay, but Agile is starting to sound a lot more like religious rhetoric than an engineering practice.

and

Insert compelling argument here.
It is a religion.

Agile is not a religion, however, both Agile and religions are non-ideas. Also referred to as the third value of the propositional truth trichotomy, “not even false”, non-terminating computation, the bottom value, unfalsifiable, or if you prefer, outright nonsense. All religions and Agile (and Scrum and REST and SOA and… need I go on?) fall into this broader category. It might be healthy to call this category “religion”, but many observers - at least in my dealings - won’t understand why you have shifted to this consistent definition.

Hitherto Agile and religions exhibit common traits; ill-definition (you know the real Agile or are you a real Muslim?), sub-cultures in conflict (religion implies war), extreme absurdity in contrast to a mild absurdity (an invisible sky daddy watching everything we do, whose son died for sins…), cult leaders able to alter the course of the flock and cognitive dissonance - holding two otherwise immediately apparent logically contradicting positions at once.

I’m happy to hear this pseudo-science is falling - its absence is an improvement for the industry and the quality of software development. However, the concern is that it will be replaced by another non-concept for the scientific-illiterates to sustain their well-intentioned misguidance.

History tells us that its downfall is not an improvement. After all, what was immediately before the current Abrahamic false ideas? The creation of the universe and therefore, the first religions? No, I don’t think so either - I don’t think anybody does

I have a couple of whining rants on here about the ineptitude of the IntelliJ IDEA Early Access Program releases and the Scala plugin. It was, at that time, quite unusable, which is fine on its own, but I was concerned by the fact that the number and magnitude of the workarounds was increasing over time.

I am pleased to report that my preliminary use of the recently released IntelliJ IDEA 8.0 and the Scala plugin appears to require significantly less workarounds to the degree that it is now usable. In fact, it is more usable than it has been in a long time.

Myself and at least one other person were initially tricked into believing that there was no Scala plugin available because it was not listed in the Available plugins. There was however, a “Scala Application runner” plugin available. Installing this also installs the Scala plugin.

Unless I am making a judgment too early, I consider IntelliJ IDEA to have redeemed itself from my earlier complaints and I am thankful to the JetBrains team for making it so (with little/no effort on my part).

Interestingly, I note that JetBrains are considering adding automated specification testing and make a reference to ScalaCheck in this discussion. I wonder if they are aware of this alternative (Functional Java) that does the same with a more comprehensive library and also able to be used from standard Java.

Thanks for listening to my whining earlier and thanks to JetBrains for making smooth development with Scala possible

Edit: Except this same old bug is still there (it has been there for months) when expanding some source trees (I know I’m not the only one to experience this):

Error during dispatching of java.awt.event.MouseEvent[MOUSE_PRESSED,(118,350),absolute(114,375),button=1,modifiers=Button1,extModifiers=Button1,clickCount=1] on frame0
java.lang.StackOverflowError
	at com.intellij.psi.impl.CachedValueImpl.a(CachedValueImpl.java:1)
	at com.intellij.psi.impl.CachedValueImpl.a(CachedValueImpl.java:70)
	at com.intellij.psi.impl.CachedValueImpl.a(CachedValueImpl.java:3)
	at com.intellij.psi.impl.CachedValueImpl.a(CachedValueImpl.java:104)
	at com.intellij.psi.impl.CachedValueImpl.getValue(CachedValueImpl.java:41)

Scalaz 3.2 includes support for a State data type for the Scala Programming Language. This data type is a monad and thus supports flatMap and can be used in a for-comprehension.

Below I will give a practical demonstration of why you might choose to use the State data type as a monad.

Consider a binary leaf tree data type:

sealed abstract class Tree[+A]
final case class Leaf[A](a: A) extends Tree[A]
final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

This is pretty simple so far. Now suppose we wanted to map a function across a Tree from left to right where the result depended on the previous result. For this example, consider that we wanted to number each leaf by adding 1 as we traverse left to right (at a given starting value). That is, the result depends on the previous result because we must add 1 to that previous result.

We might implement this by passing in the integer value and returning the pair of the Tree as it is constructed and the integer value as it increments. Such an implementation might look like this:

sealed abstract class Tree[+A] {
  def number(seed: Int): (Tree[(A, Int)], Int) = this match {
    case Leaf(x) => (Leaf(x, seed), seed + 1)
    case Branch(left, right) => left number seed match {
      case (l, ls) => {
        right number ls match {
          case (r, rs) => (Branch(l, r), rs)
        }
      }
    }
  }
}

This code is pretty messy and it would become even messier with a less trivial example to apply across the Tree.

The State data type is effectively a Function[S, (S, A)] and the monad instance runs across the Function[_, (_, A)] part. That is to say, the flatMap signature looks roughly like this:

trait State[S, A] {
  val s: Function[S, (S, A)] // abstract
  def flatMap[B](f: A => Function[S, (S, B)]): Function[S, (S, B)]
}

You might consider filling out this method signature for fun

The flatMap function allows the user to make the state change implicit rather than explicit (and messy!). The State data type includes a few useful methods and functions. I will only use two of those functions below; init, which constructs a State object that has computed the state itself. For example, going with the analogy to Function[S, (S, A)], the init function looks like this: s => (s, s) and so returns a State[S, S]. The second function is modify, which applies a transform the state and it is intended to ignore the computed value (Unit).

Here is our new implementation:

import scalaz.State
import scalaz.State._
 
def numbers: State[Int, Tree[(A, Int)]] = this match {
  case Leaf(x) => for(s <- init[Int];
                      n <- modify((_: Int) + 1))
                  yield Leaf((x, s + 1))
  case Branch(left, right) => for(l <- left.numbers;
                                  r <- right.numbers)
                              yield Branch(l, r)
}

This is much neater and hides the otherwise explicit recursive application of adding 1 to an integer. Following is a complete source file that can be compiled successfully against Scalaz 3.2 using the latest version of Scala.

sealed abstract class Tree[+A] {
  def number(seed: Int): (Tree[(A, Int)], Int) = this match {
    case Leaf(x) => (Leaf(x, seed), seed + 1)
    case Branch(left, right) => left number seed match {
      case (l, ls) => {
        right number ls match {
          case (r, rs) => (Branch(l, r), rs)
        }
      }
    }
  }
 
  import scalaz.State
  import scalaz.State._
 
  def numbers: State[Int, Tree[(A, Int)]] = this match {
    case Leaf(x) => for(s <- init[Int];
                        n <- modify((_: Int) + 1))
                    yield Leaf((x, s + 1))
    case Branch(left, right) => for(l <- left.numbers;
                                    r <- right.numbers)
                                yield Branch(l, r)
  }
}
final case class Leaf[A](a: A) extends Tree[A]
final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

And if you find Haskell easier to read, this might help too. It is a roughly equivalent program using GHC’s built-in State data type.

import Control.Monad.State.Lazy
 
data Tree a = Leaf a | Branch (Tree a) (Tree a)
 
number :: Int -> Tree a -> (Tree (a, Int),Int)
number seed (Leaf a) = (Leaf (a, seed), seed + 1)
number seed (Branch left right)
 = let (l, ls) = number seed left
       (r, rs) = number ls right
   in
       (Branch l r, rs)
 
numbers :: Tree a -> State Int (Tree (a, Int))
numbers (Leaf a) = do n <- get
                      modify (+1)
                      return (Leaf (a, n))
 
numbers (Branch l r) = do left <- numbers l
                          right <- numbers r
                          return (Branch left right)
 
initState :: State s s
initState = State (\s -> (s, s))

Well done. Keep it up.