A question about stack overflow

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

A question about stack overflow

Huazhi (Hank) Gong

Hi, all

I’m just a newbie for Haskell and functional programming world. The idea I currently read is quite different and interesting.

I have one general question about the recursively looping style. For example:

myMax [ ] = error “empty list”

myMax [x] = x

myMax [x:xs] = if x>= (myMax xs) then x else (myMax xs)

 

I just list out this kind of very simple program. However, if the list size if a big number such as 10000000, the Winhug will report that the stack is overflow.

Does it mean that the functional programming is lacking of scalability? I do know that we can manually change the stack size for it. But that’s not a good solution according to my opinion.

 

Yours, Hank


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

Re: A question about stack overflow

haskell-2
Huazhi (Hank) Gong wrote:
 > Hi, all
 >
 > I’m just a newbie for Haskell and functional programming world. The idea
 > I currently read is quite different and interesting.
 >
 > I have one general question about the recursively looping style. For
 > example:
 >
 > myMax [ ] = error “empty list”
 >
 > myMax [x] = x
 >
 > myMax [x:xs] = if x>= (myMax xs) then x else (myMax xs)
 >
 >
 >
 > I just list out this kind of very simple program. However, if the list
 > size if a big number such as 10000000, the Winhug will report that the
 > stack is overflow.
 >
 > Does it mean that the functional programming is lacking of scalability?
 > I do know that we can manually change the stack size for it. But that’s
 > not a good solution according to my opinion.
 >
 >
 >
 > Yours, Hank
 >

The function is not "tail recursive"

Think about unfolding the recursion:

mymax [1,2,3,4] =
   if 1 >= (if 2 >= (if 3 >= (4)
                       then 3 else (4))
              then 2 else (<above>))
     then 1 else (<above>)

If 4 is a long list, then the chain of "if" statements gets larger than size of
the stack that the runtime will allow.  The definition you have looks like a
"right fold" where compare the head to the function applies to the remaining
list and what you need is a "left fold" where you process the list so far then
operate on the next element.

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

Re: A question about stack overflow

Donald Bruce Stewart
In reply to this post by Huazhi (Hank) Gong
hankgong:

>
>    Hi, all
>
>    I'm just a newbie for Haskell and functional programming
>    world. The idea I currently read is quite different and
>    interesting.
>
>    I have one general question about the recursively looping
>    style. For example:
>
>    myMax [ ] = error "empty list"
>
>    myMax [x] = x
>
>    myMax [x:xs] = if x>= (myMax xs) then x else (myMax xs)
>
>
>    I just list out this kind of very simple program. However,
>    if the list size if a big number such as 10000000, the
>    Does it mean that the functional programming is lacking of
>    scalability? I do know that we can manually change the stack
>    size for it. But that's not a good solution according to my
>    opinion.
>

No, your code is just really inefficient (think about how many times its
traversing the list). Try rewriting it as a simple accumulating pass over the
list, carrying the largest element you've seen so far.

    mymax []     = undefined
    mymax (x:xs) = f x xs
        where
          f x [] = x
          f x (y:ys) | y > x     = f y ys
                     | otherwise = f x ys

However, 'f' is just a foldl inlined:

    import Data.List
    mymax []     = undefined
    mymax (x:xs) = foldl' (\a b -> if b > a then b else a) x xs

And the lambda is just 'max':

    import Data.List
    mymax []     = undefined
    mymax (x:xs) = foldl' max x xs

Now, we already check for the empty list, so avoid checking again:

    import Data.List
    mymax [] = undefined
    mymax xs = foldl1' max xs

And that'll do.

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

Re: A question about stack overflow

Neil Mitchell
Hi,

>   mymax []     = undefined
>   mymax (x:xs) = f x xs
>       where
>         f x [] = x
>         f x (y:ys) | y > x     = f y ys
>                    | otherwise = f x ys

