Heinrich Apfelmus wrote:
Actually you need five versions: The pure version, the pre-order
traversal, the post-order traversal, the in-order traversal, and the
reverse in-order traversal. And that is just looking at syntax. If you
care about your semantics you could potentially have more (or less).
Exactly! There is no unique choice for the order of effects when lifting
a pure function to an effectful one.
For instance, here two different versions of an effectful map :
mapM f [] = return []
mapM f (x:xs) = do
y <- f x
ys <- mapM f xs
return (y:ys)
mapM2 f [] = return []
mapM2 f (x:xs) = do
ys <- mapM2 f xs
y <- f x
return (y:ys)
Which one will the DCC compiler chose, given
map f [] = []
map f (x:xs) = f x : map f xs
Disciple uses default strict, left to right evaluation order. For
the above map function, if "f" has any effects they will be executed
in the same order as the list elements.
? Whenever I write a pure higher order function, I'd also have to
document the order of effects.
If you write a straight-up higher-order function like map above,
then it's neither pure or impure. Rather, it's polymorphic in the
effect of its argument function. When effect information is
added to the type of map it becomes:
map :: forall a b %r1 %r2 !e1
. (a -(!e1)> b) -> List %r1 a -(!e2)> List %r2 b
:- !e2 = !{ !Read %r1; !e1 }
Which says the effect of evaluating map is to read the list and
do whatever the argument function does. If the argument function
is pure, and the input list is constant, then the application
of map is pure, otherwise not.
If you want to define an "always-pure" version of map, which
only accepts pure argument functions then you can give it the
signature:
pureMap :: (a -(!e1)> b) -> List %r1 a -> List %r2 b
:- Pure !e1, Const %r1
.. and use the same definition as before.
Note that you don't have to specify the complete type in the
source language, only the bits you care about - the rest is
inferred.
Now if you try to pass pureMap an impure function, you get
an effect typing error.
Adding purity constraints allows you to write H.O functions
without committing to an evaluation order, so you can change
it later if desired.
Ben.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
