haskell - 如何查找具有开始和结束索引的字符串的所有子字符串

Question

我最近编写了一些处理字符串的 Scala 代码，查找其所有子字符串并保留在字典中找到的子字符串的列表。整个字符串中子字符串的开头和结尾也必须保留以供以后使用，因此最简单的方法似乎就是使用嵌套的 for 循环，如下所示:

for (i <- 0 until word.length)
  for (j <- i until word.length) {
    val sub = word.substring(i, j + 1)
    // lookup sub in dictionary here and add new match if found
  }

作为练习，我决定尝试在 Haskell 中做同样的事情。这看起来很简单，不需要子字符串索引 - 我可以使用类似 this approach 的东西获取子字符串，然后调用递归函数来累积匹配项。但如果我也想要索引，这似乎更棘手。

如何编写一个函数，返回一个列表，其中包含“父”字符串中的每个连续子字符串及其开始和结束索引？

例如标记“blah”将给出[(“b”,0,0),(“bl”,0,1),(“bla”,0,2 )，...]

更新

精选的答案和大量新事物可供探索。经过一番困惑之后，我选择了第一个答案，丹尼尔的建议是允许使用 [0..]。

data Token = Token String Int Int 

continuousSubSeqs = filter (not . null) . concatMap tails . inits

tokenize xs = map (\(s, l) -> Token s (head l) (last l)) $ zip s ind
    where s = continuousSubSeqs xs
          ind = continuousSubSeqs [0..]

鉴于我有限的 Haskell 知识，这似乎相对容易理解。

Answer 1

import Data.List

continuousSubSeqs = filter (not . null) . concatMap inits . tails

tokens xs = map (\(s, l) -> (s, head l, last l)) $ zip s ind
    where s   = continuousSubSeqs xs
          ind = continuousSubSeqs [0..length(xs)-1]

工作原理如下:

tokens "blah"
[("b",0,0),("bl",0,1),("bla",0,2),("blah",0,3),("l",1,1),("la",1,2),("lah",1,3),("a",2,2),("ah",2,3),("h",3,3)]