Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Merge Sort Stack Overflow (Florian Lammel)
2. Fwd: Merge Sort Stack Overflow (Florian Lammel)
3. Re: Merge Sort Stack Overflow (Oscar Benjamin)
4. Re: Merge Sort Stack Overflow (Brandon Allbery)
5. Re: Merge Sort Stack Overflow (Oscar Benjamin)
6. Re: Merge Sort Stack Overflow (Chadda? Fouch?)
----------------------------------------------------------------------
Message: 1
Date: Mon, 16 Sep 2013 19:35:24 +0200
From: Florian Lammel <m...@florianlammel.com>
To: Beginners@haskell.org
Subject: [Haskell-beginners] Merge Sort Stack Overflow
Message-ID:
<CAAnRmS081F812_H7c__ipBDmVNS=n02rrmtkzfebsz4vaku...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Hi,
I've just started learning Haskell and am trying to implement some basic
algorithms. My shot at merge sort looks like this:
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort as) (mergeSort bs)
where
(as, bs) = splitInHalf xs
splitInHalf :: [a] -> ([a], [a])
splitInHalf [] = ([], [])
splitInHalf [x] = ([x], [])
splitInHalf (x:y:xys) = (x:xs, y:ys)
where (xs, ys) = splitInHalf xys
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = if x < y
then x:(merge xs (y:ys))
else y:(merge ys (x:xs))
As far as I can tell, my implementation is more or less the same as on
rosetta code [0], literate programs [1] and several stack overflow
questions [2][3].
The algorithm works, but for large lists (for example, 500k random
numbers), I get a stack overflow.
So my question is: How can I change my code so that it works on larger
inputs? Or, more generally, how can I write recursive algorithms in
functional languages that require more nested function calls than fit in
the stack?
Regards
Florian
[0] http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Haskell
[1] http://en.literateprograms.org/Merge_sort_(Haskell)
[2]
http://stackoverflow.com/questions/7554226/haskell-merge-sort-sorting-words-and-numbers
[3] http://stackoverflow.com/questions/1215432/merge-sort-in-haskell
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130916/530a33af/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 16 Sep 2013 19:54:51 +0200
From: Florian Lammel <m...@florianlammel.com>
To: beginners@haskell.org
Subject: [Haskell-beginners] Fwd: Merge Sort Stack Overflow
Message-ID:
<CAAnRmS1jN7QGEEV2vj5eTjrVgmJm7nn5kOhqNLVN+ptZuM=a...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Hi,
I've just started learning Haskell and am trying to implement some basic
algorithms. My shot at merge sort looks like this:
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort as) (mergeSort bs)
where
(as, bs) = splitInHalf xs
splitInHalf :: [a] -> ([a], [a])
splitInHalf [] = ([], [])
splitInHalf [x] = ([x], [])
splitInHalf (x:y:xys) = (x:xs, y:ys)
where (xs, ys) = splitInHalf xys
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = if x < y
then x:(merge xs (y:ys))
else y:(merge ys (x:xs))
As far as I can tell, my implementation is more or less the same as on
rosetta code [0], literate programs [1] and several stack overflow
questions [2][3].
The algorithm works, but for large lists (for example, 500k random
numbers), I get a stack overflow.
So my question is: How can I change my code so that it works on larger
inputs? Or, more generally, how can I write recursive algorithms in
functional languages that require more nested function calls than fit in
the stack?
Regards
Florian
[0] http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Haskell
[1] http://en.literateprograms.org/Merge_sort_(Haskell)
[2]
http://stackoverflow.com/questions/7554226/haskell-merge-sort-sorting-words-and-numbers
[3] http://stackoverflow.com/questions/1215432/merge-sort-in-haskell
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130916/f7bf77bb/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 16 Sep 2013 19:34:34 +0100
From: Oscar Benjamin <oscar.j.benja...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Merge Sort Stack Overflow
Message-ID:
<cahvvxxtodujs9samkega793qamhebyvn_g32vn-x3ue689o...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
On 16 September 2013 18:35, Florian Lammel <m...@florianlammel.com> wrote:
> Hi,
Hi Florian,
>
> I've just started learning Haskell and am trying to implement some basic
> algorithms.
I'm a beginner in Haskell as well so my advice may be corrected by
someone else :)
> My shot at merge sort looks like this:
>
> mergeSort :: Ord a => [a] -> [a]
> mergeSort [] = []
> mergeSort [x] = [x]
> mergeSort xs = merge (mergeSort as) (mergeSort bs)
> where
> (as, bs) = splitInHalf xs
>
> splitInHalf :: [a] -> ([a], [a])
> splitInHalf [] = ([], [])
> splitInHalf [x] = ([x], [])
> splitInHalf (x:y:xys) = (x:xs, y:ys)
> where (xs, ys) = splitInHalf xys
>
> merge :: Ord a => [a] -> [a] -> [a]
> merge xs [] = xs
> merge [] ys = ys
> merge (x:xs) (y:ys) = if x < y
> then x:(merge xs (y:ys))
> else y:(merge ys (x:xs))
>
> As far as I can tell, my implementation is more or less the same as on
> rosetta code [0], literate programs [1] and several stack overflow questions
> [2][3].
Well actually the Rosetta code link shows 3 different implementations
and yours is the first of the three. Did you try the second one (the
bottom up merge)? This is also what's used in the answer to the SO
post [3] and according to the author there it's roughly what's used by
ghc for Data.List.sort so it's presumably a good algorithm.
> The algorithm works, but for large lists (for example, 500k random numbers),
> I get a stack overflow.
I'm not sure how this gets optimised but your call-stack is
essentially as long as the input list. That's only going to work with
such big inputs if the recursion is somehow optimised which I think
happens because of lazy evaluation. However this depends on your merge
function pulling a similar number of items from the 'as' list as from
the 'bs' list. Otherwise (I think) you'll have a whole load of
splitInHalf frames in the stack and maybe that gives your overflow.
I may be *entirely* wrong but I think the problem comes from returning
two lists from a function as you do in splitInHalf but then not
consuming the same number of items from each at any one time. I don't
think this can be optimised in quite the same lazy manner. It would be
fine if you consumed from both lists in unison as in e.g. a merge-sum
algorithm.
> So my question is: How can I change my code so that it works on larger
> inputs? Or, more generally, how can I write recursive algorithms in
> functional languages that require more nested function calls than fit in the
> stack?
Have you tried the other algorithm from e..g Rosetta code? That one
looks like it would work better in a lazy evaluation context since it
just works sequentially on a list of lists.
Oscar
------------------------------
Message: 4
Date: Mon, 16 Sep 2013 14:39:26 -0400
From: Brandon Allbery <allber...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Merge Sort Stack Overflow
Message-ID:
<CAKFCL4Wzyamc851a3Re0oD8xzwbMKFQ-bwXmLinn=lkr8oc...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Mon, Sep 16, 2013 at 2:34 PM, Oscar Benjamin
<oscar.j.benja...@gmail.com>wrote:
> I'm not sure how this gets optimised but your call-stack is
GHC's stack is a pattern match stack, *not* a call stack. While
implementations are allowed to differ in how they produce non-strict
evaluation, GHC uses graph reduction; "calls" are not necessarily done in
the order you would expect in a procedural language.
--
brandon s allbery kf8nh sine nomine associates
allber...@gmail.com ballb...@sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130916/c84fe12b/attachment-0001.html>
------------------------------
Message: 5
Date: Mon, 16 Sep 2013 20:09:14 +0100
From: Oscar Benjamin <oscar.j.benja...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Merge Sort Stack Overflow
Message-ID:
<CAHVvXxTK7-aihqNB9h8PA9nbva1Yi4j=4aboz7ca56yvw+k...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
On 16 September 2013 19:39, Brandon Allbery <allber...@gmail.com> wrote:
> On Mon, Sep 16, 2013 at 2:34 PM, Oscar Benjamin <oscar.j.benja...@gmail.com>
> wrote:
>>
>> I'm not sure how this gets optimised but your call-stack is
>
> GHC's stack is a pattern match stack, *not* a call stack. While
> implementations are allowed to differ in how they produce non-strict
> evaluation, GHC uses graph reduction; "calls" are not necessarily done in
> the order you would expect in a procedural language.
Okay so I'm not so clear on the terminology that should be used for
these things. My understanding is that lazy recursion over a list is
fine in Haskell where it would be problematic in procedural languages,
for example this function:
timesTwo (x:xs) = 2*x:(timesTwo xs)
recurses for every item in a list and could blow the stack for even
small lists in a procedural language but is okay in Haskell. My
understanding is that it's because it just evaluates whichever
elements of the list are needed at the time so if you consume the list
e.g. printing out the items then it never builds up any actual
accumulating stack/heap of in-memory data during processing.
However when you do this
splitInHalf (x:y:xys) = (x:xs, y:ys)
where (xs, ys) = splitInHalf xys
and print out 1000s of values from one list and not the other then
surely *something* has to build up in memory. How else would it
remember which items belong in the other list? (This is what will
happen when the OP tries to sort 500k random numbers since sqrt(500k)
is roughly 1000.)
Or am I still just not getting it?
Oscar
------------------------------
Message: 6
Date: Mon, 16 Sep 2013 21:33:16 +0200
From: Chadda? Fouch? <chaddai.fou...@gmail.com>
To: beginners <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Merge Sort Stack Overflow
Message-ID:
<canfjzra_k4l6bfissmdkg4jvz3cedac8mdmw1b9khslrcq+...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Le 16 sept. 2013 19:35, "Florian Lammel" <m...@florianlammel.com> a ?crit :
> splitInHalf :: [a] -> ([a], [a])
> splitInHalf [] = ([], [])
> splitInHalf [x] = ([x], [])
> splitInHalf (x:y:xys) = (x:xs, y:ys)
> where (xs, ys) = splitInHalf xys
Try the following :
> where ~(xs, ys) = splitInHalf xys
And let us know if that help.
--
Chadda?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130916/d2e2c2d2/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 63, Issue 21
*****************************************
