Do the libraries define S' ?
There's a pattern of higher-order function usage I find myself repeatedly wanting to use, exemplified by the following: [[ -- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a) (.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&) (.|.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.|.) = combineTest (||) t1 = (>0) .&. (<=4) $ 2 -- True t2 = (>0) .&. (<=4) $ 5 -- False t3 = (>0) .&. (<=4) $ 0 -- False t4 = (>0) .|. (<=4) $ 5 -- True t5 = (>0) .|. (<=4) $ 0 -- True tall = and [t1,not t2,not t3,t4,t5] ]] Looking at the fully-generalized type of 'combineTest', and digging around in SPJ's book on implementation of FP languages, I notice that my combineTest function has the same reduction pattern as the S' combinator used as an optimization of SK combinator compilation. All this (the recurring requirement, and the fact that S' is a very well-known combinator) leads me to think that maybe there is a version of S' somewhere in the standard Haskell libraries. If there is, where is it please? If not, should it be in there somewhere? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
On Wed, Jul 07, 2004 at 01:18:54PM +0100, Graham Klyne wrote:
There's a pattern of higher-order function usage I find myself repeatedly wanting to use, exemplified by the following:
[[ -- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a)
(.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&)
This can be seen as liftM2 on the reader monad ((->) r): (.&.) = liftM2 (&&) t1 = (>0) .&. (<=4) ans = t1 3 == True Andrew
At 14:45 07/07/04 -0400, Andrew Pimlott wrote:
This can be seen as liftM2 on the reader monad ((->) r):
(.&.) = liftM2 (&&)
Thanks to those who pointed out this. I think the ((->) r) reader monad is one of those I've yet to fully grasp. #g -- At 14:45 07/07/04 -0400, Andrew Pimlott wrote:
-- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a)
(.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&)
This can be seen as liftM2 on the reader monad ((->) r):
(.&.) = liftM2 (&&) t1 = (>0) .&. (<=4) ans = t1 3 == True
------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
hi, you can use the reader (environment monad) for this. combineTest c t1 t2 = liftM2 c t1 t2 lately i have been using 2 combinators to do things like that (thanks to Thomas Hallgren for showing me this): -- a nicer name for fmap (or liftM if one prefers) (#) :: Functor f => (a -> b) -> f a -> f b -- a nicer name for "ap" from Monad.hs (<#) :: Monad m => m (a -> b) -> m a -> m b then you can write the above as: cobineTest c t1 t2 = c # t1 <# t2 i like those two as then you don't need all the liftM? functions. -iavor Graham Klyne wrote:
There's a pattern of higher-order function usage I find myself repeatedly wanting to use, exemplified by the following:
[[ -- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a)
(.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&)
(.|.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.|.) = combineTest (||)
t1 = (>0) .&. (<=4) $ 2 -- True t2 = (>0) .&. (<=4) $ 5 -- False t3 = (>0) .&. (<=4) $ 0 -- False t4 = (>0) .|. (<=4) $ 5 -- True t5 = (>0) .|. (<=4) $ 0 -- True
tall = and [t1,not t2,not t3,t4,t5] ]]
Looking at the fully-generalized type of 'combineTest', and digging around in SPJ's book on implementation of FP languages, I notice that my combineTest function has the same reduction pattern as the S' combinator used as an optimization of SK combinator compilation.
All this (the recurring requirement, and the fact that S' is a very well-known combinator) leads me to think that maybe there is a version of S' somewhere in the standard Haskell libraries.
If there is, where is it please?
If not, should it be in there somewhere?
#g
------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Hi folks Iavor S. Diatchki wrote:
hi, you can use the reader (environment monad) for this.
lately i have been using 2 combinators to do things like that (thanks to Thomas Hallgren for showing me this):
-- a nicer name for fmap (or liftM if one prefers) (#) :: Functor f => (a -> b) -> f a -> f b
-- a nicer name for "ap" from Monad.hs (<#) :: Monad m => m (a -> b) -> m a -> m b
i like those two as then you don't need all the liftM? functions. -iavor
As some of you know, I like them a lot too. In fact, if you have a return-like thing and an ap-like thing, you can make fmap as well. (Note that the return for the environment monad is none other than S's best friend K.) So I got hacking, a little while ago... infixl 9 <%> -- my name for <# -- others have other names class Idiom i where idi :: x -> i x (<%>) :: i (s -> t) -> i s -> i t I call them idioms because it's like having the apparatus of applicative programming, just in a different (perhaps impure) idiom. [I only just found out that they show up under the name Sequence in the experimental Control.Sequence module. I should have known. It's part of the Arrow stuff, and these things are an interesting species of Arrow. As far as I know, it was Ross Paterson who identified them in the categorical jungle as weakly symmetric lax monoidal functors.] I thought I'd like some `funny brackets' which would just shunt the typechecker into an idiom and allow me to program fairly normally. Replacing this return f `ap` t1 `ap` ... `ap` tn with this idI f t1 ... tn Idi Being a crook, I figured out how to implement my idI ... Idi brackets. Sick hack follows: data Idi = Idi class Idiom i => Idiomatic i f g | g -> f i where idI :: f -> g idiomatic :: i f -> g instance Idiom i => Idiomatic i x (Idi -> i x) where idI x Idi = idi x idiomatic ix Idi = ix instance Idiomatic i f g => Idiomatic i (s -> f) (i s -> g) where idI sf = idiomatic (idi sf) idiomatic isf is = idiomatic (isf <%> is) It's also useful to insert stuff which just has an effect in the idiom, but whose pure part isn't important. You just shove in Ig blah like this---here rhubarb and custard get executed, but their values don't get passed to f. idI f t1 Ig rhubarb t2 t3 Ig custard Idi How to make this work? data Ig = Ig instance Idiomatic i f g => Idiomatic i f (Ig -> i x -> g) where idI f = idiomatic (idi f) idiomatic f Ig ix = idiomatic (idi const <%> f <%> ix) Why bother with these idioms? For one thing, it's a more functional notation for working with monads. But there's more to it than that. Here's a serious generalization of the Prelude's mapM class IFunctor f where imap :: Idiom i => (s -> i t) -> f s -> i (f t) instance IFunctor [] where imap f [] = idI [] Idi imap f (x : xs) = idI (:) (f x) (imap f xs) Idi imap is mapM when f is [] and i is a monad. To my mind, imap is the real payoff for working with idioms. First-order type constructors are IFunctors, but ((->) r) isn't (or you could solve the Halting Problem). imap is more powerful than mapM not only because it generalizes lists, but because it only needs idioms, not monads. Here's a non-monadic idiom: newtype Monoid a => a :<++ x = Acc {accumulated :: a} instance Monoid a => Idiom ((:<++) a) where idi _ = Acc mempty Acc a <%> Acc b = Acc (mappend a b) Now a :<++ t is a phantom type, indicating that its a has been accumulated from some t. We can now write the map-and-flatten pattern once, for all IFunctors and all Monoids: icrush :: (IFunctor f, Monoid a) => (x -> a) -> f x -> a icrush ax = accumulated . imap (Acc . ax) One of my favourite monoids is this: newtype Must = Must {must :: Bool} instance Monoid Must where mempty = Must True mappend (Must x) (Must y) = Must (x && y) Now we can generalize all to IFunctors all :: IFunctor f => (x -> Bool) -> f x -> Bool all p = must . icrush (Must . p) And that's how you solve the Halting Problem if ((->) r) is an IFunctor! [Exercise for masochists: given suitable monoids, find all the library functions implementable by icrush idi, modulo newtypes.] I apologize if I'm becoming tediously repetitive every time a whiff of this approaches the list, but I find this equipment really useful. Quite a few people have been using it in various forms: the parser-combinator experts had these gadgets long ago, but I don't think they've achieved the widespread currency they deserve. And every time they come up as cool gadgets for working _with_monads_, I feel I have to jump in, because they're all that and loads more. Cheers Conor
Conor T McBride writes:
As some of you know, I like them a lot too. In fact, if you have a return-like thing and an ap-like thing, you can make fmap as well. (Note that the return for the environment monad is none other than S's best friend K.)
So I got hacking, a little while ago...
infixl 9 <%> -- my name for <# -- others have other names class Idiom i where idi :: x -> i x (<%>) :: i (s -> t) -> i s -> i t
I call them idioms because it's like having the apparatus of applicative programming, just in a different (perhaps impure) idiom.
[I only just found out that they show up under the name Sequence in the experimental Control.Sequence module. I should have known. It's part of the Arrow stuff, and these things are an interesting species of Arrow. As far as I know, it was Ross Paterson who identified them in the categorical jungle as weakly symmetric lax monoidal functors.]
I've also seen this referred to as a pointed functor[1] and a premonad[2]. So here's yet another definition of Monad: class Functor f where fmap :: (a -> b) -> f a -> f b class Functor p => Premonad p where return :: a -> p a class Premonad m => Monad m where join :: m (m a) -> m a (>>=) :: m a -> (a -> m b) -> m b join m = m >>= id m >>= k = join (fmap k m) [1] Composing Monads Using Coproducts <http://www.informatik.uni-bremen.de/~cxl/papers/icfp02.pdf> [2] Composing Monads <http://www.cse.ogi.edu/~mpj/pubs/composing.html> -- David Menendez <zednenem@psualum.com> <http://www.eyrie.org/~zednenem/>
On Thu, Jul 08, 2004 at 08:36:57PM -0400, David Menendez wrote:
Conor T McBride writes:
infixl 9 <%> -- my name for <# -- others have other names class Idiom i where idi :: x -> i x (<%>) :: i (s -> t) -> i s -> i t
I call them idioms because it's like having the apparatus of applicative programming, just in a different (perhaps impure) idiom.
[I only just found out that they show up under the name Sequence in the experimental Control.Sequence module. I should have known. It's part of the Arrow stuff, and these things are an interesting species of Arrow. As far as I know, it was Ross Paterson who identified them in the categorical jungle as weakly symmetric lax monoidal functors.]
I've also seen this referred to as a pointed functor[1] and a premonad[2]. [...] class Functor f where fmap :: (a -> b) -> f a -> f b
class Functor p => Premonad p where return :: a -> p a
Not quite: premonads let you lift values (using return) and unary functions (using fmap), but the things Conor is talking about let you lift functions of any arity. A premonad doesn't give you lift2 :: (a -> b -> b) -> f a -> f b -> f c
On Wed, Jul 07, 2004 at 01:18:54PM +0100, Graham Klyne wrote:
There's a pattern of higher-order function usage I find myself repeatedly wanting to use, exemplified by the following:
[[ -- combineTest :: (Bool->Bool->Bool) -> (a->Bool) -> (a->Bool) -> (a->Bool) combineTest :: (b->c->d) -> (a->b) -> (a->c) -> a -> d combineTest c t1 t2 = \a -> c (t1 a) (t2 a)
(.&.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.&.) = combineTest (&&)
(.|.) :: (a->Bool) -> (a->Bool) -> (a->Bool) (.|.) = combineTest (||)
All this (the recurring requirement, and the fact that S' is a very well-known combinator) leads me to think that maybe there is a version of S' somewhere in the standard Haskell libraries.
I use almost exactly the same thing in my code. And I nearly came up with the same names as you! (I have .&&. and .||.) I find them very useful in guards: foo x y | (this .&&. that) x = ... I don't believe this kind of abstraction is defined anywhere in the standard libraries. Others have noted that you can rewrite it in terms of the Reader monad. Perhaps the Boolean specialistation is useful enough to warrant its own definition in a standard library, perhaps Data.Bool? Cheers, Bernie.
On Thu, Jul 08, 2004 at 03:47:08PM +1000, Bernard James POPE wrote:
I use almost exactly the same thing in my code. And I nearly came up with the same names as you! (I have .&&. and .||.)
I find them very useful in guards:
foo x y | (this .&&. that) x = ...
I don't believe this kind of abstraction is defined anywhere in the standard libraries.
Others have noted that you can rewrite it in terms of the Reader monad. Perhaps the Boolean specialistation is useful enough to warrant its own definition in a standard library, perhaps Data.Bool?
*digs up his own yet-another-variant* Though I can't claim to have come up with the same names, I did invent basically the same thing. I also made a class of it to make it work with multiple arguments: *Main> ((==) ||| (>)) 4 3 True Then I got carried away and made (->) an instance of Num: *Main> (negate * abs) 5 -25 *Main> ((*) + (^)) 2 3 14 Other "uses" for dup are dup (.) and dup (>>) --dup :: (b -> b -> b) -> (a -> b) -> (a -> b) -> (a -> b) dup :: (b1 -> b2 -> c) -> (a -> b1) -> (a -> b2) -> (a -> c) dup op f g = \x -> f x `op` g x class Boolish a where (&&&), (|||):: a -> a -> a nott :: a -> a true, false :: a instance Boolish Bool where (&&&) = (&&) (|||) = (||) nott = not true = True false = False andd, orr :: (Boolish a) => [a] -> a andd xs = foldr (&&&) true xs orr xs = foldr (|||) false xs instance Boolish b => Boolish (a -> b) where (&&&) = dup (&&&) (|||) = dup (|||) nott f = nott . f true = const true false = const false {- I haven't found a use for them yet: alll (>=) [0..5] 0 seems to be always replacable by alll (>=0) [0..5] -} alll, anyy :: (Boolish b) => (a -> b) -> [a] -> b alll f = andd . map f anyy f = orr . map f ----- Num (->) ---- -- urgh instance Num b => Show (a -> b) where show = error "Unimplementable" -- urgh again {- I failed to come up with a class for something like (===) :: (Boolish b, Eqq c) => (a -> c) -> (a -> c) -> (a -> b) (all (even /== odd) [0..] looks funny, if (/==) would work with arbitrary numbers of arguments) -} instance Num b => Eq (a -> b) where (==) = error "Unimplementable" instance Num b => Num (a -> b) where (+) = dup (+) (-) = dup (-) (*) = dup (*) signum f = signum . f abs f = abs . f fromInteger = const . fromInteger Groeten, Remi -- Nobody can be exactly like me. Even I have trouble doing it.
participants (8)
-
Andrew Pimlott -
Bernard James POPE -
Conor T McBride -
David Menendez -
Graham Klyne -
Iavor S. Diatchki -
Remi Turk -
Ross Paterson