Разве это не двойной обход?

Question

В «советы по программированию» секции haskell wiki, я нашел этот пример:

count :: (a -> Bool) -> [a] -> Int 
count p = length . filter p 

Это было сказано, чтобы быть лучшей альтернативой

count :: (a -> Bool) -> [a] -> Int 
count _ [] = 0 
count p (x:xs) 
    | p x  = 1 + count p xs 
    | otherwise =  count p xs 

Что, с точки зрения читаемости, я полностью согласен с.

Однако, разве это не двойной обход, а потому на самом деле хуже, чем функция явного рекурсии? Разве ленивость в GHC означает, что это эквивалентно одному движению после оптимизации? Какая реализация выполняется быстрее и почему?

Answer 1

Итак, чтобы увидеть, что оптимизатор на самом деле, давайте look at the core:

% ghc -O2 -ddump-simpl Temp.hs 
[1 of 1] Compiling Temp    (Temp.hs, Temp.o) 

==================== Tidy Core ==================== 
Result size of Tidy Core = {terms: 29, types: 26, coercions: 0} 

Temp.count 
    :: forall a_arN. 
    (a_arN -> GHC.Types.Bool) -> [a_arN] -> GHC.Types.Int 
[GblId, 
Arity=2, 
Caf=NoCafRefs, 
Str=DmdType <L,C(U)><S,1*U>, 
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True, 
     ConLike=True, WorkFree=True, Expandable=True, 
     Guidance=IF_ARGS [60 0] 191 0}] 
Temp.count = 
    \ (@ a_aMA) 
    (p_arV :: a_aMA -> GHC.Types.Bool) 
    (eta_B1 :: [a_aMA]) -> 
    letrec { 
     go_aNr [Occ=LoopBreaker] 
     :: [a_aMA] -> GHC.Prim.Int# -> GHC.Types.Int 
     [LclId, Arity=1, Str=DmdType <S,1*U>] 
     go_aNr = 
     \ (ds_aNs :: [a_aMA]) -> 
      case ds_aNs of _ [Occ=Dead] { 
      [] -> GHC.Types.I#; 
      : y_aNx ys_aNy -> 
       case p_arV y_aNx of _ [Occ=Dead] { 
       GHC.Types.False -> go_aNr ys_aNy; 
       GHC.Types.True -> 
        let { 
        g_a10B [Dmd=<L,C(U)>] :: GHC.Prim.Int# -> GHC.Types.Int 
        [LclId, Str=DmdType] 
        g_a10B = go_aNr ys_aNy } in 
        \ (x_a10C :: GHC.Prim.Int#) -> g_a10B (GHC.Prim.+# x_a10C 1) 
       } 
      }; } in 
    go_aNr eta_B1 0 

Очистка это немного:

Temp.count :: forall aType. (aType -> Bool) -> [aType] -> Int 
Temp.count = \(@ aType) (p :: aType -> Bool) (as :: [aType]) -> 
    letrec { 
    go :: [aType] -> GHC.Prim.Int# -> Int 
    go = \(xs :: [aType]) -> 
     case xs of _ { 
     [] -> I#; -- constructor to make a GHC.Prim.Int# into an Int 
     : y ys -> 
      case p y of _ { 
      False -> go ys; 
      True -> 
       let { 
       go' :: GHC.Prim.Int# -> Int 
       go' = go ys 
       } in \(x :: GHC.Prim.Int#) -> go' (GHC.Prim.+# x 1) 
      } 
     }; 
    } in go as 0 

Поскольку мы действуем на Unboxed типа GHC.Prim.Int#, all the additions are strict, так мы имеем только один цикл данных.

Answer 2

В любом случае, вам необходимо выполнить одну или две операции для каждого элемента. Необходимым является проверка предиката. Второе добавление 1 зависит от результата предиката.

Итак, если вы не учитываете эффекты кеша и т. Д., Оба случая генерируют равное количество операций.

Картинка, которую вы получаете, состоит в том, что в первом случае есть два отдельных прохода, один из которых собирает элементы и один их подсчитывает. Учитывая, что список больше, чем может обрабатывать кеш, это замедлит обработку. И это на самом деле происходит в строгом языке.

Однако лента Haskell появляется здесь. Список, генерируемый filter, оценивается (возникает) поэтапно, поскольку функция подсчета length нуждается в этом. И тогда, поскольку length использует их только для подсчета и не сохраняет ссылки на вновь созданный список, элементы немедленно освобождаются от сбора мусора. Таким образом, в любой момент времени во время вычисления используется только O(1).

Существует небольшая накладная часть для создания результирующего «отфильтрованного» списка в первой версии. Но это обычно незначительно по сравнению с кеш-эффектами, которые возникают, когда списки большие. (Для небольших списков это может иметь значение, это нужно проверить.) Кроме того, он может быть оптимизирован в зависимости от выбранного компилятора и выбранного уровня оптимизации.

Обновление. Вторая версия фактически потребляет память, как указано в одном из комментариев. Для справедливого сравнения вам нужно написать его с помощью аккумулирующего параметра и строгого аннотатора в нужном месте, потому что (я ожидаю) length уже написан таким образом.

Answer 3

Вы можете проверить, какая версия работает быстрее с profiling, например .:

module Main where 


main :: IO() 
main = print countme' 

count' :: (a -> Bool) -> [a] -> Int 
count' p = length . filter p 

count :: (a -> Bool) -> [a] -> Int 
count _ [] = 0 
count p (x:xs) 
    | p x  = 1 + count p xs 
    | otherwise =  count p xs 


list = [0..93823249] 

countme' = count' (\x -> x `mod` 15 == 0) list 
countme = count (\x -> x `mod` 15 == 0) list 

Затем запустите ghc -O2 -prof -fprof-auto -rtsopts Main.hs и ./Main +RTS -p. Он даст файл Main.prof. Затем замените основную функцию на использование countme и сравните результаты. Месторождение:

• 4.12s неявной версии
• 6.34s для явной версии

Если вы отключите оптимизацию, то неявный один еще немного (но не намного) быстрее.

Помимо слияния и лености, которые уже были объяснены другими, я полагаю, что другая причина может заключаться в том, что length и filter являются функциями Prelude и могут быть оптимизированы компилятором.