[Haskell-cafe] how to Enumerate without lists?

[David Feuer]

I don't really understand your purpose. There are many ways to write code
that GHC is good at optimizing, but there are far fewer ways to write code
that will compile to non-allocating loops without optimization. Heck,
without the worker-wrapper transformation demand analysis enables, you
can't even get a non-allocating counter without unboxing by hand and using
primops for arithmetic.

On Tue, Sep 4, 2018, 1:00 PM Johannes Waldmann <
johannes.waldmann at htwk-leipzig.de> wrote:

> Dear Cafe (again),
>
>
> I was trying to write
>
>   sum $ map (^ 2) $ [ 1 :: Int .. 10^8 ]
>
> in a list-free style
>
>    getSum $ foldMap  (Sum . (^ 2)) $ [ 1 :: Int .. 10^8 ]
>
> This avoids building an intermediate list (of squares)
> but it will allocate, since  foldMap  uses  foldr
> (by default, and it's not overridden for lists)
>
> The conclusion would be: not to use lists at all.
> Which will be the point of my talk anyway.
>
>
> But here, we get a list from  enumFromTo. Can we avoid that?
>
> Let's try: we just reify  enumFromTo
>
>   data Enumerator a = Enumerator {from :: a, to :: a}
>
> we have this for decades, it is called  (a,a)  in Data.Ix,
> and then
>
>   instance Foldable Enumerator where ...
>
> Oh no,  foldMap  (and others) would need an Enum constraint!
>
>
> - J
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.


On Sep 4, 2018 1:00 PM, "Johannes Waldmann" <
johannes.waldmann at htwk-leipzig.de> wrote:

Dear Cafe (again),


I was trying to write

  sum $ map (^ 2) $ [ 1 :: Int .. 10^8 ]

in a list-free style

   getSum $ foldMap  (Sum . (^ 2)) $ [ 1 :: Int .. 10^8 ]

This avoids building an intermediate list (of squares)
but it will allocate, since  foldMap  uses  foldr
(by default, and it's not overridden for lists)

The conclusion would be: not to use lists at all.
Which will be the point of my talk anyway.


But here, we get a list from  enumFromTo. Can we avoid that?

Let's try: we just reify  enumFromTo

  data Enumerator a = Enumerator {from :: a, to :: a}

we have this for decades, it is called  (a,a)  in Data.Ix,
and then

  instance Foldable Enumerator where ...

Oh no,  foldMap  (and others) would need an Enum constraint!


- J

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180904/933c73e2/attachment.html>