Hi Wolfgang,
> Shouldn’t breadth-first search find every solution?
Yes, it should (unless any individual solution diverges.)
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). Nondeterminism in the definition of *variables* is
shared (unlike nondeterminism in the definition of *operations*, even
top-level ones without arguments.)
While coins looks like a nondeterministic operation without arguments,
it is a variable, because it is defined locally. Therefore it is
equivalent to
repeat 0 ? repeat 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.
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.
Interesting example!
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 - 10:41:38 CEST