(deftest p33-coprime-integers (is (coprime? 14 15)) (is (not (coprime? 14 21))))
Two positive integers are coprime if the only positive integer that divides them both is 1. That is equivalent to their greatest common divisor being 1.
The solution is trivial building upon the solution to the last problem.
Use Euclid's algorithm.
(deftest p32-euclids-algorithm (is (= 9 (gcd 36 63))) (is (= 21 (gcd 462 1071))) (is (= 1 (gcd 1 1))))
The greatest common divisor of two positive integers is the largest integer that divides them both without a remainder. A common form of Euclid's algorithm uses division and comparison. We start with a pair of numbers (here represented by the two arguments of the function). We then form a new pair consisting of the smaller of the two numbers and the remainder of dividing the larger number by the smaller one. We continue this process until the remainder is zero. The first number of the pair is then the greatest common divisor.
A simple recursive solution pretty much follows this description. We compare the second argument with zero to determine the exit condition. If we find it to be zero we return the first argument. Otherwise we recursively call the function itself with the second argument in the first argument's place and the remainder of the division in the second place.
The use of recursion can cause problems as the available stack size is not knowable and depends on runtime configuration. While Lamé's Theorem states that the number of steps in Euclid's algorithm never exceed five times the number of digits in the smaller number, this doesn't guarantee that we won't run out of stack frames given Clojure's support for integer sizes exceeding 64 bits. Using recur here makes the function "stack-safe."
If you look at the description of the algorithm above you will notice the implicit assumption that the first number is always the larger of the two. But we don't enforce the order of arguments (it could be done easily using Clojure's support for preconditions) because the first iteration of the algorithm will simply reorder them. This becomes clear when we make the first couple of substitutions explicit:
(gcd 36 63) (gcd 63 (rem 36 63)) (gcd 63 36)
(deftest p31-test-primes (is (not (prime? 4))) (is (prime? 7)))
My second solution is a translation of a primality test based on Fermat's Little Theorem as outlined in SICP 1.2.6. It says that a number n is certainly not prime if raised to a random positive integer a less than n and divided by n is not equal to a.
This second approach is faster for large numbers but it is a probabilistic algorithm. This means in our case if the remainder of a^n divided by n is a, the number n is only probably a prime. While the probability gets higher every time we successfully run the test with another number, there is no "guarantee".
In addition the Fermat test can be fooled by a couple of extremely rare numbers (called Carmichael numbers). Read the relevant chapter in SICP for more on this topic.
Imagine, you have a list of options on Strings and you want to work with the values (the Somes) and ignore the absent values (the Nones). One way of doing that would be something like this:
val names = List(Some("Peter"), None, Some("Mary"))
names.flatMap(n => n.map("Hello " + _))
You might remember faintly what the type signature of flatMap was and think: hang on a minute, what's going on here?
def flatMap[A,B](f: A => List[B]): List[B]This is obviously simplified compared to the actual Scala standard library version of flatMap (look for TraversableLike#flatMap). But still flatMap takes a function from A to List[B], while Option's map looks like this:
@inline final def map[B](f: A => B): Option[B] =
if (isEmpty) None else Some(f(this.get))
So how does the result of map which is of type Option[String] turn magically into List[Option[B]]? Implicit conversion is the answer. If scalac finds a type mismatch between what we are passing in and what the function expects it looks for an implicit view definition to satisfy the expression.
We can use scalac's print option to see what's going on under the hood:
p_brc@brc-mbp ~/s/s/S/s/t/s/intro> scalac -print Tester.scala
//lots of code removed
// here is the call to flatMap
Tester.this.names().flatMap({
(new anonymous class anonfun$1(): Function1)
}, immutable.this.List.canBuildFrom());
// more synthetic classes removed
// here is the synthetic class representing the outer lambda function:
@SerialVersionUID(0) final class Tester$$anonfun$1 extends runtime.AbstractFunction1 with Serializable {
final def apply(n: Option): Iterable = scala.this.Option.option2Iterable(n.map({
(new anonymous class anonfun$apply$1(Tester$$anonfun$1.this): Function1)
}));
final def apply(v1: Object): Object = Tester$$anonfun$1.this.apply(v1.$asInstanceOf[Option]());
def (): anonymous class anonfun$1 = {
Tester$$anonfun$1.super.();
()
}
}
You can see how the lambda is represented by a synthetic class Tester$$anonfun$1. In its apply method the code we defined is wrapped in a call to option2Iterable.
Option.option2Iterable is the implicit view definition that was in scope and was automagically injected by the compiler. It is quite simple and looks like this:
implicit def option2Iterable[A](xo: Option[A]): Iterable[A] = xo.toList
Riddle solved. Are we happy now? Maybe, but implicit conversions are certainly one of Scala's features that can lead to confusing if not unintelligible code quite easily. But then again, that is nothing new and if you look at the related literature, be it Odersky, Spoon, Venners: Programming in Scala or Suereth: Scala in Depth, the chapters covering implicit conversions are full of warnings and calls for restraint. Therefore: advance with caution.
(deftest p28-sublist-sort
(is (= '((o) (d e) (d e) (m n) (a b c) (f g h) (i j k l))
(lsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))))))
(deftest p28-sublist-freq-sort
(is (= '((i j k l) (o) (a b c) (f g h) (d e) (d e) (m n))
(lsort-freq '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))))))
"Note that in the above example, the first two lists in the result L have length 4 and 1, both lengths appear just once. The third and forth list have length 3; there are two list of this length. And finally, the last three lists have length 2. This is the most frequent length."
The solution to a) is trivial if we use Clojure's sort-by and base the key function on the count of the sublists.
The solution to b) is based on the frequencies of the sublists. Clojure comes with the frequencies function that we use on the lengths of the sublists. All that is left is to call sort on the list of lists and use the frequencies map to determine the order of the sublists.