ハスケル関数の純粋な実装は、よりスマートなソリューションよりも高速ですか？

Question

私はハスケルの初心者です。なぜ私の純粋な実装が、よりスマートな解決策であると思ったよりも実際に速いのか理解しようとしています。

Stringは、を返す関数を作成しようとしています。これは、Stringが1つの母音だけを使用するかどうかを示します。私の素朴な実装は次のとおりです。

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 `elem` "aeiouyAEIOUY" 
    then singleVowelHelper xs (Just x) 
    else singleVowelHelper xs Nothing 
singleVowelHelper (x:xs) (Just c) = 
    (x `elem` "aeiouyAEIOUY" && c == x) && singleVowelHelper xs (Just c) 

しかし、何らかの奇妙な理由で、「素朴な」実装は「スマートな」ソリューションよりも速く実行されます。

ハスケルが怠惰なので、がで評価されていない可能性があります。ベースケースに達すると、すべてのサンクが評価され、「ナイーブ」実装よりも遅くなるのですか？

この場合、なぜ私は(x elem "aeiouyAEIOUY" && c == x)をif文に入れて評価すると、機能のパフォーマンスが似ているのですか？

私は2番目の機能が時間でO(1)のスペース使用量を持っていると言っていますか？

Answer 1

最も簡単な修正は、最初の&&コールの順序を逆にして、安価なelemチェックの前に格安==チェックを実行することです。

これは、機能がより速く実行されるようにします...しかし、それでも間違っています！基本的には、最初の母音の後に続くすべての母音はまったく同じ母音であると主張しています。その代わりにあなたが意図したのは、すべての母音が同じ母音であるという主張です。

(x == c || not (x `elem`vowels)) && singleVowelHelper xs (Just c) 

または、よく、本当に私は多少異なる関数全体を書くだろうが、上記の実装作業を行うための最も簡単な変更である：私はこのようにそれを記述します。より包括的な述語ベースの関数から始めて、母音に特化して記述する実装を次に示します。

exactlyOne :: Eq a => (a -> Bool) -> [a] -> Bool 
exactlyOne pred [] = False 
exactlyOne pred (x:xs) 
    | pred x = not . any pred . filter (/= x) $ xs 
    | otherwise = exactlyOne pred xs 

exactlyOneVowel :: String -> Bool 
exactlyOneVowel = exactlyOne (`elem` "aeiouAEIOU")