Sergio Antoy schrieb:
> E.g., the following does not work:
>
> prelude> findall (permute [1,2,3] =:=)
>
> which is often confusing to students.
Why does it not work? It seems to me that this is solely a problem of
the old pakcs frontend, which does not handle application precedence
properly, isn't it? The quirks of that frontend are very confusing to
students indeed... but there will soon be help for PAKCS users, as we
adapted the much better frontend of the Münster Curry Compiler to PAKCS.
(You can write "findall (permute [1,2,3] =:=)" in the MCC, but with the
same confusing result as discussed for allValuesOf because of
lambda-lifting.)
And for allValuesOf
> Having the function in the prelude with a few lines of
> comments explaining its problems might be better that letting the
> user, particularly if a student, code the function in his program
> and discover the problems the hard way. We, as implementors, look
> much better by making the problems clear rather than sweeping them
> under the rug.
This is a really good point. Thus convinced, I would like to add some
definitions to the proposal, as this is how we handle non-determinism in
the prelude of the new Curry implementation, following the proposal of
the mentioned paper:
----------------------------------------------------------------
-- Encapsulated search:
----------------------------------------------------------------
--- Search trees represent the search space of evaluating a given
--- term. For example, the search tree corresponding to
--- the evaluation of
--- (0?1) + (0?1)
--- is Or [Or [Value 0,Value 1],Or [Value 1,Value 2]]
--- whereas the one corresponding to
--- let x=0?1 in x+x
--- is Or [Value 0,Value 2].
data SearchTree a
= Fail
| Value a
| Or [SearchTree a]
| Suspend
--- Basic search control operator, providing the searchtree lazily with
--- respect to Or branches. The argument of the Value constructor is
--- always evaluated to full normal form. This guarantees that it is
--- really a value and does neither induce another fail nor a
--- branching.
getSearchTree :: a -> IO (SearchTree a)
getSearchTree external
--- depth first search
allValuesD :: SearchTree a -> [a]
allValuesD (Value x) = [x]
allValuesD Fail = []
allValuesD Suspend = []
allValuesD (Or xs) = concatMap allValuesD xs
--- breadth first search
allValuesB :: SearchTree a -> [a]
allValuesB st = unfoldOrs [st]
where
partition (Value x) (vs,ors) = (x:vs,ors)
partition (Or xs) (vs,ors) = (vs,xs++ors)
partition Fail x = x
partition Suspend x = x
unfoldOrs [] = []
unfoldOrs (x:xs) = let (vals,ors) = foldr partition ([],[]) (x:xs) in
vals ++ unfoldOrs ors
-------------------------------------------------------------------------------
The primitive getSearchTree can only be incompletely defined in PAKCS as
getSearchTree x = return $ case findall (x=:=) of
[] -> Fail
[x] -> Value x
xs -> Or (map Value xs)
But we could also explain the shortcomings in the comments.
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fr Okt 14 2005 - 10:32:05 CEST