bbarrington (25) [Avatar] Offline
#1
After many hours of thought, I came up with a solution for Exercise 10, Chapter 10, section 3 that is almost identical to the one in the answer key. Alas, it reports that the sequence 1,3,2,4 is ordered. But so does the solution in the answer key. Below is the code with a simple test. Seems to me that in order to make this work with a balanced fold, you have to know which 'side' you are on when executing the binary operation in the Monoid.

Any thoughts?

-----------------------------------------------
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}

object OrderedTest {

def foldMapV[A, B](as: IndexedSeq[A], m: Monoid[B])(f: A => B): B = {
if (as.isEmpty) m.zero
else if (as.length == 1) f(as(0))
else {
val (l, r) = as.splitAt(as.length / 2)
m.op(foldMapV(l, m)(f), foldMapV(r, m)(f))
}
}

def ordered(ints: IndexedSeq[Int]): Boolean = {
val mon = new Monoid[Option[(Int, Boolean)]] {
def op(o1: Option[(Int, Boolean)], o2: Option[(Int, Boolean)]) =
(o1, o2) match {
case (Some((n, p)), Some((m, q))) =>
val b = n <= m
Some((if (p || b) n else m, p && b && q))
case (x, None) => x
case (None, x) => x
}
val zero = None
}
foldMapV(ints, mon)(i => Some((i, true))).map(_._2).getOrElse(true)
}

def main(args: Array[String]): Unit = {

val is = IndexedSeq(1, 3, 2, 4)
println(ordered(is)) // Should print 'false', but instead prints 'true'

}

}
runar (53) [Avatar] Offline
#2
Re: Chapter 10.3, Exercise 10 (Bug)
It looks like the answer key has an old version of this monoid. The Monoids.scala file in the answers directory has this:

[b]
// This implementation detects only ascending order,
// but you can write a monoid that detects both ascending and descending
// order if you like.
def ordered(ints: IndexedSeq[Int]): Boolean = {
// Our monoid tracks the minimum and maximum element seen so far
// as well as whether the elements are so far ordered.
val mon = new Monoid[Option[(Int, Int, Boolean)]] {
def op(o1: Option[(Int, Int, Boolean)], o2: Option[(Int, Int, Boolean)]) =
(o1, o2) match {
// The ranges should not overlap if the sequence is ordered.
case (Some((x1, y1, p)), Some((x2, y2, q))) =>
Some((x1 min x2, y1 max y2, p && q && y1 <= x2))
case (x, None) => x
case (None, x) => x
}
val zero = None
}
// The empty sequence is ordered, and each element by itself is ordered.
foldMapV(ints, mon)(i => Some((i, i, true))).map(_._3).getOrElse(true)
}
[]