Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Avoiding stack space overflow (Hans Georg Schaathun)
2. Re: Avoiding stack space overflow (David McBride)
3. Re: Avoiding stack space overflow (Hans Georg Schaathun)
4. Re: Avoiding stack space overflow (Bob Ippolito)
5. Re: Avoiding stack space overflow (David McBride)
6. Fixed Point function (Animesh Saxena)
7. Re: Fixed Point function (Karl Voelker)
----------------------------------------------------------------------
Message: 1
Date: Mon, 26 Jan 2015 13:19:26 +0100
From: Hans Georg Schaathun <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Avoiding stack space overflow
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hi,
can someone give some hints on how to get around a stack space
overflow?
My problem is with the training function for a neural network:
trainNetwork :: Double -> Samples -> Int -> Network -> Network
trainNetwork _ _ 0 n = n
trainNetwork eta samples c n = trainNetwork eta samples (c-1) $!
epoch eta n samples
epoch :: Double -> Network -> Samples -> Network
So trainNetwork runs epoch c times, each time taking a Network
in and modifying the Network as output. Clearly, space complexity
can be made constant in c, but I get stack overflow if and only
if c is too large.
As you can see, I have tried to make the epoch evaluation strict
($!). I have also tried bang patterns on the input parameter n,
and I have tried rewriting with foldr/foldl/foldl', and I have
tried switchin the inner and outer calls (epoch vs. trainNetwork),
all to no avail.
I reckon this loop like pattern should be fairly common ...
does it have a common solution too?
TIA
--
:-- Hans Georg
------------------------------
Message: 2
Date: Mon, 26 Jan 2015 09:55:03 -0500
From: David McBride <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Avoiding stack space overflow
Message-ID:
<CAN+Tr436BnCAQtBjfidAK3PNhviE742dTqhd5=7yruy_w4m...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I don't think the problem is with trainNetwork, but rather epoch. You
might try adjusting your network datatype and sub datatypes in the manner
of data Network = Network !Int !Int until you narrow down which piece is
causing the problem.
On Mon, Jan 26, 2015 at 7:19 AM, Hans Georg Schaathun <
[email protected]> wrote:
> Hi,
>
> can someone give some hints on how to get around a stack space
> overflow?
>
> My problem is with the training function for a neural network:
>
> trainNetwork :: Double -> Samples -> Int -> Network -> Network
> trainNetwork _ _ 0 n = n
> trainNetwork eta samples c n = trainNetwork eta samples (c-1) $!
> epoch eta n samples
> epoch :: Double -> Network -> Samples -> Network
>
> So trainNetwork runs epoch c times, each time taking a Network
> in and modifying the Network as output. Clearly, space complexity
> can be made constant in c, but I get stack overflow if and only
> if c is too large.
>
> As you can see, I have tried to make the epoch evaluation strict
> ($!). I have also tried bang patterns on the input parameter n,
> and I have tried rewriting with foldr/foldl/foldl', and I have
> tried switchin the inner and outer calls (epoch vs. trainNetwork),
> all to no avail.
>
> I reckon this loop like pattern should be fairly common ...
> does it have a common solution too?
>
> TIA
> --
> :-- Hans Georg
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150126/7a0f0b33/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 26 Jan 2015 17:45:17 +0100
From: Hans Georg Schaathun <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Avoiding stack space overflow
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Mon, Jan 26, 2015 at 09:55:03AM -0500, David McBride wrote:
> I don't think the problem is with trainNetwork, but rather epoch. You
> might try adjusting your network datatype and sub datatypes in the manner
> of data Network = Network !Int !Int until you narrow down which piece is
> causing the problem.
It turns out that you are absolutely right.
A number of randomly inserted bang patterns got rid of the overflow.
Thanks a lot for the idea..
I feel even more clueless than I used too, but I have at least a way
to proceed.
--
:-- Hans Georg
------------------------------
Message: 4
Date: Mon, 26 Jan 2015 08:58:37 -0800
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Avoiding stack space overflow
Message-ID:
<CACwMPm_CzD3=WkSQAcRj92MLFy=oYzexqH=OsT=hn627=kq...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Here are my go-to resources for Haskell's evaluation:
http://chimera.labs.oreilly.com/books/1230000000929/ch02.html#sec_par-eval-whnf
https://hackhands.com/lazy-evaluation-works-haskell/
On Mon, Jan 26, 2015 at 8:45 AM, Hans Georg Schaathun <
[email protected]> wrote:
> On Mon, Jan 26, 2015 at 09:55:03AM -0500, David McBride wrote:
> > I don't think the problem is with trainNetwork, but rather epoch. You
> > might try adjusting your network datatype and sub datatypes in the manner
> > of data Network = Network !Int !Int until you narrow down which piece is
> > causing the problem.
>
> It turns out that you are absolutely right.
> A number of randomly inserted bang patterns got rid of the overflow.
> Thanks a lot for the idea..
>
> I feel even more clueless than I used too, but I have at least a way
> to proceed.
>
> --
> :-- Hans Georg
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150126/e15b045d/attachment-0001.html>
------------------------------
Message: 5
Date: Mon, 26 Jan 2015 12:20:56 -0500
From: David McBride <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Avoiding stack space overflow
Message-ID:
<can+tr40krpj9chwaft+uh+styfeqqdbs8dr4vyx9ltaachk...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
We're all guilty of throwing around the bang patterns to fix performance
problems, and that is a reasonable solution. But if you wish to understand
the problem, see if you can narrow down much of your leak to a specific
field within one of your types, then you can look at epoch and sub
functions and identify why that particular field is not being fully
evaluated by the time you have returned from epoch. Hopefully it will be
obvious in hindsight and you will not run into this next time you have
similar code. GHCI's debugger may also give you a nice way to determine
where your problem lies.
On Mon, Jan 26, 2015 at 11:45 AM, Hans Georg Schaathun <
[email protected]> wrote:
> On Mon, Jan 26, 2015 at 09:55:03AM -0500, David McBride wrote:
> > I don't think the problem is with trainNetwork, but rather epoch. You
> > might try adjusting your network datatype and sub datatypes in the manner
> > of data Network = Network !Int !Int until you narrow down which piece is
> > causing the problem.
>
> It turns out that you are absolutely right.
> A number of randomly inserted bang patterns got rid of the overflow.
> Thanks a lot for the idea..
>
> I feel even more clueless than I used too, but I have at least a way
> to proceed.
>
> --
> :-- Hans Georg
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150126/5cdcbcfa/attachment-0001.html>
------------------------------
Message: 6
Date: Tue, 27 Jan 2015 04:43:00 +0000 (GMT)
From: Animesh Saxena <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Fixed Point function
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
I stumbled across this example as a shiny way of explaining why Lazy eval
matters....
? ? fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)
fix f = f (fix f)
With lazy eval, I get?
fact 4 = fix $ \f 4 (......)
since haskell goes outside to inside I have,
fac 4 =?$ \f 4 (......)?(fix?$ \f 4 (......))
Now the first chunk can get evaluated, but what about the rest of the
expression. The outer "f" from "fix f" function has the parameter (fix f). So
when writing "f (fix f)" apparently f got evaluated without using this
parameter. I understand that the anonymous lambda does have 4 as the param, but
somehow "f (fix f)" doesn't feel complete.?
-Animesh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150127/81d18119/attachment-0001.html>
------------------------------
Message: 7
Date: Mon, 26 Jan 2015 22:24:26 -0800
From: Karl Voelker <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Fixed Point function
Message-ID:
<1422339866.2943779.219346645.012ab...@webmail.messagingengine.com>
Content-Type: text/plain; charset="us-ascii"
On Mon, Jan 26, 2015, at 08:43 PM, Animesh Saxena wrote:
> I stumbled across this example as a shiny way of explaining why Lazy
> eval matters....
>
> fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1) fix f =
> f (fix f)
>
> With lazy eval, I get
>
> fact 4 = fix $ \f 4 (......)
Not quite. Let's go one step at a time:
fact 4 = (fix $ \f n -> if n == 0 then 1 else n * f (n - 1)) 4
Now we can bring in the definition of fix, substituting the argument to
fix for all of the occurrences of f in the definition of fix. Notice
that we can't substitute the 4 for n yet.
fact 4 = ((\f n -> if n == 0 then 1 else n * f (n - 1)) (fix $ \f n ->
if n == 0 then 1 else n * f (n - 1))) 4
I think if you are very patient and methodical about performing the
substitutions (and writing them out fully - no dot-dot-dot), then you'll
figure out how it all works.
-Karl
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20150126/1a242721/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 79, Issue 30
*****************************************
