Am Freitag, den 26.04.2013, 04:28 +0200 schrieb Sebastian Fischer:
> Hi Wolfgang,
>
> […]
>
> I had a look at your code. First, I was impressed with the elegance of
> the cyclic definition of
>
> applyRules rules str = strs where
> strs = zipWith applyRule rules (str : strs)
>
> but now I think it may be (part of) your problem.
>
> Curry uses "call-time choice" for the definition of variables. For
> example, in
>
> let coins = (0?1) : coins in coins
>
> all uses of coins depend on the first (and, therefore, *only* choice
> between 0 and 1).
>
> […]
>
> Similarly, your local definition of strs probably has less
> nondeterminism than you intended which might be the reason why you
> don't get another result.
Hi Sebastian,
I’m not sure whether this is the problem. The function applyRules itself
doesn’t add any nondeterminism of its own. It calls the function
applyRule (singular), which is nondeterministic. However, it calls
applyRule for every element of the rules argument. Well, these are
different calls with generally different arguments; so applyRules
(plural) doesn’t reuse function results through sharing as your coins
variable does. Do you think, there is a problem nevertheless?
On the other hand, I don’t use applyRules just to compute results, but I
search for rules arguments also. Could this be problematic in
conjunction with the circular definition of strs?
> It is unclear to me how to fix your program in an elegant way. You
> seem to require some sharing of strs but not all. You want to share
> individual results of nondeterministic computations without sharing
> the nondeterministic choices.
No, I don’t think I want to share results at all.
Anyway, I have now rewritten the applyRules function in a traditional
inductive style:
> applyRules :: [Rule] -> Str -> [Str]
> applyRules [] _ = []
> applyRules (rule : rules) str = let
>
> str' = applyRule rule str
>
> in str' : applyRules rules str'
Unfortunately, the program still doesn’t work.
> Interesting example!
Best wishes,
Wolfgang
> On Wed, Apr 24, 2013 at 12:27 PM, Wolfgang Jeltsch <wolfgang_at_cs.ioc.ee> wrote:
> > Hi Sergio,
> >
> > thank you for your answer.
> >
> > Actually, I want to avoid the manual construction of a search tree,
> > since this is, in my opinion, one of the things that Curry should handle
> > itself.
> >
> > I also don’t understand why an infinite search space should be a
> > problem, as I’m using breadth-first search. Shouldn’t breadth-first
> > search find every solution?
> >
> > Best wishes,
> > Wolfgang
> >
> > Am Dienstag, den 23.04.2013, 13:29 -0700 schrieb Sergio Antoy:
> >> Hi Wolfgang,
> >>
> >> Interesting system, thank you for bringing it to this mailing
> >> list. I do not fully understand your code. However, most
> >> Curry implementations are not complete, hence an infinite
> >> computation space is always dangerous, unless you control
> >> yourself the traversal.
> >>
> >> I attach such an implementation hacked in 10 minutes.
> >> It prints the computation space up to a fixed depth.
> >> Indeed, it is shorter and simpler than Haskell's.
> >>
> >> To look for a solution more efficiently than traversing the
> >> space in some order, one could represent the computation space
> >> as a trie. Just an idea.
> >>
> >> Best,
> >> Sergio
> >>
> >> The search space is infinite
> >>
> >> On Tue, 23 Apr 2013, at 20:48, Wolfgang Jeltsch <wolfgang_at_cs.ioc.ee> wrote:
> >>
> >> > Hi,
> >> >
> >> > I have recently implemented a derivation engine for the MIU system from
> >> > Douglas Hofstadter’s book “Gödel, Escher, Bach” in Haskell. See my blog
> >> > post:
> >> >
> >> > <http://jeltsch.wordpress.com/2013/04/18/miu-in-haskell/>
> >> >
> >> > Now I wanted to implement the same thing in Curry, since this could
> >> > dramatically simplify the code. I wrote an implementation, which I have
> >> > attached to this e-mail.
> >> >
> >> > Unfortunately when I try out this implementation, it prints at most one
> >> > solution and then causes heavy use of the swap partition. So if anyone
> >> > would be interested in looking at the code and giving me hints for
> >> > improving it, I would be very thankful.
> >> >
> >> > Best wishes,
> >> > Wolfgang
> >>
> >> > > import SearchTree
> >> > >
> >> > > data Sym = M | I | U
> >> > >
> >> > > type Str = [Sym]
> >> > >
> >> > > showSym :: Sym -> String
> >> > > showSym M = "M"
> >> > > showSym I = "I"
> >> > > showSym U = "U"
> >> > >
> >> > > showStr :: Str -> String
> >> > > showStr str = concatMap showSym str
> >> > >
> >> > > data Rule = R1 | R2 | R3 | R4
> >> > >
> >> > > showRule :: Rule -> String
> >> > > showRule R1 = "R1"
> >> > > showRule R2 = "R2"
> >> > > showRule R3 = "R3"
> >> > > showRule R4 = "R4"
> >> > >
> >> > > applyRule :: Rule -> Str -> Str
> >> > > applyRule R1 (init ++ [I]) = init ++ [I,U]
> >> > > applyRule R2 ([M] ++ tail) = M : tail ++ tail
> >> > > applyRule R3 (pre ++ [I,I,I] ++ post) = pre ++ [U] ++ post
> >> > > applyRule R4 (pre ++ [U,U] ++ post) = pre ++ post
> >> > >
> >> > > applyRules :: [Rule] -> Str -> [Str]
> >> > > applyRules rules str = strs where
> >> > >
> >> > > strs = zipWith applyRule rules (str : strs)
> >> > >
> >> > > data Deriv = Deriv [DStep] Str
> >> > >
> >> > > data DStep = DStep Str Rule
> >> > >
> >> > > showDeriv :: Deriv -> String
> >> > > showDeriv (Deriv steps goal) = " " ++
> >> > > concatMap showDStep steps ++
> >> > > showStr goal ++
> >> > > "\n"
> >> > >
> >> > > showDerivs :: [Deriv] -> String
> >> > > showDerivs derivs = concatMap ((++ "\n") . showDeriv) derivs
> >> > >
> >> > > showDStep :: DStep -> String
> >> > > showDStep (DStep origin rule) = showStr origin ++
> >> > > "\n-> (" ++
> >> > > showRule rule ++
> >> > > ") "
> >> > >
> >> > > derivation :: Str -> Str -> Deriv
> >> > > derivation start end
> >> > > | start : applyRules rules start =:= init ++ [end]
> >> > > = Deriv (zipWith DStep init rules) end where
> >> > >
> >> > > rules :: [Rule]
> >> > > rules free
> >> > >
> >> > > init :: [Str]
> >> > > init free
> >> > >
> >> > > printDerivations :: Str -> Str -> IO ()
> >> > > printDerivations start end = do
> >> > > searchTree <- getSearchTree (derivation start end)
> >> > > putStr $ showDerivs (allValuesBFS searchTree)
> >>
> >> > _______________________________________________
> >> > curry mailing list
> >> > curry_at_lists.RWTH-Aachen.DE
> >> > http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
> >>
> >
> >
> > _______________________________________________
> > curry mailing list
> > curry_at_lists.RWTH-Aachen.DE
> > http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
> >
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fr Apr 26 2013 - 18:38:44 CEST