如何在不多次遍历字符串的情况下跟踪字符串的多个属性？

Question

我最近做了一道验证字符串的练习题。

Use the Maybe type to write a function that counts the number of vowels in a string and the number of consonants. If the number of vowels exceeds the number of consonants, the function returns Nothing.

我最终得到了两个函数，分别计算元音和辅音：

isVowel :: Char -> Bool
isVowel c = c `elem` "aeiou"

countVowels :: String -> Integer
countVowels []     = 0
countVowels (x:xs) =
  if isVowel x
  then countVowels xs + 1
  else countVowels xs

countConsonants :: String -> Integer
countConsonants []     = 0
countConsonants (x:xs) =
  if not $ isVowel x
  then countConsonants xs + 1
  else countConsonants xs

然后通过比较两者的值得到我的答案。

makeWord :: String -> Maybe String
makeWord [] = Nothing
makeWord s  =
  if countVowels s < countConsonants s
  then Nothing
  else Just s

我的问题是它遍历字符串两次，一次获取元音的数量，另一次获取辅音的数量。

我想也许我可以通过从开始的字符串长度中减去元音的数量来解决这个问题，但这也需要两次遍历。

所以我尝试制作一个同时跟踪元音和辅音的函数，将结果存储在一个元组中，但由于我不知道添加元组实际上非常困难，所以结果更加复杂。

countVowelsAndConsonants :: String -> [(Integer, Integer)]
countVowelsAndConsonants []     = []
countVowelsAndConsonants (x:xs) =
  if isVowel x
    then (1, 0) : countVowelsAndConsonants xs
    else (0, 1) : countVowelsAndConsonants xs

makeWord :: String -> Maybe String
makeWord [] = Nothing
makeWord s  =
  if countVowels s < countConsonants s
    then Nothing
    else Just s
  where counts = let unzipped = unzip (countVowelsAndConsonants s)
                 in (sum $ fst unzipped, sum $ snd unzipped)

而且，老实说，我认为这比我开始的时候还要糟糕。

此外，如果我还必须跟踪大小写字母怎么办？那么我认为元组方法不会扩展。

命令式语言，比如我比较习惯的javascript，遍历一次就这么简单

const word        = "somestring"
let numVowels     = 0
let numConsonants = 0

for (var s of word) isVowel(s) ? numVowels++ : numConsonants++

我确定Haskell有一个方法很简单，但不幸的是我不熟悉。

保持 String 的多个属性的选项卡而不必多次遍历它的惯用方法是什么？

Answer 1

对状态使用 foldr 有点简单：

countVCs :: String -> (Int, Int)
countVCs str = foldr k (0, 0) str
   where
     k x (v, c) = if isVowel x then (v + 1, c ) else (v , c + 1 )

另一种方法是 Data.List.partition 后跟对的两个元素 length：

countVCs :: String -> (Int, Int)
countVCs str = both length (partition isVowel str)
  where 
    both f (x,y) = (f x, f y)

另一种方法是使用 foldMap 和 (Sum Int, Sum Int):

countVCs :: String -> (Int, Int)
countVCs str = both getSum (foldMap k str)
  where
    k x          = if isVowel x then (Sum 1, Sum 0) else (Sum 0, Sum 1)
    both f (x,y) = (f x, f y)

Answer 2

我首先定义传统的 "indicator function"

indicate :: Num a => Bool -> a
indicate b = if b then 1 else 0

所以

indicate . isVowel :: Char -> Integer

接下来，我会从 Control.Arrow

获得两个关键的工具包

(&&&) :: (x -> y) -> (x -> z) -> x -> (y, z)
(***) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)

所以（记住有些字符既不是元音也不是辅音）

(indicate . isVowel) &&& (indicate . isConsonant)
  :: Char -> (Integer, Integer)

然后我会从 Data.Monoid 手中抓住 Sum。

(Sum . indicate . isVowel) &&& (Sum . indicate . isConsonant)
  :: Char -> (Sum Integer, Sum Integer)
getSum *** getSum :: (Sum Integer, Sum Integer) -> (Integer, Integer)

现在我部署 foldMap，因为我们正在做某种幺半群 "crush"。

(getSum *** getSum) .
foldMap ((Sum . indicate . isVowel) &&& (Sum . indicate . isConsonant))
  :: String -> (Integer, Integer)

然后我记得我写了一些变成了 Control.Newtype 的代码，我发现下面缺少但应该在那里。

instance (Newtype n o, Newtype n' o') => Newtype (n, n') (o, o') where
  pack = pack *** pack
  unpack = unpack *** unpack

现在我只需要写

ala' (Sum *** Sum) foldMap ((indicate . isVowel) &&& (indicate . isConsonant))
  :: String -> (Integer, Integer)

关键小工具是

ala' :: (Newtype n o, Newtype n' o') =>
 (o -> n) -> ((a -> n) -> b -> n') -> (a -> o) -> b -> o'
-- ^-packer    ^-higher-order operator  ^-action-on-elements

打包程序的工作是 select 具有正确行为实例的新类型，并确定解包程序。它的设计恰好是为了支持在本地以更具体的类型工作，以表明预期的结构。

Answer 3

坦率地说，函数式编程中最惯用的方法是不要担心额外的遍历，而寻求更简单的解决方案提供的改进的可读性和可组合性。两次遍历还是O(n)。除非你的字符串很大或者是从网络流这样的不可逆源读取的，否则这两种遍历的性能差异可以忽略不计。

此外，您不需要使用递归。 countVowels 和 countConsonants 可以实现为：

countVowels = length . filter isVowel
countConsonants = length . filter (not . isVowel)

Answer 4

另一种方法是使用像 foldl 这样的 'beautiful folding' 库。那么这个问题基本上就简化为写一个表达式。我来分：

import qualified Control.Foldl as L
import Control.Lens

isVowel :: Char -> Bool
isVowel c = c `elem` "aeiou"

countVowels, countConsonants :: L.Fold Char Int
countVowels = L.handles (filtered isVowel) L.length
countConsonants  = L.handles (filtered (not.isVowel)) L.length

lessVowels :: L.Fold Char Bool
lessVowels  = (<) <$> countVowels <*> countConsonants 

makeWord :: String -> Maybe String
makeWord s =  if L.fold lessVowels s then Nothing else Just s

所以我说

 >>> makeWord "aaa"
 Just "aaa"
 >>> makeWord "ttt"
 Nothing

使用 foldl，您可以同时运行在同一个 material 上无限多次折叠。元素序列可以是纯列表、向量或数组，也可以是像管道或管道这样的有效流。折叠的构成与最终将其折叠起来的内容无关。

我在上面使用了handles，这可能有点复杂，因为它使用了透镜，但这允许不同的折叠考虑到不同种类的元素。所以在这里，一个折叠只有 'looking' 在元音处，另一个在辅音处。如果不用 filtered isVowel 镜头，手写这些折叠会很简单。

如何在不多次遍历字符串的情况下跟踪字符串的多个属性？

How do you keep track of multiple properties of a string without traversing it multiple times?

haskell

functional-programming

traversal

list