• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Flawed hasSubsequence solution in Functional Programming in Scala exercise 3.24?

 
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I actually found a bug in that code ^^^^ today.

It breaks when there are repeating numbers in the sequence / list that match the head of the search subsequence.

For Example: Searching for List(1,2,3) in List(4,1,1,2,3,7,8,9).

This fixes:

 
Ranch Hand
Posts: 121
12
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, Scott.

Your last code gives incorrect results on tests like searching List(1,1,1,2) inside List(1,1,1,1,2). However, you are right that book solution is not optimal in the terms of execution time. You can see that problem on sequences with long series of equal elements. It is hard to process that sequences both fast and correct at the same time

It is interesting that best algorithms still have a linear search complexity regardless of the sequence and subsequence patterns. You could search for "String Searching Algorithms". There are many interesting approaches with different characteristics. My personal preference is Knuth-Morris-Pratt algorithm.
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well now you had to go and mess it all up. :-D

This seems to work for that case but now I'm tracking so many variables...when I get a chance I'll try to refine this. There has to be a more elegant approach. I've heard of the other algorithms you mention. Looks like I'll have to look into them over Christmas break!

 
author
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The nonstrict solution in chapter 5 improves on this answer. To quote exercise 3.24:

You may have some difficulty finding a concise purely functional implementation that is also effi- cient. That’s okay. Implement the function however comes most naturally. We’ll return to this implementation in chapter 5 and hopefully improve on it.



Rúnar
 
I am going to test your electrical conductivity with this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic