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. Re: backtracking search and memory usage (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Sat, 15 Mar 2014 23:08:43 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] backtracking search and memory usage
Message-ID:
<capy+zdqq3ex9kjuwue-h8dftbnsncj-51dsr4nuajohrwq2...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Let's look at the requirements for this problem, uncovering some of the
unspoken ones:
1. very general problem
2. fast, or at least not too slow
3. memory-efficient
4. correct
Leaving aside performance issues 2 and 3, is it possible that 1 and 4 alone
are enough to deliver plenty of heartburn?
I can think of at least one class of problems: the enumeration and
application of choices lead to cyclical states. Hence resulting in a list
of solutions pockmarked with bottoms.
I mean your backtrack function is a correct and succinct description of the
very notion of backtracking. The devil is in the details of state design,
including the enumeration and application issues I've described.
By narrowing the scope of the problem so that you first obtain a library
that correctly solves it, you could then focus on performance issues.
-- Kim-Ee
On Sat, Mar 15, 2014 at 9:06 AM, Dennis Raddle <[email protected]>wrote:
> I want to implement backtracking search, but I wonder if I'm going to
> immediately run into memory usage problems if I don't use strict evaluation
> somewhere. I'm very hazy on how to implement strict evaluation. I'm
> thinking of creating a generic algorithm that looks something like the
> following.
>
> We have the concept of a data construct that can be built step by step. At
> each step are choices. We are investigating all the choices and finding
> series of choices that lead to a completed data construct or "solution." We
> want to generate a list of all solutions.
>
> (My Haskell syntax is rusty so there may be errors in the following.)
>
>
> class Construct a where
> enumerateChoices :: a -> [b]
> applyChoice :: a -> b -> a
> isSolution :: a -> Bool
>
> backtrack :: Construct a => a -> [a]
> backtrack c
> | isSolution c = [c]
> | otherwise =
> concat . map (backtrack . applyChoice c) . enumerateChoices $ c
>
> So my question is whether this is going to use a lot of memory to run,
> maybe by holding all partially solved data? Where would strict evaluation
> go?
>
>
>
>
> _______________________________________________
> 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/20140315/b81fdebe/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 69, Issue 20
*****************************************
