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:56:31 CEST