Implement "return" of sequential languages in Haskell

Question

Currently reading through the Learn You a Haskell, and I've come across this example for searching if a sublist is inside a list:

searchSublist :: (Eq a) => [a] -> [a] -> Bool
searchSublist needle haystack =
  let nlen = length needle
  in foldl (\acc x -> if take nlen x ==  needle then True else acc) False (tails haystack)

Algorithm optimality aside (Horspool's algorithm comes to mind), it seems inefficient for Haskell to use folds and keep iterating through values when it could just "stop" when it hits "True". I.e., say, in Python, we could have something like...

def sublist_exists(needle, haystack):
  nlen = len(needle)
  if len(haystack) < nlen:
    return False
  elif haystack[:nlen] == needle:
    return True
  else:
    return sublist_exists(needle, haystack[1:])

and we would stop if we hit a True condition.

However, for the Haskell code, if I switch the fold to a scan, I get...

searchSublist :: (Eq a) => [a] -> [a] -> [Bool]
searchSublist needle haystack =
  let nlen = length needle
  in scanl (\acc x -> if take nlen x ==  needle then True else acc) False (tails haystack)

ghci> searchSublist [3,4,5] [1..5]
[False,False,False,True,True,True,True]

Seems inefficient to traverse through the entire list.

Answer 1

it seems inefficient for Haskell to use folds and keep iterating through values when it could just "stop" when it hits True.

If you use foldr and use tha laziness that (||) uses, it can stop from the moment it finds an element. For example take nlen x will not first calculate the entire list, this will be done lazily as well, so the (==) function will check elementwise, and from the moment one of the two elements is different, it will stop.

We can use of isPrefixOf :: Eq a => [a] -> [a] -> Bool to check if one list is the prefix of the other, which is more elegant than writing this with take nlen.

We can thus implement this as:

searchSublist :: (Eq a) => [a] -> [a] -> Bool
searchSublist needle = foldr ((||) . isPrefixOf needle) False . tails

or with any :: Foldable f => (a -> Bool) -> f a -> Bool:

searchSublist :: (Eq a) => [a] -> [a] -> Bool
searchSublist needle = any (isPrefixOf needle) . tails

There is also an isInfixOf :: Eq a => [a] -> [a] -> Bool function which seems to do what you here implement.