Geek asks and answers

Why directly imported functions in GHC are very different from functions that I write with source code copied from GHC libraries

module Has (r,p,s) where

import Prelude ((==),Bool(..),otherwise,(||),Eq)
import qualified Data.List as L

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

problem1: This one is filtercopied from the library GHC, but why is it consuming more and more memory as opposed to directly imported filter, which consumes a constant amount of memory.

elem :: (Eq a) => a -> [a] -> Bool
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

problem2: This one is filtercopied from the library GHC, but why does it consume more and more memory as directly used elem, which also consumes more and more memory as opposed to directly imported filter.

r = L.filter (==1000000000000) [0..]
p = filter (==1000000000000) [0..]
s = 1000000000000 `elem` [0..]

GHC version: 7.4.2 OS: Ubuntu 12.10 Compiled with -O2 for optimization

filter elem, p = filter (==1000000000000) [0..], s = 1000000000000 `elem` [0..] [0..] . p, s . r, filter, .

, GHC , , GHC Libraries. , GHC - ?

: , , " , ". , , GHC.

.

+5
1

ghci filter elem. ( filter GHC.List .)

() ​​ghc-7.4.2, -O2 (-ddump-simpl). r, GHC.List.filter:

Has.r1
  :: GHC.Integer.Type.Integer
     -> [GHC.Integer.Type.Integer] -> [GHC.Integer.Type.Integer]
[GblId,
 Arity=2,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [0 0] 60 30}]
Has.r1 =
  \ (x_awu :: GHC.Integer.Type.Integer)
    (r2_awv :: [GHC.Integer.Type.Integer]) ->
    case GHC.Integer.Type.eqInteger x_awu Has.p5 of _ {
      GHC.Types.False -> r2_awv;
      GHC.Types.True ->
        GHC.Types.: @ GHC.Integer.Type.Integer x_awu r2_awv
    }

Has.r :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 40 0}]
Has.r =
  GHC.Enum.enumDeltaIntegerFB
    @ [GHC.Integer.Type.Integer] Has.r1 Has.p3 Has.p2

Has.p3 - 0 :: Integer, Has.p2 - 1 :: Integer. ( filter enumDeltaInteger) ( )

r = go fun 0 1
  where
    go foo x d = x `seq` (x `foo` (go foo (x+d) d))

fun n list
    | n == 1000000000000 = n : list
    | otherwise          = list

, , , fun , , filter ed , .

p, , ()

Has.p1 :: [GHC.Integer.Type.Integer]
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p1 = GHC.Enum.enumDeltaInteger Has.p3 Has.p2

Has.p :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p = Has.filter @ GHC.Integer.Type.Integer Has.p4 Has.p1

CAF [0 .. ] (Has.p1) Has.filter (== 1000000000000) .

, - , .

( ), , - , . , , ghci [0 .. ] p s ( [0 .. ], ), -hT ( s, . ghci +RTS -M300M -hT -RTS, , 300M, ghci ):

enter image description here

, ghci . Has.filter , , , .

, ghci, [0 .. ], .

+1

More articles:


All Articles