Dear Haskell Cafe,
I am playing around with a backtracking algorithm that can take quite a while to compute all solutions to a problem. I'd like to use Debug.Trace.trace to provisionally output something that lets me estimate the total time it might take. But I just can't wrap my head around it. This is how I think I'd write it in a C-like language: backtrack(int level, double position, double stepsize, misc...) { // with variations = number of variations to try on this level double part = stepsize / variations // split time on this level for (i=0; i<variations; ++i) { double current = position + part*i // do the actual work backtrack(level+1, current, part); if (level < not_too_much_detail) printf("progress: %f%%\n", current); } } and start with backtrack(1, 0.0, 100.0). And now for something completely Haskell: I have a function step :: State -> Index -> [State] that on a certain level tries all allowable varaiants and returns a list of those that can be further pursued on deeper levels. Then solving the problem involves applying the step on all levels (whicht are indexed by some array indices here): solve :: Problem -> [State] solve problem = foldM step start grid where start = stateFromProblem problem grid = indices (sLines start) I am totally at loss at how I could accomplish some kind of progress reporting in this lazily evaluated (I hope) backtracking scheme. If anybody would like to review the full code (about 80 lines total vor the solver, not counting I/O), this is where I am right now: https://github.com/ctbo/slitherlink/tree/c8951ca1eaf83ce9de43f0483740ce339f4134ae and this is the branch I am working on right now: https://github.com/ctbo/slitherlink/tree/2lines Or is there maybe a totally different and better way to approach this kind of tree search in Haskell? I'm eager to learn. Thanks for your attention Harald -- Harald Bögeholz <b...@ct.de> (PGP key available from servers) Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417 http://www.ct.de/ int f[9814],b,c=9814,g,i;long a=1e4,d,e,h; main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a) while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;} (Arndt/Haenel) Affe Apfel Vergaser /* Heise Zeitschriften Verlag GmbH & Co. KG * Karl-Wiechert-Allee 10 * 30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 * Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag * Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB 60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe