Haskell - 將高階函數轉換爲遞歸函數

Question

要求：寫入函數單個 - 測試列表中是否只有一個元素滿足給定條件。

single :: (a -> Bool) -> [a] -> Bool 

我寫了這個功能：

single p xs = count p xs == 1 
    where count pred = length . filter pred 

問題：什麼是最簡單的（正確）的方式轉換成上述功能於一體的遞歸函數，而不使用「高階函數」？

Answer 1

如何使用輔助功能

single' :: (a -> Bool) -> [a] -> Int -> Bool 
single' _ [] c = c == 1                                    
single' f (h:tl) c = single' f tl (if (f h) then c + 1 else c) 

然後

single :: (a -> Bool) -> [a] -> Bool 
single f l = single' f l 0 

Answer 2

你可以做這樣的：

single p = lookupFirst 
    where 
    lookupFirst []     = False 
    lookupFirst (x:xs) | p x  = lookupSecond xs 
         | otherwise = lookupFirst xs 
    lookupSecond []     = True 
    lookupSecond (x:xs) | p x  = False 
         | otherwise = lookupSecond xs 

Answer 3

我們可以用一個none斷言如果餘數來檢查的列表不符合條件：

single :: (a -> Bool) -> [a] -> Bool 
single p []  = False 
single p (x:xs) | p x  = none p xs 
       | otherwise = single p xs 

none :: (a -> Bool) -> [a] -> Bool 
none _ [] = True 
none p (x:xs) = not (p x) && none p xs 

因此，我們還定義了一個none函數，該函數檢查給定列表中沒有元素是否滿足給定的謂詞。

或者不經過謂詞通過遞歸：

single :: (a -> Bool) -> [a] -> Bool 
single p = helper 
    where helper []  = False 
      helper (x:xs) | p x = none xs 
         | otherwise = helper xs 
      none []  = True 
      none (x:xs) = not (p x) && none xs 

上面這些功能也將立即從目前的第二項研究發現，滿足謂詞停止。如果我們使用無限列表來工作，這會非常有用。如果有第二個項目滿足約束條件，那麼函數將停止，如果沒有這樣的元素或者只有一個這樣的元素會被生成，我們將會陷入無限循環（對此我們無能爲力）。例如：

*Main> single even [1..] -- two or more elements satisfy the constraint 
False 
*Main> single even [1,3..] -- no element satisfies the constraint 
^CInterrupted. 
*Main> single even ([1,2]++[3,5..]) -- one element satisfies the constraint 
^CInterrupted. 

Answer 4

xor和foldl

最直觀的事情，我可以的事情就是剛剛折xor直通名單（異或）和你的函數f。如果您不熟悉二進制函數xor，則僅當（至多）1個參數爲True時返回True;否則False

xor :: Bool -> Bool -> Bool 
xor True b = not b 
xor False b = b 

single :: (a -> Bool) -> [a] -> Bool 
single f [] = False 
single f xs = foldl (\acc -> xor acc . f) False xs 

main = do 
    putStrLn $ show (single even [])  -- False 
    putStrLn $ show (single even [1])  -- False 
    putStrLn $ show (single even [2])  -- True 
    putStrLn $ show (single even [1,2])  -- True 
    putStrLn $ show (single even [1,2,3]) -- True 
    putStrLn $ show (single even [1,2,3,4]) -- False 

---

Xor幺

xor能很好地被編碼爲一個Monoid壽，這使其single使用foldMap更代數實現。

data Xor = Xor Bool 

instance Monoid Xor where 
    mempty      = Xor False 
    mappend (Xor True) (Xor b) = Xor (not b) 
    mappend (Xor False) (Xor b) = Xor b 

single f xs = aux $ foldMap (Xor . f) xs 
    where 
    aux (Xor b) = b 

main = do 
    putStrLn $ show (single even [])  -- False 
    putStrLn $ show (single even [1])  -- False 
    putStrLn $ show (single even [2])  -- True 
    putStrLn $ show (single even [1,2])  -- True 
    putStrLn $ show (single even [1,2,3]) -- True 
    putStrLn $ show (single even [1,2,3,4]) -- False 

---

輔助幫手

這是另一種方式，您可以用auxiliary助手去做。這其中有，它立即退出一個額外的好處（停止迭代直通列表）的答案是確定

single :: (a -> Bool) -> [a] -> Bool 
single f xs = aux False f xs 
    where 
    aux b  f []  = b 
    aux True f (x:xs) = if (f x) then False else aux True f (xs) 
    aux False f (x:xs) = aux (f x) f xs 

main = do 
    putStrLn $ show (single even [])  -- False 
    putStrLn $ show (single even [1])  -- False 
    putStrLn $ show (single even [2])  -- True 
    putStrLn $ show (single even [1,2])  -- True 
    putStrLn $ show (single even [1,2,3]) -- True 
    putStrLn $ show (single even [1,2,3,4]) -- False 

---

反饋迎了！

我是哈斯克爾的新手，但也許這些想法對你很有意思。或者，也許他們不好！如果有任何我可以做的改進答案，留下我的評論^ _^