Hi Wolfgang,
> 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.
Yes, this is a good idea. Curry constructs the search tree.
> 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?
The computation space and the search tree are different
things. Yes, a bf traversal of the computation space will
find every solution. I do not know exactly how the search
space is constructed/traversed, hence I won't comment on this.
Best,
Sergio
> 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 - 09:45:08 CEST