haskell中「all」的表現

Question

我幾乎沒有haskell的知識，並試圖解決一些Project Euler問題。 在解決Number 5我寫了這個解決方案（對於1..10）

--Check if n can be divided by 1..max 
canDivAll :: Integer -> Integer -> Bool 
canDivAll max n = all (\x -> n `mod` x == 0) [1..max] 

main = print $ head $ filter (canDivAll 10) [1..] 

現在我發現，那all實現這樣的：

all p   = and . map p 

不這意味着，條件是檢查每個元素？打破條件的第一個假結果不是很快嗎？這會使上面的代碼更快地執行。

感謝

Answer 1

and本身是短路，因爲這兩個map和all評價是懶惰的，你只會得到一樣多的元素需要 - 沒有更多。

您可以驗證一個GHCi會話：

Prelude Debug.Trace> and [(trace "first" True), (trace "second" True)] 
first 
second 
True 
Prelude Debug.Trace> and [(trace "first" False), (trace "second" False)] 
first 
False 

Answer 2

你假設and不短路。 and將在其看到的第一個false結果上停止執行，因此它可能會像所期望的那樣「快速」。

Answer 3

map在執行and之前未對其所有參數進行評估。並且and被短路。

請注意，在GHC all沒有像這樣定義。

-- | Applied to a predicate and a list, 'all' determines if all elements 
-- of the list satisfy the predicate. 
all      :: (a -> Bool) -> [a] -> Bool 
#ifdef USE_REPORT_PRELUDE 
all p     = and . map p 
#else 
all _ []  = True 
all p (x:xs) = p x && all p xs 
{-# RULES 
"all/build"  forall p (g::forall b.(a->b->b)->b->b) . 
       all p (build g) = g ((&&) . p) True 
#-} 
#endif 

我們看到all p (x:xs) = p x && all p xs，所以每當p x是假的，評估將停止。

此外，還有一個簡化規則all/build，從而有效地將您的all p [1..max]成一個簡單的故障快速環路*，所以我不認爲你可以提高從修改all得多。

---

^{*。簡化的代碼應該是這樣的：}

eftIntFB c n x0 y | x0 ># y = n   
        | otherwise = go x0 
       where 
        go x = I# x `c` if x ==# y then n else go (x +# 1#) 

eftIntFB ((&&) . p) True 1# max# 

Answer 4

這是融合優化的一個好的方案，因爲所有的迴路表示爲熔組合程序。因此，您可以使用例如Data.Vector，並獲得比列表更好的性能。

從N = 20，用列表作爲你的程序：

• 52.484s

此外，使用rem代替mod。

• 15。712s

凡列表功能變得向量運算：

import qualified Data.Vector.Unboxed as V 

canDivAll :: Int -> Int -> Bool 
canDivAll max n = V.all (\x -> n `rem` x == 0) (V.enumFromN 1 max) 

main = print . V.head $ V.filter (canDivAll 20) $ V.unfoldr (\a -> Just (a, a+1)) 1