函数式编程算法查找重复字符 [英] functional programming algorithm for finding repeated characters

问题描述

我转换zxcvbn密码强度的算法从JavaScript来斯卡拉。我要寻找一个纯粹的功能性算法找出重复的字符序列的字符串。

I am converting the "zxcvbn" password strength algorithm from JavaScript to Scala. I am looking for a pure functional algorithm for finding sequences of repeating characters in a string.

我知道，我可以翻译的版本必须通过JavaScript，但我想保持这是无副作用的可能，所有的通常是函数式编程说明理由。

I know that I can translate the imperative version from JavaScript, but I would like to keep this as side-effect free as possible, for all the reasons usually given for functional programming.

该算法可以在Scala中，Clojure中，哈斯克尔，F＃，甚至是伪code。

The algorithm can be in Scala, Clojure, Haskell, F#, or even pseudocode.

感谢。

推荐答案

使用Haskell的标准高阶函数：

Using Haskell's standard higher-order functions:

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

• Data.List.group finds runs of equal elements in a list:

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

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

We care about the length of these runs, not the elements themselves:

> 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]

荏苒这两个列表给了我们所有对起始位置和相应长度的：

Zipping these two lists gives us all pairs of starting positions and corresponding lengths:

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

最后，我们删除长度不的群体比3。

Finally, we remove the groups of length less than 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

这篇关于函数式编程算法查找重复字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！