Finding the index of a string that contains a substring recursively

Question

Im trying to find the index of a string in the context of a list that contains a certain substring, with no avail. Im unsure how one may pass the entirety of the untouched array as an argument to another function in a recursive function. Here is my approach:

find' :: [String] -> Maybe Int
find' [] = error "List is empty"
find' [x] = return maybe 0
find' (x:xs)
    | "HU" `isInfixOf` x = return elemIndex x (x:xs)
    | otherwise = checkTail
    where checkTail = find' xs

The error is namely:

 * Couldn't match type `[[String]] -> Maybe Int' with `Maybe Int'
  Expected type: String -> [String] -> Maybe Int
    Actual type: String -> [String] -> [[String]] -> Maybe Int
* The function `return' is applied to three arguments,
  but its type `([String] -> [[String]] -> Maybe Int)
                -> String -> [String] -> [[String]] -> Maybe Int'
  has only four
  In the expression: return elemIndex x (x : xs)
  In an equation for find':
      find' (x : xs)
        | "HU" `isInfixOf` x = return elemIndex x (x : xs)
        | otherwise = checkTail
        where
            checkTail = find' xs

   | "HU" `isInfixOf` x = return elemIndex x (x:xs)
                      ^^^^^^^^^^^^^^^^^^^^^^^^^

I dont really understand the error and why it doesnt match, because in both cases im returning a maybe int. However as I've mentioned im not sure if (x:xs) actually means the entire list for the argument. Just to clarify, im trying to find the index of the string from a list of strings.

I find it very hard to understand what you're trying to do with this - in particular what you mean by return and maybe. They are both standard functions in Haskell, but I strongly suspect neither does what you think it does. (In particular by return maybe 0 I think you just mean Just 0) — Robin Zigmond

chepner chepner · Accepted Answer · 2019-04-22T15:49:45

First, maybe is a function by itself; what it does isn't relevant to the question. Suffice to say, return 0 does what you want: it returns Just 0 from the function:

find' :: [String] -> Maybe Int
find' [] = Nothing
find' [x] = return 0 -- equivalent to find' [x] = Just 0

(Note the use of Nothing; if you are going to raise an error, there's no reason to use Maybe Int instead of Int as the return type. Also, there's no reason to use return over Just, since you aren't trying to support an arbitrary monad here.)

Further, elemIndex already returns a value of type Maybe Int; you don't need to use the return function, which wraps the value in another layer, producing a Maybe (Maybe Int) value, which is not what you want.

find' (x:xs)
    | "HU" `isInfixOf` x = elemIndex x (x:xs)
    | otherwise = find' xs

One last problem: if "HU" isn't present in the first element of the list, you are correct to simply call find' on the tail of the list. However, you need to add 1 to that return value to compensate for passing a shorter argument. (This also means you don't need elemIndex, since you always find "HU" in the head of the current list.)

find' (x:xs)
    | "HU" `inInfixOf` x = Just 0
    | otherwise = fmap (1+) (find' xs)

You need to use fmap; find' returns a Maybe Int, not an Int, so 1 + find' xs by itself won't work.

This also means you can drop the special case for [x], since it follows from finding the search string in the head of the list. The entire function is just

find' :: [String] -> Maybe Int
find' [] = Nothing
find' (x:xs)
    | "HU" `isInfixOf` x = Just 0
    | otherwise = fmap (1+) (find' xs)

One way that works with the entire list is to search the entire list at once, then find the (first) occurrence of True in the resulting list of booleans.

find'' :: [String] -> Maybe Int
find'' xs = elemIndex True (map ("HU" `inInfixOf`) xs)
-- or find'' = elemIndex True . map ("HU" `inInfixOf`)
-- or find'' = findIndex ("HU" `inInfixOf`)

Finding the index of a string that contains a substring recursively

1 Answers