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.