6 ms·

Won't product [1..n] lead to a space leak?

RubenSandwich 11y ago
It could; depending on the size of n.
pherq 11y ago
With a decent compiler (I think GHC is up to the job, but I've not checked), stream fusion should ensure that the intermediate list never actually exists.
jfoutz 11y ago
the prelude implementation is foldMap on list. as i understand it, a cons cell will be created with the head pointer pointing at 1, and the tail at a lazily evaluated thunk. + tries to evaluate, which creates a cons cell pointing at 2, and a thunk. 1 and 2 are added. so we've got two cells hanging around, but no references to the first one, so the gc can grab it whenever. it'll just kind of chug through the list. it's kinda wasteful to keep making the cells, but it's easy to read. shrug however ghc is very smart. it might be clever enough to optimize away the cells. it might also do immediate ints, rather than pointers to '1', i'm pretty hazy on when there's an int, and when there's a bigint.
- platz 11y ago
  here is the output of main = print $ product [1..100] ghc-core-html --ghc-option=-ddump-simpl --ghc-option=-dsuppress-all fact.hs https://rawgit.com/jonschoning/c4ad2129aa7d258e65f9/raw/f8edf61aaba6a7a28dc60bb935738d648e53335c/fact.html https://rawgit.com/jonschoning/c4ad2129aa7d258e65f9/raw/f8ed... you can see main_go (plusInteger x_a3Sq main4) (timesInteger eta_B1 x_a3Sq); where it compiles to a recursive loop with an accumulator typicall the [1..100] gets compiled to (enumFromTo 1 100) and it can be desugared further.. so, yeah, foldmap compiles to foldr which may compile down further
  - PeCaN 11y ago
    foldr usually gets deforested in GHC, so the intermediate list probably doesn't exist. GHC rewrites most of the common built-in functions to eliminate intermediate trees and lists. You can see a list https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_guide/rewrite-rules.html https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_gui... (section 7.14.4; ctrl-f "good producer").
    - deleted 11y ago
      [deleted]
bbcbasic 11y ago
[1..n] is not an array but a lazy-generated linked list. So you'd get a space leak only if it loaded the entire list in memory, or it kept all of the intermediate calculations (called thunks) in memory. The question is does it do that, or can it use tail-call optimisation, which would effectively compile to a loop with an accumulating variable, discarding the thunks I admit now I am stuck looking at http://hackage.haskell.org/package/base-4.8.2.0/docs/src/Data.Foldable.html#product http://hackage.haskell.org/package/base-4.8.2.0/docs/src/Dat... as it uses foldMap which I am not used to. According to https://wiki.haskell.org/Fold https://wiki.haskell.org/Fold foldl can make use of TCO. When I get some time I will see if I can produce the thunks as I am very interested i this!
- platz 11y ago
  there are various ways to view exactly what ghc produces (i have one in my comment below)

It could; depending on the size of n.

pherq 11y ago

With a decent compiler (I think GHC is up to the job, but I've not checked), stream fusion should ensure that the intermediate list never actually exists.

jfoutz 11y ago

the prelude implementation is foldMap on list. as i understand it, a cons cell will be created with the head pointer pointing at 1, and the tail at a lazily evaluated thunk. + tries to evaluate, which creates a cons cell pointing at 2, and a thunk. 1 and 2 are added. so we've got two cells hanging around, but no references to the first one, so the gc can grab it whenever. it'll just kind of chug through the list. it's kinda wasteful to keep making the cells, but it's easy to read. shrug however ghc is very smart. it might be clever enough to optimize away the cells. it might also do immediate ints, rather than pointers to '1', i'm pretty hazy on when there's an int, and when there's a bigint.

platz 11y ago
here is the output of main = print $ product [1..100] ghc-core-html --ghc-option=-ddump-simpl --ghc-option=-dsuppress-all fact.hs https://rawgit.com/jonschoning/c4ad2129aa7d258e65f9/raw/f8edf61aaba6a7a28dc60bb935738d648e53335c/fact.html https://rawgit.com/jonschoning/c4ad2129aa7d258e65f9/raw/f8ed... you can see main_go (plusInteger x_a3Sq main4) (timesInteger eta_B1 x_a3Sq); where it compiles to a recursive loop with an accumulator typicall the [1..100] gets compiled to (enumFromTo 1 100) and it can be desugared further.. so, yeah, foldmap compiles to foldr which may compile down further
- PeCaN 11y ago
  foldr usually gets deforested in GHC, so the intermediate list probably doesn't exist. GHC rewrites most of the common built-in functions to eliminate intermediate trees and lists. You can see a list https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_guide/rewrite-rules.html https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_gui... (section 7.14.4; ctrl-f "good producer").
  - deleted 11y ago
    [deleted]

bbcbasic 11y ago

[1..n] is not an array but a lazy-generated linked list. So you'd get a space leak only if it loaded the entire list in memory, or it kept all of the intermediate calculations (called thunks) in memory. The question is does it do that, or can it use tail-call optimisation, which would effectively compile to a loop with an accumulating variable, discarding the thunks I admit now I am stuck looking at http://hackage.haskell.org/package/base-4.8.2.0/docs/src/Data.Foldable.html#product http://hackage.haskell.org/package/base-4.8.2.0/docs/src/Dat... as it uses foldMap which I am not used to. According to https://wiki.haskell.org/Fold https://wiki.haskell.org/Fold foldl can make use of TCO. When I get some time I will see if I can produce the thunks as I am very interested i this!

platz 11y ago
there are various ways to view exactly what ghc produces (i have one in my comment below)