Re: [Haskell-cafe] Composing functions with runST
Yitzchak Gale wrote: Here is a concrete example: Let's say you want to shuffle a large list randomly, within a larger application that lives inside some MTL monad stack. Among other things, your monad m satisfies (RandomGen g, MonadState g m), perhaps after a lift. Well, it turns out that using Data.Sequence or Data.IntMap to shuffle a list becomes prohibitive if you might have more than about 10^5 elements in your list. So in that case you will need to use a mutable array, and you now need ST. Combining ST and MTL can be messy, even in this simple case. You will probably write something with a type like RandomGen g = [a] - g - ST s ([a], g) But why would you even want to do this? It's ugly and cumbersome. You'd plug a runST in there and get shuffle :: RandomGen g = [a] - g - ([a], g) or lift it into a state monad. Telling the world that you messed with imperative code inside is completely pointless, since the only thing you could possibly do with the result anyway is apply runST to it. Wouldn't it be nice if instead you could just write: shuffle :: (RandomGen g, MonadState g m) = [a] - m [a] shuffle = stToState . shuffleST It seems, what you really want is shuffleST :: RandomGen g = [a] - StateT g ST [a] No need to stick the generator into a mutable variable. Maybe you even want a MonadST class, analogous to MonadIO. Uhm... use MonadState in the first place? You mean use ST in the first place. No, I don't. -Udo signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
Simon Peyton-Jones wrote: Conor and others are right; it's all to do with type inference. There is nothing wrong with the program you are writing, but it's hard to design a type inference algorithm that can figure out what you are doing. The culprit is that you want to instantiate a polymorphic function (here (.) or ($) in your examples) with a higer-rank polymorphic type (the type of runST, in this case). That requires impredicative polymorphism and while GHC now allows that, it only allows it when it's pretty obvious what is going on --- and sadly this case is not obvious enough. I don't know enough type theory to suggest a specific patch, but I hope a future version of GHC can do the right thing for (.) and ($) in this situation (and possibly for other functions that simply rearrange their arguments, like flip). From a friendliness-to-newbies point of view, these error messages are a tremendous wart. I've been on haskell-cafe for a little over three months and seen postings from three people who were tripped up by this (the first of them was myself). So I can't just tell someone who's just starting to learn Haskell that f $ g y is equivalent to f (g y); I have to say those two are *almost always* equivalent, but if you use $ and the compiler complains about not being able to match the expected and the inferred type and a type signature in the error message has the word 'forall', try rewriting that expression without the $ and see if it compiles. Eeeww. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Possible (GHC or HGL) bug or ??
[EMAIL PROTECTED] wrote: Calvin Smith wrote: When the problem occurs, there is a message to the console that says: thread blocked indefinitely. I can reproduce this on OS X with ghc-6.4.2, X11-1.1 and HGL-3.1. The console message is rare but I also got it once. This looks like a bug in HGL, perhaps some issue with polling the event queue in a threaded fashion. Thanks very much for checking this on a different platform and GHC. I filed a bug report with the HGL maintainer. p.s. Any stylistic or other comments about the code welcome too. It might also be a good idea not to mess with trigonometry when creating the snowflake. Yes, that is much cleaner. The following code demonstrates this. Your solution is very elegant, and a big improvement over my messy first solution. Thanks for the very instructive code! Regards, Calvin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
On 03/01/07, Seth Gordon [EMAIL PROTECTED] wrote: So I can't just tell someone who's just starting to learn Haskell that f $ g y is equivalent to f (g y); I have to say those two are *almost always* equivalent, but if you use $ and the compiler complains about not being able to match the expected and the inferred type and a type signature in the error message has the word 'forall', try rewriting that expression without the $ and see if it compiles. Eeeww. Why would someone just starting to learn Haskell be using ST? The canonical tutorial structure is to start with the pure stuff and only introduce the (more complicated!) impure stuff (ST, IORefs, etc.) in an 'advanced techniques' or similar section. -- -David House, [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] darcs repo for yampa + gadt
Folks, I have a version of Yampa with Henrik Nilsson's GADT optimizations that I cleaned up for ghc 6.6 and cabalized. Would it be possible to set it up at darcs.haskell.org and if so how should I go about it? Thanks, Joel -- http://wagerlabs.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
David House wrote: So I can't just tell someone who's just starting to learn Haskell that f $ g y is equivalent to f (g y); I have to say those two are *almost always* equivalent, but if you use $ and the compiler complains about not being able to match the expected and the inferred type and a type signature in the error message has the word 'forall', try rewriting that expression without the $ and see if it compiles. Eeeww. Why would someone just starting to learn Haskell be using ST? The canonical tutorial structure is to start with the pure stuff and only introduce the (more complicated!) impure stuff (ST, IORefs, etc.) in an 'advanced techniques' or similar section. I (and one other person on this list) ran into this issue when I was trying to use takusen to make Haskell talk to a RDBMS. You obviously need to learn advanced techniques to *implement* such a thing, but you shouldn't need advanced knowledge to *use a library* that happens to use higher-rank polymorphic types in its API. There are many routes to fluency in a language, and not everybody is suitable for the route of here are the axioms underlying the language and the simplest code that applies them; after you thoroughly understand those, we'll show you how to make something practical. Some of us prefer the route of here are some examples of how to get practical things done; after you're comfortable with them, we'll show you the theory that underlies them. Actually, I suspect that *most* of us prefer the second route. Set theory is closer to the theoretical foundations of mathematics than arithmetic, but when elementary schools tried teaching kids set theory, it didn't work out so well. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Glasgow Distributed Haskell
Joel Reymont [EMAIL PROTECTED] wrote: I'm after Erlang in Haskell, if you will, for fault-tolerance and scalability. I think the way to do Erlang in Haskell is to build a middleware layer on top of the language, not try to make the language into something it is not. In this kind of environment you need to be able to upgrade components while the system is running. The careful Haskell habit of separating stateful operations from pure functions is useful here. I gather that the HAppS project is working along similar lines, and for similar reasons. Take a look at it. http://happs.org/HAppS/README.html Paul. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
On 1/3/07, David House [EMAIL PROTECTED] wrote: On 03/01/07, Seth Gordon [EMAIL PROTECTED] wrote: So I can't just tell someone who's just starting to learn Haskell that f $ g y is equivalent to f (g y); I have to say those two are *almost always* equivalent, but if you use $ and the compiler complains about not being able to match the expected and the inferred type and a type signature in the error message has the word 'forall', try rewriting that expression without the $ and see if it compiles. Eeeww. Why would someone just starting to learn Haskell be using ST? The canonical tutorial structure is to start with the pure stuff and only introduce the (more complicated!) impure stuff (ST, IORefs, etc.) in an 'advanced techniques' or similar section. (slightly OT) It's true that this is the typical way of learning Haskell, but I for one think it's a bad way of learning Haskell. Very few real world programs get by without the impure stuff, so if you give the newbie the impression that it isn't there (by postponing it) there's a chance he'll run into a situation where he needs it before it's been even mentioned (queue newbie going bah, academic language and switching to C++). I find that the Haskell introductions I like the most are the ones that accompany papers about STM and such. I.e. ones which have to teach the reader about the basics of Haskell IO, but doesn't have enough space to start with the pretty stuff. Mix that with some actual comutations to show off some pretty stuff and you'll have a newbie who is both excited about the cool looking features of the pure aspects of Haskell, but completely aware of the fact that you can do impure stuff as well. Oh yeah, I agree that the relationship between ($) and (.) is a bit ugly from the user's perspective. It may have very good reasons, but I'd prefer consistency towards the user (i.e. spot when someone is using ($) with higher ranked types and do rewriting) rather than consistency towards the compiler. -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Arrays performance
Quoting Udo Stenzel [EMAIL PROTECTED]: [EMAIL PROTECTED] wrote: It isn't, but not for the reasons you might suspect. You're using 'nub', which is quadratic, and your 'coupage' is also quadratic because it uses 'lookup' on a list, which is linear, a linear number of times. You can get this down to O(n * log n) if you replace these lists by Data.Map and Data.Set, to get down to O(n) you need arrays there, too, but that would be pointless, because you're also using 'sort', which is already in O(n * log n). The core of the algorithm is clearly linear in the length of its input. (Btw, putting 'devil' into a state monad doesn't make much sense. I think, ordinary recursion would be more clear. In fact, it's a 'foldl'.) Ok, I've simplified some code and moved to foldl, to collect the result. I paste new version in case you care give me some moe suggestion. Thanks. Paolino ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Socket Programming
Or you could ignore the problem of shutdown altogether: http://swig.stanford.edu/~candea/papers/crashonly/ On Jan 2, 2007, at 12:20 PM, Chris Kuklewicz wrote: Mark Goldman wrote: I am trying to write a toy echo server that can handle multiple connections. I would like to be able to test and see if there are any connections waiting to be accepted on a socket. In C and related languages I would use something like select or poll to be nice to the OS, what would I use with the current haskell libs given that I can't seem to find a function to test if accept would block or not? -mdg The wiki page http://haskell.org/haskellwiki/Concurrency_demos/ Graceful_exit uses accepting connections as its example. The main idea is use accept (which blocks) in a background thread and which provides the resulting connections to some inter-thread data stream: MVar, MChan, TMVar, TChan, or your own structure. Shutting down a system is usually subtle, and that wiki page concentrates on a trying to create a solution which provides dependable shutdown semantics. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
Hi, It's true that this is the typical way of learning Haskell, but I for one think it's a bad way of learning Haskell. Very few real world programs get by without the impure stuff, so if you give the newbie the impression that it isn't there (by postponing it) there's a chance he'll run into a situation where he needs it before it's been even mentioned (queue newbie going bah, academic language and switching to C++). I agree. It also confuses matters when the newbie is suddenly given a library of IO code to use -- but told to ignore it -- they suddenly start wondering why it is so difficult to do anything useful in Haskell. A consequence of which seems that the student becomes afraid (and ignorant) of Haskell. I find that the Haskell introductions I like the most are the ones that accompany papers about STM and such. I.e. ones which have to teach the reader about the basics of Haskell IO, but doesn't have enough space to start with the pretty stuff. I agree with this also. I don't think it is a difficult feat teaching an absolute beginner how do some some basic stuff with the IO monad. This shows straight away that haskell can do some useful stuff other than adding numbers together in Hugs. Mix that with some actual comutations to show off some pretty stuff and you'll have a newbie who is both excited about the cool looking features of the pure aspects of Haskell, but completely aware of the fact that you can do impure stuff as well. Yes, I wish this approach was applied much more often. Semi-related to this: I taught an algorithms and data structures class last term. In one of the classes the students were given an equation to solve and they were frantically typing it into their calculators, replacing the variable parameters with numbers. I told them they could all finish the class in 5 minutes if they used Haskell. Type the equation as it is and use higher-order functions to work out the parameters. The look of horror on the student's faces when I mentioned the 'H' word was priceless. However, they were all prepared to spend 50 minutes writing a Java program which would have the same effect. Chris. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
It's true that this is the typical way of learning Haskell, but I for one think it's a bad way of learning Haskell. Very few real world programs get by without the impure stuff, so if you give the newbie the impression that it isn't there (by postponing it) there's a chance he'll run into a situation where he needs it before it's been even mentioned (queue newbie going bah, academic language and switching to C++). On the contrary, I think it's an excellent way of learning Haskell. I'm writing a lot of useful Haskell code with only one IO action (interact). I don't think I could reasonably construct an introductory problem that couldn't be solved with it, and I haven't yet found an application for which I've needed more. I think it's destructive to teach people we have a wonderful new paradigm of programming that solves all sorts of problems, but all we're going to use it for is doing what we did with C++ anyway. That's just my 2¢ -- I like Haskell specifically because I don't have to do things in order and I don't have to do things in an imperative style, I would love for more people to be taught about this wonderful thing. Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
Hi On the contrary, I think it's an excellent way of learning Haskell. I'm writing a lot of useful Haskell code with only one IO action (interact). I don't think I could reasonably construct an introductory problem that couldn't be solved with it, and I haven't yet found an application for which I've needed more. I think interact is a bit ugly. Most introductory problems are take a small amount of data, do something. In that case using Hugs/GHCi with :main arguments to give in the arguments, getArgs to read them and putStrLn to show the results is a very beautiful and does about all that you need. Very few programs are actually interactive - if they are they should usually get a GUI. As for beginner issues with rank-2 types, I've been learning Haskell for years now, and have never felt the need for a rank-2 type. If the interface for some feature requires rank-2 types I'd call that an abstraction leak in most cases. It certainly means that you can't properly Hoogle for it, can't compile it with Yhc, can't do full type inference etc. Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composing functions with runST
Hi, On the contrary, I think it's an excellent way of learning Haskell. I'm writing a lot of useful Haskell code with only one IO action (interact). I don't think I could reasonably construct an introductory problem that couldn't be solved with it, and I haven't yet found an application for which I've needed more. I think it's destructive to teach people we have a wonderful new paradigm of programming that solves all sorts of problems, but all we're going to use it for is doing what we did with C++ anyway. Yes, but the point is most students have already been poisoned with C++ (or Java). They don't see the point in Haskell becuase they can't see the wood for the trees. The only way to get them interested in Haskell in the first place is to make it look vaguely like C++ (or Java) -- it's like coercing a Donkey with a carrot. Once they are interested - show them there is a lot more to Haskell than imperative-style behaviour, that way they may also see the elegence of purely functional programming. That's just my 2¢ -- I like Haskell specifically because I don't have to do things in order and I don't have to do things in an imperative style, I would love for more people to be taught about this wonderful thing. So would I. But in reality it just doesn't seem to work like that. Chris. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] State separation/combination pattern question
Hi Reto,
On Thu, Dec 21, 2006 at 10:11:22PM -0800, Reto Kramer wrote:
I've tried to thread the two states (StateA and StateB) using a chain
of StateT ... StateT ..., but couldn't really make that work.
That is how I would write it; I have attached code for your example.
It
seems rather arbitrary in this case which state to make the inner/
outer one
The choice is indeed arbitrary.
and depending on this ordering the lifts have to go with
one or the other set of store calls.
If you don't mind turning on overlapping and undecidable instances then
you don't need to manually lift things at all.
Thanks
Ian
{-# OPTIONS_GHC -fglasgow-exts
-fallow-overlapping-instances
-fallow-undecidable-instances #-}
import Control.Monad.Trans (MonadTrans)
import Control.Monad.State (StateT, evalStateT, get, put, lift)
-- StateA
type StateA = [Integer]
newtype MonadAT m a = MonadAT (StateT StateA m a)
deriving (Monad, MonadTrans)
class Monad m = MonadA m where
getA :: m StateA
putA :: StateA - m ()
instance Monad m = MonadA (MonadAT m) where
getA = MonadAT get
putA = MonadAT . put
instance (MonadTrans t, MonadA m, Monad (t m)) = MonadA (t m) where
getA = lift getA
putA = lift . putA
evalAT :: Monad m = MonadAT m a - StateA - m a
evalAT (MonadAT x) = evalStateT x
-- StateB
type StateB = [Integer]
newtype MonadBT m a = MonadBT (StateT StateB m a)
deriving (Monad, MonadTrans)
class Monad m = MonadB m where
getB :: m StateB
putB :: StateB - m ()
instance Monad m = MonadB (MonadBT m) where
getB = MonadBT get
putB = MonadBT . put
instance (MonadTrans t, MonadB m, Monad (t m)) = MonadB (t m) where
getB = lift getB
putB = lift . putB
evalBT :: Monad m = MonadBT m a - StateB - m a
evalBT (MonadBT x) = evalStateT x
-- The program
type Monads = MonadBT (MonadAT IO)
main :: IO ()
main = do res - evalAT (evalBT exec []) []
print res
exec :: Monads (StateA, StateB)
exec = do foo
bar
foo
foo
bar
a - getA
b - getB
return (a, b)
foo :: MonadA m = m ()
foo = do st - getA
putA (1 : st)
bar :: MonadB m = m ()
bar = do st - getB
putB (2 : st)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Monad Set via GADT
To improve my understanding of GADT, I tried to define a Set datatype,
with the usual operations, so that it can be made a member of the
standard Monad class. Here I report on my experiments.
First, I recap the problem. Data.Set.Set can not be made a Monad because
of the Ord constraint on its parameter, while e.g. (return :: a - m a)
allows any type inside the monad m. This problem can be solved using an
alternative monad class (restricted monad) so that the Ord context is
actually provided for the monad operations. Rather, I aimed for the
standard Monad typeclass.
To avoid reinventing Data.Set.Set, my datatype is based on that.
Basically, when we know of an Ord context, we use a Set. Otherwise, we
use a simple list representation. Using a list is just enough to allow
the implementation of return (i.e. (:[])) and (=) (i.e. map and (++)),
so while not being very efficient, it is simple. Other non-monadic
operators require an Ord context, so that we can turn lists into Set.
My first shot at this was:
data SetM a where
L :: [a] - SetM a
SM :: Ord a = Set.Set a - SetM a
However, this was not enough to convince the type checker to use the Ord
context stored in SM. Specifically, performing union with
union (SM m1) (SM m2) = SM (m1 `Set.union` m2)
causes GHC to report No instance for (Ord a). After some experiments,
I found the following, using a type equality witness:
data Teq a b where Teq :: Teq a a
data SetM a where
L :: [a] - SetM a
SM :: Ord w = Teq a w - Set.Set w - SetM a
Now if I use
union (SM p1 m1) (SM p2 m2) =
case (p1,p2) of
(Teq,Teq) - SM Teq (m1 `Set.union` m2)
it typechecks! This rises some questions I cannot answer:
1) Why the first version did not typececk?
2) Why the second one does?
3) If I replace (Teq a w) with (Teq w a), as in
SM :: Ord w = Teq w a - Set.Set w - SetM a
then union above does not typecheck! Why? I guess the type variable
unification deriving from matching Teq is not symmetric as I expect it
to be...
Below, I attach the working version. Monad and MonadPlus instances are
provided for SetM. Conversions from/to Set are also provided, requiring
an Ord context. Efficient return and mzero are included, forcing the
Set representation to be used, and requiring Ord (these could also be
derived from fromSet/toSet, however).
Comments are very welcome, of course, as well as non-GADT related
alternative approaches.
Regards,
Roberto Zunino.
\begin{code}
{-# OPTIONS_GHC -Wall -fglasgow-exts #-}
module SetMonad
( SetM()
, toSet, fromSet
, union, unions
, return', mzero'
) where
import qualified Data.Set as S
import Data.List hiding (union)
import Control.Monad
-- Type equality witness
data Teq a b where Teq :: Teq a a
-- Either a list or a real Set
data SetM a where
L :: [a] - SetM a
SM :: Ord w = Teq a w - S.Set w - SetM a
instance Monad SetM where
return = L . (:[])
m = f = case m of
L l - unions (map f l)
SM Teq s - unions (map f (S.toList s))
instance MonadPlus SetM where
mzero = L []
mplus = union
-- Efficient variants for Ord types
return' :: Ord a = a - SetM a
return' = SM Teq . S.singleton
mzero' :: Ord a = SetM a
mzero' = SM Teq S.empty
-- Set union: use the best representation
union :: SetM a - SetM a - SetM a
union (L l1) (L l2) = L (l1 ++ l2)
union (SM p1 m1) (SM p2 m2) = case (p1,p2) of
(Teq,Teq) - SM Teq (m1 `S.union` m2)
union (L l1) (SM p m2) = case p of
Teq - SM Teq (m2 `S.union` S.fromList l1)
union s1 s2 = union s2 s1
-- Try to put a SM first before folding, to improve performance
unions :: [SetM a] - SetM a
unions = let isSM (SM _ _) = True
isSM _= False
in foldl' union (L []) . uncurry (++) . break isSM
-- Conversion from/to Set requires Ord
toSet :: Ord a = SetM a - S.Set a
toSet (L l)= S.fromList l
toSet (SM p m) = case p of Teq - m
fromSet :: Ord a = S.Set a - SetM a
fromSet = SM Teq
-- Tests
test :: IO ()
test =
do let l = [1..3] :: [Int]
s = fromSet (S.fromList l)
g x = return' x `mplus` return' (x+100)
print $ S.toList $ toSet $
do x - s
y - s
return' (x+y)
-- [2,3,4,5,6]
print $ S.toList $ toSet $
do x - s
g x
-- [1,2,3,101,102,103]
print $ S.toList $ toSet $
do x - s
y - g x
return' y
-- [1,2,3,101,102,103]
print $ S.toList $ toSet $
do x - s
y - g x
g y
-- [1,2,3,101,102,103,201,202,203]
print $ S.toList $ toSet $
do x - s
y - return (const x) -- no Ord!
return' (y ())
-- [1,2,3]
\end{code}
Re: [Haskell-cafe] darcs repo for yampa + gadt
joelr1: Folks, I have a version of Yampa with Henrik Nilsson's GADT optimizations that I cleaned up for ghc 6.6 and cabalized. Would it be possible to set it up at darcs.haskell.org and if so how should I go about it? There are some details here: http://haskell.org/haskellwiki/How_to_write_a_Haskell_program If you hang on a couple of weeks, you should be able to upload it to the hackage database. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] GADT proofs of FunDeps?
I am investigating mixing FunDeps with the type equality GADT data Teq a b where Teq :: Teq a a Basically, I would like to write something like proof :: (C a b1, C a b2) = Teq b1 b2 proof = unsafeCoerce# Teq provided the FunDep class C a b | a - b Is this safe? Any caveat? Regards, Roberto Zunino. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
