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 

---

反馈迎了！

我是哈斯克尔的新手，但也许这些想法对你很有意思。或者，也许他们不好！如果有任何我可以做的改进答案，留下我的评论^ _^