- Haskell - Haskell.org

Position of arguments in function definition and performance
by José Romildo Malaquias 07 Feb '02

07 Feb '02

Hello. Please, tell me which set of definitions below should I expected to be more efficient: the reverse1 or the reverse2 functions. reverse1 [] ys = ys reverse1 (x:xs) ys = reverse2 (x:ys) xs reverse2 ys [] = ys reverse2 ys (x:xs) = reverse2 (x:ys) xs The difference rely on the position of the argument in which the pattern matching is done in the function definition. Regards. Romildo -- Prof. José Romildo Malaquias Departamento de Computação http://iceb.ufop.br/~romildo Universidade Federal de Ouro Preto romildo(a)iceb.ufop.br Brasil romildo(a)uber.com.br

2 3

RE: Reference types
by Ashley Yakeley 07 Feb '02

07 Feb '02

At 2002-02-07 02:09, I wrote: >The kind of generalisation you are proposing is, in my opinion, best done >explicitly by Haskell. Primitive functions and types should be as simple, >concrete and primitive as possible. Let Haskell do the clever >generalisation stuff. As a rule, I'm opposed to any generalisation in the standard libraries over IO and (ST s) that cannot be made to work for user-defined monads. People will use them in their code, and those monads will become "privileged". I admit I have a stake in this, my JVM-Bridge makes extensive use of lifted monads, and so I'd like porting code between monads to be as easy as possible. The way forward for this is classes and types in the standard libraries that generalise over any monad which has the necessary properties. -- Ashley Yakeley, Seattle WA

1 0

RE: Reference types
by John Hughes 07 Feb '02

07 Feb '02

