a minor bug (memory leak) in ListLike package

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

a minor bug (memory leak) in ListLike package

bob zhang
Hi, John, there is a space leak problem in ListLike typeclass,
in the method genericLength
calclen !accum cl =
calclen accum cl =
--- thank you for your nice library
btw, is there any way to derive ListLike interface automatically?
for such type :
newtype List a = List {[a]}
Best,bob

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

Ivan Lazar Miljenovic
On 24 August 2011 11:10, bob zhang <[hidden email]> wrote:
> Hi, John, there is a space leak problem in ListLike typeclass,
> in the method genericLength
> calclen !accum cl =
> calclen accum cl =

I _think_ this may cause problems with some data types (e.g.
http://hackage.haskell.org/packages/archive/numbers/2009.8.9/doc/html/Data-Number-Natural.html
) that require the extra laziness (that is, you can do things like ` 3
< genericLength [1..] ' and have it return True).

> --- thank you for your nice library
> btw, is there any way to derive ListLike interface automatically?
> for such type :
> newtype List a = List {[a]}

GeneralizedNewtypeDeriving can do that.

--
Ivan Lazar Miljenovic
[hidden email]
IvanMiljenovic.wordpress.com

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

bob zhang
Hi, 
  I think 3 < genericLength [1..] should fail, that laziness is not we want. 
  I can not derive ListLike  instance using GHC extensions, can you provide a working example?
  Thanks
On Tue, Aug 23, 2011 at 9:47 PM, Ivan Lazar Miljenovic <[hidden email]> wrote:
On 24 August 2011 11:10, bob zhang <[hidden email]> wrote:
> Hi, John, there is a space leak problem in ListLike typeclass,
> in the method genericLength
> calclen !accum cl =
> calclen accum cl =

I _think_ this may cause problems with some data types (e.g.
http://hackage.haskell.org/packages/archive/numbers/2009.8.9/doc/html/Data-Number-Natural.html
) that require the extra laziness (that is, you can do things like ` 3
< genericLength [1..] ' and have it return True).

> --- thank you for your nice library
> btw, is there any way to derive ListLike interface automatically?
> for such type :
> newtype List a = List {[a]}

GeneralizedNewtypeDeriving can do that.

--
Ivan Lazar Miljenovic
[hidden email]
IvanMiljenovic.wordpress.com



--
Best, bob

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

Ivan Lazar Miljenovic
On 24 August 2011 13:17, bob zhang <[hidden email]> wrote:
> Hi,
>   I think 3 < genericLength [1..] should fail, that laziness is not we
> want.

It might not be what _you_ want, but it might be what others want.  If
you're concerned with efficiency, then wouldn't you use length rather
than genericLength?

>   I can not derive ListLike  instance using GHC extensions, can you provide
> a working example?

I take it back, it doesn't seem to be possible due to the design of
ListLilke.  You need to define the instance explicitly (there are only
four functions you have to define, but for performance reasons you
probably want to re-define all of them).

--
Ivan Lazar Miljenovic
[hidden email]
IvanMiljenovic.wordpress.com

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

bob zhang
于 11-8-23 下午11:37, Ivan Lazar Miljenovic 写道:
> It might not be what_you_  want, but it might be what others want.  If
> you're concerned with efficiency, then wouldn't you use length rather
> than genericLength?
>
length is identical to genericLength in ListLike except type signature.
but still,
import Data.Number
import Data.List
import qualified Data.ListLike as L
(3 :: Natural) < genericLength [1..] (work)
(3 :: Natural) < L.genericLength [1..] (non-terminating)

If you want laziness, L.genericLength should be defined like this
L.genericLength [] = 0
L.genericLength (_:l) = 1 + L.genericLength l
the genericLength used in ListLike package used tail recursion while
non-strict.
and also, a strict length is still needed (currently, length is
identical to genericLength)

Thank you
bob

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

wren ng thornton
In reply to this post by bob zhang
On 8/23/11 11:17 PM, bob zhang wrote:
> I think 3 < genericLength [1..] should fail, that laziness is not we want.

And it'd be more efficient to use

     lengthBound 3 (<) [1..]

where lengthBound is from list-extras:Data.List.Extras.LazyLength. The
efficiency comes from using Int rather than a chain of pointers for lazy
Peano numbers.

--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

Sebastian Fischer-2
In reply to this post by Ivan Lazar Miljenovic
On Wed, Aug 24, 2011 at 10:47 AM, Ivan Lazar Miljenovic
<[hidden email]> wrote:

> On 24 August 2011 11:10, bob zhang <[hidden email]> wrote:
>> Hi, John, there is a space leak problem in ListLike typeclass,
>> in the method genericLength
>> calclen !accum cl =
>> calclen accum cl =
>
> I _think_ this may cause problems with some data types (e.g.
> http://hackage.haskell.org/packages/archive/numbers/2009.8.9/doc/html/Data-Number-Natural.html
> ) that require the extra laziness (that is, you can do things like ` 3
> < genericLength [1..] ' and have it return True).

Does the current version support this? The use of an accumulator (that
is presumably returned after consuming the complete input) seems to
suggest that your example would diverge anyway (but I did not try).

Sebastian

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

Ivan Lazar Miljenovic
On 24 August 2011 15:54, Sebastian Fischer <[hidden email]> wrote:
>>
>> I _think_ this may cause problems with some data types (e.g.
>> http://hackage.haskell.org/packages/archive/numbers/2009.8.9/doc/html/Data-Number-Natural.html
>> ) that require the extra laziness (that is, you can do things like ` 3
>> < genericLength [1..] ' and have it return True).
>
> Does the current version support this? The use of an accumulator (that
> is presumably returned after consuming the complete input) seems to
> suggest that your example would diverge anyway (but I did not try).

I was just trying to remember some of the tricks Daniel Peebles (aka
{co}pumpkin) used to do in #haskell with Data.List.genericLength.
I've never really used ListLike, but was just trying to guess why the
default implementation was as it is.

--
Ivan Lazar Miljenovic
[hidden email]
IvanMiljenovic.wordpress.com

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

John Lato-2
In reply to this post by bob zhang
Thanks for reporting this.  I understand the problem, however I don't
want to bloat the interface even more with a bunch of strict versions
of functions.  Even so, the current implementation is definitely the
worst possible option as it has the slow performance of building
thunks without the actual benefits of laziness.

`Data.List` currently uses a fully lazy implementation, with RULEs to
specialize to a strict variant for Int and Integer accumulators.  The
same solution should work for ListLike, with the following additions:

1.  `length` be made fully strict in the accumulator
2.  `genericLength'` (strict variant) be exposed via the interface

Currently I know of no way to automatically derive listlike-instances,
however the `listlike-instances` package has instances for a few other
useful types (vectors and Text mainly).  Adding instances is
definitely a pain, so I may well try to create a Derive extension for
the next time I want to do so.

Cheers,
John

On Wed, Aug 24, 2011 at 5:17 AM, bob zhang <[hidden email]> wrote:

> 于 11-8-23 下午11:37, Ivan Lazar Miljenovic 写道:
>>
>> It might not be what_you_  want, but it might be what others want.  If
>> you're concerned with efficiency, then wouldn't you use length rather
>> than genericLength?
>>
> length is identical to genericLength in ListLike except type signature.
> but still,
> import Data.Number
> import Data.List
> import qualified Data.ListLike as L
> (3 :: Natural) < genericLength [1..] (work)
> (3 :: Natural) < L.genericLength [1..] (non-terminating)
>
> If you want laziness, L.genericLength should be defined like this
> L.genericLength [] = 0
> L.genericLength (_:l) = 1 + L.genericLength l
> the genericLength used in ListLike package used tail recursion while
> non-strict.
> and also, a strict length is still needed (currently, length is identical to
> genericLength)
>
> Thank you
> bob
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

John Lato-2
In reply to this post by Ivan Lazar Miljenovic
On Wed, Aug 24, 2011 at 7:47 AM, Ivan Lazar Miljenovic
<[hidden email]> wrote:
>
> I was just trying to remember some of the tricks Daniel Peebles (aka
> {co}pumpkin) used to do in #haskell with Data.List.genericLength.
> I've never really used ListLike, but was just trying to guess why the
> default implementation was as it is.

Unfortunately I can't answer this either (although I can make a good
guess); it's from John Goerzen's original code.  And really, any
thanks for ListLike should go to him; he did all the work.

John L.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: a minor bug (memory leak) in ListLike package

Sebastian Fischer-2
In reply to this post by Ivan Lazar Miljenovic
On Wed, Aug 24, 2011 at 3:47 PM, Ivan Lazar Miljenovic
<[hidden email]> wrote:
> I was just trying to remember some of the tricks Daniel Peebles (aka
> {co}pumpkin) used to do in #haskell with Data.List.genericLength.
> I've never really used ListLike, but was just trying to guess why the
> default implementation was as it is.

Maybe he used lazy implementations of Num and Ord in combination with
a definition like

    length [] = 0
    length (_:xs) = 1 + length xs

But as John observed, the accumulating version of length does not
provide such laziness and the accumulator might as well be made
strict.

Sebastian

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe