所以我是Haskell的新手,我想弄清楚为什么我的天真实现实际上比我认为更智能的解决方案更快.
我正在尝试编写一个函数,给定一个String将返回一个Bool指示String是否使用一个且恰好是一个元音的函数.以下是我天真的实现:
singleVowel :: Maybe String -> Bool
singleVowel Nothing = False
singleVowel (Just s) = singleVowel (Just s) = length (nub $ filter (`elem` "aeiouyAEIOUY") s) == 1
请注意,我过滤掉了元音集中没有的所有元素.然后,我使用该nub函数进行另一次传递,从筛选列表中删除重复项,并查看列表中是否只有1个元音.然后在最坏的情况下,此解决方案将使用O(n)内存和时间,因为它必须为筛选列表分配内存.
现在对于我的另一个解决方案,我决定使用递归并在每次递归调用时传递一个字符,以便在看到当前元音时跟踪当前元音.
singleVowelFaster :: Maybe String -> Bool
singleVowelFaster Nothing = False
singleVowelFaster (Just s) = singleVowelHelper s Nothing
singleVowelHelper :: String -> Maybe Char -> Bool
singleVowelHelper [] Nothing = False
singleVowelHelper [] _ = True
singleVowelHelper (x:xs) Nothing = if x …