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
Received on Mi Apr 24 2013 - 15:58:08 CEST