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

Question

我最近做了一个验证字符串的练习题.

使用该Maybe类型编写一个函数,该函数计算字符串中元音的数量和辅音的数量.如果元音的数量超过辅音的数量,则该函数返回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有一种简单的方法,但不幸的是我不熟悉.

什么是保持a的多个属性的标签String而不必多次遍历它的惯用方法是什么？

Answer 1

我首先定义传统的"指标功能"

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)

然后,我会抓牢Sum的Data.Monoid.

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

现在我部署foldMap,因为我们正在进行某种单一的"迷恋".

(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

封隔器的工作是选择具有正确行为实例的newtype,并确定解包器.它的设计旨在支持在更具体的类型上本地工作,从而发出预期结构的信号.

Answer 2

使用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)