It is not "impossible" to implement digitsToDouble((Seq('2', '0', '4', '.', '5')) with just map, zip and reduce

[darrylkid]

From the latest Nov 23, 2023 draft, Sergei claims In page 13 from CH 1 and page 33 from CH 2, digitsToDouble((Seq('2', '0', '4', '.', '5')) is unsolvable using map, filter, sum, zip and others without using induction. I think the claim is too strong here because you actually can come up with such an implementation:

object Main {
    def DigitsToDouble(s: Seq[Char]): Double =
    {
        val n = s
        .map( c => c == '.' )
        .zipWithIndex
        .filter{ case (isPeriod, index) => isPeriod }
        .map{ case (isPeriod, index) => index }
        .headOption
        .getOrElse(0)

        s
        .filter(c => c != '.')
        .zipWithIndex
        .map{ case (c, index) => (c, n - 1 - index) }
        .map{ case (c, exponent) => c.toString.toDouble * Math.pow(10, exponent) }
        .sum
    }

    def main(args: Array[String]) = 
    {
        println(DigitsToDouble(Seq('1', '2', '3', '.', '0', '5')))
    }
}

Run here

[philipschwarz]

Interesting! FWIW, I asked ChatGPT "how is zipwithindex related to induction?":

The zipWithIndex operation is a common operation in programming, especially in functional programming contexts, where it is used to combine elements of a collection with their indices. While zipWithIndex itself is not directly related to mathematical induction, there is a conceptual connection when you think about the iteration over a collection in a functional programming context.

Mathematical induction is a proof technique that is often used to establish a property for all natural numbers. It consists of two steps: the base case, where the property is shown to hold for the smallest value (usually zero or one), and the inductive step, where it is shown that if the property holds for a certain value, then it must also hold for the next value.

Now, consider a scenario where you have a collection of elements and you want to perform some operation on each element, considering its position in the collection. You might start by showing that the operation holds for the first element (base case) and then prove that if it holds for one element, it holds for the next (inductive step).

The zipWithIndex operation is often used in functional programming to iterate over a collection, combining each element with its index. This can be related to induction in the sense that you're processing elements one by one, starting from the base case (index 0) and moving to the next indices in an incremental manner.

For example, in Scala:

val myList = List("apple", "banana", "cherry")

val result = myList.zipWithIndex.map { case (element, index) =>
  s"Element $element is at index $index"
}

// Output:
// List("Element apple is at index 0", "Element banana is at index 1", "Element cherry is at index 2")

In this example, you're combining each element of the list with its index. The base case is when the index is 0, and the inductive step is when you move to the next index.

While the zipWithIndex operation itself doesn't perform mathematical induction, the iterative nature of processing elements with their indices can be conceptually related to the principles of induction.

[winitzki]

Good catch!

Your code needs to iterates twice over the input sequence. Can this be done iterating only once?

Another problem is the loss of precision, perhaps due to Math.pow() but maybe unavoidable when dealing with Double values.

scala> ('1' to '9').map(c => DigitsToDouble(Seq('0', '.', c)))
val res0: IndexedSeq[Double] = Vector(0.1, 0.2, 0.30000000000000004, 0.4, 0.5, 0.6000000000000001, 0.7000000000000001, 0.8, 0.9)
scala> DigitsToDouble(Seq('0', '.', '1', '1', '9', '3'))
val res1: Double = 0.11929999999999999

Does this also happen in my implementation?

[winitzki]

@philipschwarz Very funny. "Prove that the operation holds in the base case." The language model has no idea what it is talking about but it can talk at length.

[winitzki]

@darrylkid In my implementation, the precision is a bit better (because I am not using math.pow()) but I still get the last example: digitsToDouble(Seq('0', '.', '1', '1', '9', '3')) == 0.11929999999999999

[philipschwarz]

@philipschwarz Very funny. "Prove that the operation holds in the base case." The language model has no idea what it is talking about but it can talk at length.

@winitzki Yes!

I then asked it

what do you mean when you say that 'a certain operation is true'?

and it responded as follows:

I apologize for any confusion caused by the imprecise phrasing. When I mentioned "a certain operation is true," I made an error in language that doesn't accurately capture the concept. Let me clarify.

Operations are actions or procedures, and they are not typically described as being "true" or "false." Instead, properties, predicates, or statements can be true or false. ... Again, I appreciate your attention to precision, and I hope this clarification helps.

[darrylkid]

Your code needs to iterates twice over the input sequence. Can this be done iterating only once?

Probably not. There's a fundamental local dependency for the nth index where the period . resides. All elements of the sequence in the map needs to know n to independently calculate its own exponent. However, the way n is known is if the local element has c == '.' and it communicates index n to other elements of the sequence. I don't of any better way to communicate n to other elements besides introducing variable n for all elements to see and use.

In regards to precision lost, I'm sure you can introduce additional data structures for more precision. Floating point is just a tough problem in general 😞 .

I just wanted to highlight the fact that you can solve this problem with two series of transformations (finding n and computing the Double), and recursion is not strictly necessary for the solution. Something to keep in mind.

[winitzki]

L will need to update the text of the chapter and explain what we just discussed.

[winitzki]

Text updated after latest merge to master, should be good now.