algorithm - 查找重复字符的函数式编程算法

Question

我正在转换 "zxcvbn" password strength algorithm从 JavaScript 到 Scala。我正在寻找一种纯函数算法来查找字符串中重复字符的序列。

我知道我可以从 JavaScript 翻译命令式版本，但我希望尽可能避免产生副作用，因为函数式编程通常给出的所有原因。

算法可以是 Scala、Clojure、Haskell、F#，甚至是伪代码。

谢谢。

Answer 1

使用 Haskell 的标准高阶函数:

• Data.List.group 查找列表中相等元素的运行:

  > group "abccccdefffg"
  ["a","b","cccc","d","e","fff","g"]
  

• 我们关心这些运行的长度，而不是元素本身:

  > let ls = map length $ group "abccccdefffg"
  > ls
  [1,1,4,1,1,3,1]
  

• 接下来，我们需要每个组的起始位置。这只是组长度的部分和，我们可以使用 scanl 计算:

  > scanl (+) 0 ls
  [0,1,2,6,7,8,11,12]
  

• 压缩这两个列表可以得到所有对的起始位置和相应的长度:

  > zip (scanl (+) 0 ls) ls
  [(0,1),(1,1),(2,4),(6,1),(7,1),(8,3),(11,1)]
  

• 最后，我们删除长度小于 3 的组。

  > filter ((>= 3) . snd) $ zip (scanl (+) 0 ls) ls
  [(2,4),(8,3)]
  

综合起来:

import Data.List (group)

findRuns :: Eq a => [a] -> [(Int, Int)]
findRuns xs = filter ((>= 3) . snd) $ zip (scanl (+) 0 ls) ls 
  where ls = map length $ group xs