Home > Software design >  How can I make a list of start-/end indices in Haskell?
How can I make a list of start-/end indices in Haskell?

Time:09-16

I am trying to make a Haskell function that takes two strings as arguments, the first is the string we want to locate in the second argument, and return a list of tuples with the start- and end indices of every occurrence. For example,

indexTuples :: String -> String -> [(Int, Int)]
indexTuples "aa" "foobaarfoobaar" 

Output: [(4,5), (11,12)] 

So far I have made a helping function that finds the indices ( I am trying to not use any extra methods other than Prelude methods, but implement by myself).

My helper function takes a string and a char and gives back the indices like so:

findPos :: (Num a1, Enum a1, Eq a2) => [a2] -> a2 -> [a1]
findPos str c = [index | (x, index) <- zip str [0..], x == c]

(I found this solution here.) This function zips the string with the infinite list of numbers into tuples, and then selects the tuples where the character equals the argument c and returns the index for each of them. This gives me this output:

Ok, one module loaded.
ghci> findPos "blablabla" 'b'
[0,3,6]

But how do I do this so that it takes in two strings instead? Like this:

ghci> findPos "blablabla" "bl" 
[(0,1), (3,4), (6,7)] 

I tried to just change the c from a char to a string object, but then I get several errors in ghci.

CodePudding user response:

A (non-empty) string has a head element, a Char:

indexTuples :: String -> String -> [(Int, Int)]
indexTuples []     _   = []
indexTuples (c:cs) str =

Having found its index in the other string, -- a list of them for all the occurrences, -- using the function findPos which you already have,

  let
    ixs = findPos str c

we try each one of them

    len = length cs
    fits = [ (i,i len) | i <- ixs, cs == (take len $ drop i str)]

and that's our answer.

   in
      fits
  • Related