[Haskell-beginners] FW: Beginners Digest, Vol 91, Issue 26

Don’t worry about the time to append rather than pretend, it is not “exponential” nor even cubic. You are making a list of length in an N^2 algorithm. Appending to a list adds another tiny O(N^2) step, which is dominated by the main algorithm (also O(N^2), which both takes longer and evaluates vastly more values (failures as well as successes.) Message: 3 Date: Thu, 21 Jan 2016 19:05:17 +0000 From: Rein Henrichs To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell , masonmlai@gmail.com Subject: Re: [Haskell-beginners] program not running lazily Message-ID: Content-Type: text/plain; charset="utf-8" s/not/note, sorry On Thu, Jan 21, 2016 at 10:42 AM Rein Henrichs wrote:

But not that doing so will cause the program to have an exponential runtime as each new ys must be repeatedly traversed to append a [y].. The alternative is to *unfold* your list by recursing on the right hand side of the (:) to add new elements.

On Thu, Jan 21, 2016 at 5:43 AM Doug McIlroy wrote:

...

Each time you find another good 9-mer, you add it to the head of the list. This means that the ultimate list will be in reverse order of discovery: the first element to be printed is the last one to be found. To get output in the order it was discovered, build the output by ys++[y] rather than y:ys. _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners