2017-05-31 19 views
-1

要求:寫入函數單個 - 測試列表中是否只有一個元素滿足給定條件。Haskell - 將高階函數轉換爲遞歸函數

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

我寫了這個功能:

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

問題:什麼是最簡單的(正確)的方式轉換成上述功能於一體的遞歸函數,而不使用「高階函數」?

+1

這種轉換的原因是什麼? – freestyle

回答

0

如何使用輔助功能

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 
+1

也許是一個奇怪的評論,但不是你的功能遭受同樣的影響?如果有一個元素滿足謂詞,那麼最後一個參數在某個點將是'1',因此'True'將被返回。例如'single even [2,3,4]'會返回'True'。 –

+0

@WillemVanOnsem哈哈,你是對的。我忘了這句話是怎麼說的,「把你的鄰居的眼睛放在一邊」或其他什麼東西。無論如何,謝謝 - 糾正。 –

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 
+0

我比我更喜歡那個答案。在我看來,代碼更容易理解。 – Krom

0

我們可以用一個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. 
+0

哎呀,我誤解了這個問題,謝謝。將編輯。 –

0

xorfoldl

最直觀的事情,我可以的事情就是剛剛折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 

反饋迎了!

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

+0

那麼在前兩個版本中甚至會有'單一的[1,2,3,4,5,6]'? –

+0

@AlexeyRomanov,你完全教我 - 我忽略了!我現在正在重新思考'xor'方法。這裏有其他的輸入嗎? – naomik

+0

優秀的解釋。 這樣的答案對我來說更有用,那麼十篇文章。 我特別喜歡輔助函數的答案,因爲它對其他問題的廣泛含義。 – Atir