Simon writes: There were really two parts to my message: 1. Have a single built-in type (Ref), rather than two (IORef and STRef). I don't see how that can be anything other than a Good Thing, can it? The primitive operations over Refs are still non-overloaded, as before: newIORef :: a -> IO (Ref IO a) newSTRef :: a -> ST s (Ref (ST s) a) ...etc... 2. Have a RefMonad type class to overload the new, read, write operations over Refs. But nothing in my message precludes also having a RefMonad2 class with two parameters, and whatever functional dependencies (or lack of them) that you like class RefMonad2 r m where new :: a -> m (r a) read :: r a -> m a write :: r a -> a -> m () instance RefMonad2 (Ref IO) IO where ... instance RefMonad2 (Ref (ST s)) (ST s) where ... So then it's only a question of who gets the name "RefMonad"! (Incidentally, so far as I know, RefMonad isn't in any of the existing libraries.) It's in my libraries, and in other people's, with the same definition. Just not in any standard ones yet. (Proposal in preparation!) So I conclude: (1) is a win (2) is a question of what we name the new (and undoubtedly useful) class that I tendentiously called RefMonad OK, I see your point. However, note that your RefMonad class can only ever have two instances, since there is no way to define creation of a reference of any type other than Ref IO or Ref (ST s). My RefMonad class can usefully have many instances. So if you ask me, the benefit of defining your class is rather limited. The goal here is to write generic imperative code, that can work over either underlying monad, right? In that case, why would you use a class which limits you to one of the two monads IO or ST, when you can equally well use a class which works over any monad built on top of one of these? I can't see any reason to use SimonRefMonad when one can instead use JohnRefMonad. Hence I suggest that I get the nice name! The functional dependency m->r is important in practice. You get continual hassle with ambiguous overloading otherwise. Given that one wants JohnRefMonad( with the functional dependency) anyway, I can't really see that (1) is much of a win. It doesn't help define instances of the class. Maybe in some absolute sense it might be a cleaner design, but I can't see that it's worth breaking code to make this change. (Any imperative code with explicit type signatures will of course break if you make this change). John

1 0

RE: Reference types
by Ashley Yakeley 07 Feb '02

07 Feb '02

At 2002-02-07 01:19, Simon Peyton-Jones wrote: >1. Have a single built-in type (Ref), rather than two (IORef and >STRef). >I don't see how that can be anything other than a Good Thing, can it? The problem is that your Ref type is primitive, which means users wouldn't be able to create their own Refs. I suppose the user could create a Ref2 type, but wouldn't it be easier to do this: data Ref m a = MkRef { get :: m a, set :: a -> m () }; class RefMonad m where newRef :: a -> m (Ref m a) This has the advantage of not changing existing library code, only adding to it. It works out the same for the user as your proposal, only more general. The kind of generalisation you are proposing is, in my opinion, best done explicitly by Haskell. Primitive functions and types should be as simple, concrete and primitive as possible. Let Haskell do the clever generalisation stuff. -- Ashley Yakeley, Seattle WA

1 0

Re: Reference types
by Ashley Yakeley 07 Feb '02

07 Feb '02

At 2002-02-07 00:52, John Hughes wrote: >Hmm. Yes. But you still haven't addressed dropping references created in the >transformed monad back into the underlying one again. Oh that's easy: liftedNewSTRef :: (LiftedMonad (ST s) m) => a -> m (Ref (ST s) a); liftedNewSTRef = lift . newSTRef; >And this does seem to >be getting rather complicated and expensive... are you sure it's worth the >candle? I suspect any alternative will be at least as complicated. Bear in mind you are still going to need a type for your references and also get and set functions that work in all your monads. >I'm quite happy to have references depend on a state identifier myself. For instance...? -- Ashley Yakeley, Seattle WA

1 0

Re: Reference types
by Ashley Yakeley 07 Feb '02

07 Feb '02

At 2002-02-05 16:54, I wrote: > data Ref m a = MkRef > { > get :: m a, > set :: a -> m (), > modify :: (a -> a) -> m () > }; Better, data Ref m a = MkRef { get :: m a, set :: a -> m () }; modify :: (Monad m) => Ref m a -> (a -> a) -> m (); modify ref map = (get ref) >>= ((set ref) . map); -- Ashley Yakeley, Seattle WA

1 0

RE: Reference types
by Simon Peyton-Jones 07 Feb '02

07 Feb '02

Wow. One innocent message... | Oh no, please don't do this! I use the RefMonad class, but | *without* the dependency r -> m. Why not? Because I want to | manipulate (for example) STRefs in monads built on top of the | ST monad via monad transformers. So I use the same reference | type with *many different* monads! Your change would make | this impossible. I don't think so. There were really two parts to my message: 1. Have a single built-in type (Ref), rather than two (IORef and STRef). I don't see how that can be anything other than a Good Thing, can it? The primitive operations over Refs are still non-overloaded, as before: newIORef :: a -> IO (Ref IO a) newSTRef :: a -> ST s (Ref (ST s) a) ...etc... 2. Have a RefMonad type class to overload the new, read, write operations over Refs. But nothing in my message precludes also having a RefMonad2 class with two parameters, and whatever functional dependencies (or lack of them) that you like class RefMonad2 r m where new :: a -> m (r a) read :: r a -> m a write :: r a -> a -> m () instance RefMonad2 (Ref IO) IO where ... instance RefMonad2 (Ref (ST s)) (ST s) where ... So then it's only a question of who gets the name "RefMonad"! (Incidentally, so far as I know, RefMonad isn't in any of the existing libraries.) So I conclude: (1) is a win (2) is a question of what we name the new (and undoubtedly useful) class that I tendentiously called RefMonad Or am I missing something? Simon

1 0

Re: Reference types
by John Hughes 07 Feb '02

07 Feb '02

I have a solution... data Ref m a = MkRef { get :: m a, set :: a -> m (), modify :: (a -> a) -> m () }; -- m somehow uses 'rep' internally class (Monad rep, Monad m) => LiftedMonad rep m where { lift :: rep a -> m a; } instance LiftedMonad (ST s) (ST s) where { lift = id; } instance LiftedMonad (ST s) TransformedMonad where ... liftRef :: (LiftedMonad rep m) => Ref rep a -> Ref m a; liftRef ref = ... newSTRef :: a -> (ST s) (Ref (ST s) a); getLifted :: (LiftedMonad rep m) => Ref rep a -> m a; getLifted = get . liftRef; setLifted :: (LiftedMonad rep m) => Ref rep a -> a -> m (); setLifted = set . liftRef; modifyLifted :: (LiftedMonad rep m) => Ref rep a -> (a -> a) -> m (); modifyLifted = modify . liftRef; Now when you need a new Ref, use newSTRef, and when you need to use the Ref, use getLifted, setLifted and modifyLifted. They'll work equally well with (ST s) as with TransformedMonad. Hmm. Yes. But you still haven't addressed dropping references created in the transformed monad back into the underlying one again. And this does seem to be getting rather complicated and expensive... are you sure it's worth the candle? I'm quite happy to have references depend on a state identifier myself. John

1 0

joining
by ilje 07 Feb '02

07 Feb '02

Hi. I want to join please. thanks in advance. Ilan.

1 0

Re: Reference types
by Ashley Yakeley 06 Feb '02

06 Feb '02

At 2002-02-06 03:38, John Hughes wrote: >Well, I'm still not convinced. A reference *value* can't have the type > > (LiftedMonad (ST s) m) => Ref m a Oh, yeah, you're right. I made a mistake here: newSTRef :: a -> Ref (ST s) a; newSTLiftedRef :: (LiftedMonad (ST s) m) => a -> Ref m a; This should of course be: newSTRef :: a -> (ST s) (Ref (ST s) a); newSTLiftedRef :: (LiftedMonad (ST s) m) => a -> m (Ref m a); ...which won't help, because the Ref will only work in the monad that created it. But I have a solution... data Ref m a = MkRef { get :: m a, set :: a -> m (), modify :: (a -> a) -> m () }; -- m somehow uses 'rep' internally class (Monad rep, Monad m) => LiftedMonad rep m where { lift :: rep a -> m a; } instance LiftedMonad (ST s) (ST s) where { lift = id; } instance LiftedMonad (ST s) TransformedMonad where ... liftRef :: (LiftedMonad rep m) => Ref rep a -> Ref m a; liftRef ref = ... newSTRef :: a -> (ST s) (Ref (ST s) a); getLifted :: (LiftedMonad rep m) => Ref rep a -> m a; getLifted = get . liftRef; setLifted :: (LiftedMonad rep m) => Ref rep a -> a -> m (); setLifted = set . liftRef; modifyLifted :: (LiftedMonad rep m) => Ref rep a -> (a -> a) -> m (); modifyLifted = modify . liftRef; Now when you need a new Ref, use newSTRef, and when you need to use the Ref, use getLifted, setLifted and modifyLifted. They'll work equally well with (ST s) as with TransformedMonad. >Are you really in Seattle? If so, you must be a real nightbird or a >tremendously early riser! Um, yeah, that's a side effect of unemployment, along with haemorrhaging open-source software (see Truth). Does anyone need a Haskell developer in the greater Seattle area? -- Ashley Yakeley, Seattle WA

1 0