Or if you don't want to go for a fold next, in a style more similar to
the original:

maximum [] = undefined
maximum [x] = x
maximum (a:b:xs) = maximum (max a b : xs)

Thanks

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

Re: A question about stack overflow

Udo Stenzel
Neil Mitchell wrote:
> Or if you don't want to go for a fold next, in a style more similar to
> the original:
>
> maximum [] = undefined
> maximum [x] = x
> maximum (a:b:xs) = maximum (max a b : xs)

It even reproduces the stack overflow, though for a different reason.
Better write it this way:

maximum [] = undefined
maximum [x] = x
maximum (a:b:xs) = let m = max a b in m `seq` maximum (m : xs)


Udo.
--
"The condition of man is already close to satiety and arrogance, and
there is danger of destruction of everything in existence."
        -- a Brahmin to Onesicritus, 327 BC,
           reported in Strabo's Geography

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

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: A question about stack overflow

Huazhi (Hank) Gong
In reply to this post by haskell-2
Thank you very much for introducing tail recursion.
It's my first time to hear this. :)
However, I'm wondering whether every loop structure from C like language can
be translated to this kind of tail recursion?

Yours, Hank


-----Original Message-----
From: Chris Kuklewicz [mailto:[hidden email]]
Sent: Tuesday, June 27, 2006 5:34 PM
To: Huazhi (Hank) Gong
Cc: [hidden email]
Subject: Re: [Haskell-cafe] A question about stack overflow

Huazhi (Hank) Gong wrote:
 > Hi, all
 >
 > I'm just a newbie for Haskell and functional programming world. The idea
 > I currently read is quite different and interesting.
 >
 > I have one general question about the recursively looping style. For
 > example:
 >
 > myMax [ ] = error "empty list"
 >
 > myMax [x] = x
 >
 > myMax [x:xs] = if x>= (myMax xs) then x else (myMax xs)
 >
 >
 >
 > I just list out this kind of very simple program. However, if the list
 > size if a big number such as 10000000, the Winhug will report that the
 > stack is overflow.
 >
 > Does it mean that the functional programming is lacking of scalability?
 > I do know that we can manually change the stack size for it. But that's
 > not a good solution according to my opinion.
 >
 >
 >
 > Yours, Hank
 >

The function is not "tail recursive"

Think about unfolding the recursion:

mymax [1,2,3,4] =
   if 1 >= (if 2 >= (if 3 >= (4)
                       then 3 else (4))
              then 2 else (<above>))
     then 1 else (<above>)

If 4 is a long list, then the chain of "if" statements gets larger than size
of
the stack that the runtime will allow.  The definition you have looks like a

"right fold" where compare the head to the function applies to the remaining

list and what you need is a "left fold" where you process the list so far
then
operate on the next element.

--
Chris



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

RE: A question about stack overflow

voigt.16734551
In reply to this post by Huazhi (Hank) Gong
--- Huazhi (Hank) Gong" <[hidden email] wrote:
> Thank you very much
for introducing tail recursion.
> It's my first time to hear this. :)
>
However, I'm wondering whether every loop structure from C like language can

> be translated to this kind of tail recursion?

Yes, as discovered by
John McCarthy almost 50 years ago in "Recursive functions of symbolic expressions
and their computation by machine. Communications of the ACM, 3:184-195, 1960".


Ciao,
Janis Voigtlaender.

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

Re: A question about stack overflow

ihope
In reply to this post by Udo Stenzel
On 6/27/06, Udo Stenzel <[hidden email]> wrote:
> Neil Mitchell wrote:
> > Or if you don't want to go for a fold next, in a style more similar to
> > the original:
> >
> > maximum [] = undefined
> > maximum [x] = x
> > maximum (a:b:xs) = maximum (max a b : xs)
>
> It even reproduces the stack overflow, though for a different reason.

How about this:

maximum (a:b:xs) = maximum ((: xs) $! max a b)

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