I am past chapter 3 in the book now but I found the answers that the books authors provided at
https://github.com/fpinscala/fpinscala/blob/master/answers/src/main/scala/fpinscala/datastructures/List.scala the other day.
Is it just me, or for their solution to Exercise 3.24 (the hasSubsequence function), is it not inefficient? Since it calls a second method (startsWith) that has to perform a recursive series of matches as it iterates through the list from a specific point, it is doing a lot of work over and over again.
For example, when looking for List(1,2,3) inside a list like (1,2,4,1,2,5,1,3,1,1,2,3) every time it finds a 1 it starts looping down the list in the startsWith method. When it doesn't fully match, as in the case of the partial matches (1,2), (1,2), (1), (1) it eventually moves back to the main hasSubsequence function and tries to start matching again from the next index in that very series.
A dynamic programming approach can touch each element of the list only once to determine if the subsequence exists, as in the following code which was my solution to the problem as I was going through the book a week or two ago:
With this code, I think it simply moves to the next element in the list after a partial match is found, rather than jumping backward in the list to a previous marker.
Am I missing anything or being overly nitpicky? Or is this a valid criticism of the provided solution?