2
\$\begingroup\$

In an effort to strengthen my functional programming, I'm reading Functional Programming in Scala. One of the assignments is to implement a function that does the same operation as containsSlice in the List API.

@tailrec
  def hasSublist[T](list: List[T], currSub: List[T], origList: List[T], origSub: List[T]): Boolean = {
    (list, currSub) match {
      case (_, Nil) => true
      case (Nil, _) => false
      case (h1 :: t1, h2 :: t2) if h1 == h2 => hasSublist(t1, t2, origList, origSub)
      case (h1 :: t1, h2 :: t2) => hasSublist(origList.tail, origSub, origList.tail, origSub)
    }
  }

def hasSublist[T](list: List[T], sublist: List[T]): Boolean = hasSublist(list, sublist, list, sublist)

The second hasSublist is the function one would call. The first is the helper function.

I generally like my implementation. However, I wonder if there is a cleaner way of doing backtracking after partially matching the sublist and then finding that it doesn't completely match. Currently, I keep track of the list I am checking against in a variable passed to the function on every call, and likewise with the sublist that is being searched for. It seems a bit hacky to me although I can certainly live with it if there isn't a simple way to do it better. Any insight from experienced FP and Scala people would be fantastic.

\$\endgroup\$
2
\$\begingroup\$

Recursion usually makes backtracking easy. If it doesn't, your recursive function is probably doing too much. Yours does. The reason you built it that way is because your helper function returns a binary (boolean) value but you actually have 3 possible states at any one time

  1. Did match this segment of the list
  2. Did not match this segment of the list
  3. Ran out of list.

You deal with this by carrying all of your state forwards, making your code more complex and hard to read than it needs.

All you need is a nice functional way to return 3 states and your code can become much simpler. You must have been introduced to the Option monad by now. All you need to do is have your helper function (which should be hidden inside your hasSublist function, by the way) return Option[Boolean]. Now you can return 3 states:

  1. true (Found a match)
  2. false (Did not find a match)
  3. Nothing (Ran out of list)

Here is one way to do this:

def hasSublist[T](list: List[T], sub: List[T]): Boolean = {
  def matchSub(ls: List[T], ss: List[T]): Option[Boolean] = (ls, ss) match {
    case (_, Nil) => Some(true)
    case (Nil, _) => None
    case (x :: xs, y :: ys) if x == y => matchSub(xs, ys)
    case (_, _) => Some(false)
  }

  matchSub(list, sub) match {
    case None => false
    case Some(false) => hasSublist(list.tail, sub)
    case _ => true
 }
} 

It should be clear that this is simpler. It separates the business of matching the sublist to the current list from deciding whether to return a definite result or recur over the tail of the list. In the latter case, we recur using the outer function, not the inner, making it easier to backtrack and maintain appropriate state (recursion does this for us, simply).

I only used pattern matching and recursion in the second half of the function to make it simple and obvious. I would prefer to fold over the list and to apply fold or map to the Option[Boolean] result, but I don't know if you have covered those subtleties yet. However, because I have separated concerns in a functional manner, it is very easy to change either or both halves of my code to use fold/map. The outer function can be redesigned simply with no change to the inner function, or vice versa.

EDIT: adding map and fold examples as requested

Using map and getOrElse to replace the outer half:

  matchSub(list, sub) map {found => 
    if (found) true else hasSublist(list.tail, sub)
  } getOrElse false 

If an Option contains a value, map unpacks it, applies the function and wraps the result in Some. If it contains None, it simply returns None. I don't think I need to explain getOrElse ;)

Using fold

  matchSub(list, sub).fold(false) {found =>
    if (found) true else hasSublist(list.tail, sub)
  }

Option's fold evaluates and returns the first parameter only if the Option contains Nothing. Otherwise it unwraps the value and applies the function.

There is much disagreement about which is better.

  • fold is not obvious to the non-expert and doesn't behave quite like other folds. But it is typesafe.
  • map + getOrElse is more obvious than fold (not as obvious as pattern matching) but can cause surprising errors because getOrElse will happily return any type that is a subtype of what is expected by whatever is calling map/getOrElse. Nothing compels it to be of the same type as whatever is wrapped in Option.
  • scalaz fans prefer to use their opt type and have access to more consistent functions
  • Martin Odersky prefers pattern matching.
\$\endgroup\$
  • \$\begingroup\$ This is exactly what I was looking for when I posted my question. You nailed it. I had considered using a separate mechanism like your match statement, but without Option, it would've been fairly ugly. I am wondering if you could add an implementation using fold. I tried, but haven't had success. \$\endgroup\$ – br1992 Jan 9 '15 at 17:14
  • \$\begingroup\$ Do you want me to add examples of how fold and map would work or are you still working it out for yourself? \$\endgroup\$ – itsbruce Jan 9 '15 at 18:05
  • \$\begingroup\$ I am very much stuck. It would really help if you could show me. \$\endgroup\$ – br1992 Jan 9 '15 at 18:10
  • \$\begingroup\$ That's done. Hope it makes sense. \$\endgroup\$ – itsbruce Jan 9 '15 at 19:18
  • \$\begingroup\$ OH! That's what you meant. I was trying to implement matchSub in terms of foldLeft. Thanks for the explanations. Fantastic answer. \$\endgroup\$ – br1992 Jan 9 '15 at 19:23
0
\$\begingroup\$

If you have a helper function that you do not intend for others to call, hide it as a nested function.

The fourth case is a catch-all, which could be simplified to (_, _).

def hasSublist[T](list: List[T], sublist: List[T]): Boolean = {
  @tailrec
  def sublistHelper[T](currList: List[T], currSub: List[T], origList: List[T], origSub: List[T]): Boolean = {
    (currList, currSub) match {
      case (_, Nil) => true
      case (Nil, _) => false
      case (h1 :: t1, h2 :: t2) if h1 == h2 => sublistHelper(t1, t2, origList, origSub)
      case (_, _) => sublistHelper(origList.tail, origSub, origList.tail, origSub)
    }
  }

  sublistHelper(list, sublist, list, sublist)
}

Here's a simpler implementation that uses List.tails and List.startsWith. I don't know if you consider that cheating in your quest to reinvent the wheel.

def hasSublist[T](list: List[T], sublist: List[T]): Boolean = {
  list.tails.find(candidate => candidate.startsWith(sublist)).nonEmpty
}
\$\endgroup\$
  • \$\begingroup\$ I think it is probably cheating ;) \$\endgroup\$ – itsbruce Jan 9 '15 at 13:20
  • \$\begingroup\$ I appreciate your answer, but I was looking for more of a conceptual improvement to my approach, which @itsbruce provided. The second snippet is cheating for me, but the author of the book did the same thing, so... \$\endgroup\$ – br1992 Jan 9 '15 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.