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